303. Chain Into Spiral
A mosaic worker has a tray with rows rows and cols columns of empty slots, and a chain of tiles whose first tile is head. Tiles are laid in chain order starting at the top-left slot, moving right along the top edge, then down the right edge, then left along the bottom edge, then up the left edge, and then spiralling inward in the same clockwise way.
Return the tray as a matrix of rows rows and cols columns where each slot holds the number written on the tile placed there. Slots that never receive a tile hold -1. If the chain has more tiles than the tray has slots, lay as many as fit and ignore the rest. Tile numbers are never negative, so -1 is unambiguous. The tray has at most 100,000 slots.
Example 1
- Input:
- rows = 3, cols = 4, head = [5,8,13,21,34,55,89]
- Output:
- [[5,8,13,21],[-1,-1,-1,34],[-1,-1,89,55]]
- Explanation:
The tiles run along the top row: 5 8 13 21, then down the right edge: 34, 55, and back along the bottom row: 89, giving [[5, 8, 13, 21], [-1, -1, -1, 34], [-1, -1, 89, 55]].
Example 2
- Input:
- rows = 2, cols = 3, head = [9,1,7,3,6,2,4,4]
- Output:
- [[9,1,7],[2,6,3]]
- Explanation:
The tray holds only six slots: top row 9 1 7, then down to 3, then left along the bottom row 6 2, giving [[9, 1, 7], [2, 6, 3]]. The last two tiles do not fit and are ignored.
Constraints
1 ≤ rows, cols ≤ 105
rows * cols ≤ 105
0 ≤ chain length ≤ 105
0 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(rows * cols + n)
- Space
- O(rows * cols)