# Solution: Find the center of the maze

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

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

# 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.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],    y + DIRECTION_VECTORS[direction],  ]; }/** * @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).

# 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. []
• Matrix with only 1 row, e.g. [[1, 2, 3]]
• Matrix with only 1 column, e.g. [, , ]
• Odd-sized square matrix
• Even-sized square matrix

--

-- ## S7rthak

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Codeforces(Expert)