Walk a Matrix
Course launching August 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
You are given a
matrix represented by an
r x c 2-dimensional array of integers.
Starting at the root
matrix[row = 0][column = 0] and walking from the perimeter of the matrix towards the center,
you want to touch each element once in the matrix by traversing it clockwise in spiral order.
Return a 1-dimensional array of all the elements from the matrix in the order you visited them.
Write a function
walkMatrix that takes an
r x c 2D array and returns a 1D array of all the elements in the matrix printed in clockwise order.
Note: Do not consider the result array when calculating your space complexity.
// Input const matrix = [ [0, 1, 2, 3], [11, 12, 13, 4], [10, 15, 14, 5], [9, 8, 7, 6], ]; // Output: walkMatrix(matrix) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
Validate My Answer
You can do this in linear time O(n) and only need to visit each cell once.
You may be tempted to use an additional data structure which would add an additional linear O(n) space. Based on the board dimensions and location, you can actually solve this with constant space O(1).
Ensure you handle your indexes well and don't have off-by-one when tracking or let them bleed into cells you have already visited.
Does your solution handle any board dimension
r x c? The input can be a square, vertical rectangle, or horizontal rectangle.
Does your solution handle an empty matrix
0 x 0input?
Does your solution handle a
1 x cand
r x 1input correctly without repeating values?