54 — Spiral Matrix
Restating Info We’re Already Given:
- Return the elements of a 2D matrix in clockwise, outward to inward order.
- Based on the problem’s constraints, a 1x1 is the smallest matrix that could potentially be passed in.
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- Can anything be said about the uniqueness of the numbers?
Discuss Solution #1:
One way we could do this is to set boundary conditions in all 4 directions that tell us where we currently are in our spiral traversal. To begin, we initialize top to 0 as the top begins at index 0, bottom to len(matrix) -1 as the bottom is the subarray at index len(matrix) -1, left to 0, and right to len(matrix[0])-1.
Then, we perform one spiral of the current 2D matrix (one right, down, left, and then up traversal) and update the boundary variables accordingly, continuing until we have all the matrix’s elements in spiral order.
Code Solution #1:
Discuss Solution #2:
Another way we can do this is to pop the 0th index, convert its elements to a 1D array, and rotate the remaining part of the array counterclockwise.
To do the first part, we can utilize zip and *arg. We take the first (index zero) outer index, pop it, zip it, and convert it to a list. Then, we recurse on the remaining part of the matrix, counterclockwise rotated. We can do this by zipping the remaining part of the matrix (already popped 0th index) and reversing the order.
Code Solution #2:
Runtime/Space Complexity:
The runtime complexity is O(m*n) for a 2D array with m subarrays and length n for each subarray. We have to visit each index and subindex when making the resulting spiral matrix array.
The space complexity is O(1) if you don’t count the array we return or O(m*n) if you count the array we return because the length of the resulting spiral matrix array is equal to the amount of numbers in the 2D matrix.
Test Cases:
- 1x1 matrix
- 1xn matrix
- mx1 matrix
- mxn matrix
