Walk a Matrix Coding Interview Question | Skilled.dev
Interview Question

Walk a Matrix

Course launching November 17, 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.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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

  1. You can do this in linear time O(n) and only need to visit each cell once.

  2. 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).

  3. 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.

  4. Does your solution handle any board dimension r x c? The input can be a square, vertical rectangle, or horizontal rectangle.

  5. Does your solution handle an empty matrix [[]] 0 x 0 input?

  6. Does your solution handle a 1 x c and r x 1 input correctly without repeating values?