Solution: Find the center of the maze

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.

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
S7rthak

S7rthak

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