spiral
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
function spiralOrderTwo(n) {
// create nxn grid set to 0.
const grid = new Array(n).fill().map(_ => new Array(n).fill(0));
// clockwise directions
const directions = [
[1, 0], // down
[0, -1], // left
[-1, 0], // up
[0, 1], // right
];
// determines which direction to go.
let dirIdx = 0;
const totalDirectionChanges = 2;
let stepsNumber = 1;
let directionChangesCount = 0;
let [r, c] = [Math.floor(n / 2), Math.floor(n / 2)];
let value = 1;
while (value < n * n - 1) {
if (directionChangesCount < totalDirectionChanges) {
// for every direction change, do stepsNumber of steps.
for (let i = 0; i < stepsNumber; i++) {
[r, c] = [r + directions[dirIdx][0], c + directions[dirIdx][1]];
// exit loop when we go beyond the grid's bottom right cell.
if (r > n - 1 || c > n - 1) {
break;
}
grid[r][c] = value;
value += 1;
}
directionChangesCount += 1;
// change directions.
dirIdx = (dirIdx + 1) % directions.length;
} else {
// number of steps increases after every 2 direction changes.
stepsNumber += 1;
// reset count of direction changes.
directionChangesCount = 0;
}
}
return grid;
}
const res = spiralOrderTwo(3);
console.log(res.map(row => row.join(" ")).join("\n"));
function runTests() {
const tests = [
// Example from book
[5, [
[16, 17, 18, 19, 20],
[15, 4, 5, 6, 21],
[14, 3, 0, 7, 22],
[13, 2, 1, 8, 23],
[12, 11, 10, 9, 24]
]],
// Edge case - 1x1
[1, [[0]]],
// Edge case - 3x3
[3, [
[4, 5, 6],
[3, 0, 7],
[2, 1, 8]
]],
];
console.log("RUN");
for (const [n, want] of tests) {
const got = spiralOrderTwo(n);
console.assert(JSON.stringify(got) === JSON.stringify(want),
`\nspiral(${n}): got: ${JSON.stringify(got)}, want: ${JSON.stringify(want)}\n`);
}
}
runTests();
// runTests();
JavaScript
INFO