Solution: Find the center of the maze

A man starts from the north-west (top-left) corner of the land and begins walking towards the center of it, in a spiral manner. As the man moves, he keeps track of the number of trees growing on each block of land and records the counts on his journal until he reaches his destination. This list of numbers is the key to unlock treasures hidden there.

You need to be faster than him. Satellite imagery has already provided you the count of trees on each block of land. You need to trace them in a spiral manner, and print out the list of numbers to unlock the treasure.

Example:

Input:
23 17 34 5
1 9 12 14
8 2 3 16
Output:
23 17 34 5 14 16 3 2 8 1 9 12
Explanation:
Starting from the top-left corner (23), we move right, then down, then left, then up, and finally right.
──────┐
┌────>│
└─────┘

Solution:

Observe

1. At every step, we traverse from the current location to the adjacent element in the current direction. Then, when we make a turn, we always turn right.
   The direction will loop in this order: right, down, left, up, then back to right, down, etc.

Insights:
To determine the coordinate of the next position, observe this relationship between the current position(x, y) and the next position, depending on the current direction:

2. If going right, the next position is (x+1, y)
If going left, the next position is (x-1, y)
If going up, the next position is (x, y-1)
If going down, the next position is (x, y+1)

3. The logic to make a right turn should be handled well in order to correctly calculate the next position.

4. We make a turn when we hit the border, or are about to visit an already visited element.

Insights:
Checking for borders is simple. What we need is a way to check if we are about to revisit an element. There are many ways to do it, but we will go with a simple solution of using a same-size boolean matrix as markers.

5. The spiral ends when there is no more unvisited neighboring element, or if we have traversed through all the elements (if we keep track of the count).

Insights:
The simplest way to detect the end is with the element count.

Algorithm

1. Create a same-size boolean matrix to use as markers.
2. Create an empty output list.
3. Start with RIGHT direction and at the top-left corner of the matrix.
4. While the output list is still not full, do the following:
   4.1 Add the current number to the output list.
   4.2 Check if we should make a right rotation, and change the direction if needed.
   4.3 Take 1 step to the next position, based on the calculated direction.
5. Return the output list.

Code

const DIRECTION_VECTORS = [
  [1, 0]  /* right */,
  [0, 1]  /* down */,
  [-1, 0] /* left */,
  [0, -1] /* up */,
];
/**
 * @param {Array<Array<number>>} maze
 * @return {Array<number>} List of numbers from the given array printed
      out in a spiral manner.
 */
function findTheCenterOfTheMaze(maze) {
  const n = maze.length;
  const m = maze[0].length;
  const markers = createZeroMatrix(n, m);
  const output = [];
  let x = 0; // x is for left-right direction.
  let y = 0; // y is for up-down direction.
  let direction = 0;
  while (output.length < (n * m)) {
    output.push(maze[y][x]);
    // Marks that we have travelled to this position.
    markers[y][x] = 1;
    // Calculates the next position.
    let newX, newY;
    [newX, newY] = getNextPosition(x, y, direction);
    // Checks if this new position is valid (within border, not visited).
    // If not, make a right turn and re-calculate new position.
    if (newX < 0 || newX >= m || newY < 0 || newY >= n || 
        markers[newY][newX]) {
      // The modulo of 4 is to loop the direction value back to 0, 
      // when it goes higher than 3.
      direction = (direction + 1) % 4;
      [newX, newY] = getNextPosition(x, y, direction);
    }
    [x, y] = [newX, newY];
  }
  return output;
}
/**
 * @param {Number} x
 * @param {Number} y
 * @param {Number} direction
 * @return {Array<Number>} A new pair of (x,y).
 */
function getNextPosition(x, y, direction) {
  return [
    x + DIRECTION_VECTORS[direction][0],
    y + DIRECTION_VECTORS[direction][1],
  ]; 
}
/**
 * @param {Number} n
 * @param {Number} m
 * @return {Array<Array<number>>} A zero matrix of size n * m.
 */
function createZeroMatrix(n, m) {
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push(new Array(m).fill(0));
  }
  return matrix;
}

Complexity Analysis

1. Creating the zero matrix is of O(N * M) time complexity.
2. Constructing the output list requires traversing through each element once, so the complexity here is also O(N * M).

Overall, the time complexity is O(N * M).

Testing

Treat your code like a black box (you don’t know the internal implementation), and put in your best effort to try to break it.
Start with a couple normal test cases first.
Then, start brainstorming edge cases. Here are some:

• Empty matrix: [[]]
• One-element array, e.g. [[1]]
• Matrix with only 1 row, e.g. [[1, 2, 3]]
• Matrix with only 1 column, e.g. [[1], [2], [3]]
• Odd-sized square matrix
• Even-sized square matrix