function spiralMatrix(dimension) {
let matrix = [];
// create blank matrix based from given dimension
for (let i = 0; i < dimension; i++) {
matrix.push(new Array(dimension).fill(0))
}
let counter = 1;
let startRow = 0, endRow = dimension, startColumn = 0, endColumn = dimension;
while (startRow < endRow && startColumn < endColumn) {
// top left -> top right
for (let i = startColumn; i < endColumn; i++) {
matrix[startRow][i] = counter++;
}
startRow++
// top right -> bottom right
for (let i = startRow; i < endRow; i++) {
matrix[i][endColumn - 1] = counter++;
}
endColumn--;
// bottom right -> bottom left
for (let i = endColumn - 1; i >= startColumn; i--) {
matrix[endRow - 1][i] = counter++;
}
endRow--;
// bottom left -> top left
for (let i = endRow; i > startRow; i--) {
matrix[i - 1][startColumn] = counter++;
}
startColumn++;
}
return matrix;
}
Category: Loop
let gameOfLife = function(board) {
if (!board) return [];
let LIVE = 1,
DEAD = 0,
ALIVE_TO_DEAD = 0b01, // [next state, current state]
ALIVE_TO_ALIVE = 0b11,
DEAD_TO_ALIVE = 0b10,
DEAD_TO_DEAD = 0b00,
maxRow = board.length - 1,
maxCol = board[0].length - 1;
function getAdjacentCount(row, col, valueToCompare) {
let sum = 0;
for (let i = Math.max(row - 1, 0); i <= Math.min(row + 1, maxRow); i++) {
for (let j = Math.max(col - 1, 0); j <= Math.min(col + 1, maxCol); j++) {
if (i === row && j === col) continue;
if (board[i][j] & 1 === valueToCompare) sum = sum + 1;
}
}
return sum;
}
function getNextValue(row, col) {
const val = board[row][col];
let liveNeighbors = getAdjacentCount(row, col, LIVE);
if (val === LIVE) {
// Any live cell with fewer than two live neighbors dies, as if caused by under-population.
// Any live cell with more than three live neighbors dies, as if by over-population..
if (liveNeighbors < 2 || liveNeighbors > 3) {
return ALIVE_TO_DEAD;
}
// Any live cell with two or three live neighbors lives on to the next generation.
return ALIVE_TO_ALIVE;
}
// cell is DEAD
else {
// Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
if (liveNeighbors === 3) {
return DEAD_TO_ALIVE;
}
// no condition
return DEAD_TO_DEAD;
}
}
for (let row = 0; row <= maxRow; row++) {
for (let col = 0; col <= maxCol;col++) {
board[row][col] = getNextValue(row, col);
}
}
for (let row = 0; row <= maxRow; row++) {
for (let col = 0; col <= maxCol;col++) {
board[row][col] = board[row][col] >> 1;
}
}
};
let gameOfLife = function(board) {
if (!board) return [];
let copy = [],
LIVE = 1,
DEAD = 0,
maxRow = board.length - 1,
maxCol = board[0].length - 1;
function getAdjacentCount(row, col, valueToCompare) {
let sum = 0;
for (let i = Math.max(row - 1, 0); i <= Math.min(row + 1, maxRow); i++) {
for (let j = Math.max(col - 1, 0); j <= Math.min(col + 1, maxCol); j++) {
if (i === row && j === col) continue;
if (copy[i] && copy[i][j] !== undefined) {
if (copy[i][j] === valueToCompare) sum = sum + 1; //?
}
else {
if (board[i][j] === valueToCompare) sum = sum + 1; //?
}
}
}
return sum;
}
function getNextValue(row, col) {
const val = board[row][col];
let liveNeighbors = getAdjacentCount(row, col, LIVE);
if (val === LIVE) {
// Any live cell with fewer than two live neighbors dies, as if caused by under-population.
if (liveNeighbors < 2) {
return DEAD;
}
// Any live cell with more than three live neighbors dies, as if by over-population..
else if (liveNeighbors > 3) {
return DEAD;
}
// Any live cell with two or three live neighbors lives on to the next generation.
return LIVE;
}
// cell is DEAD
else {
// Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
if (liveNeighbors === 3) {
return LIVE;
}
// no condition
return DEAD;
}
}
for (let row = 0; row <= maxRow; row++) {
copy[row] = [];
for (let col = 0; col <= maxCol;col++) {
copy[row][col] = board[row][col];
board[row][col] = getNextValue(row, col);
}
}
};
let isPalindrome = function(head) {
let slow = head, fast = head, val = [slow.val];
while (fast.next) {
if (fast.next.next) {
fast = fast.next.next;
slow = slow.next;
val.push(slow.val);
}
else {
fast = fast.next;
slow = slow.next;
}
}
while (slow) {
if (slow.val !== val.pop()) {
return false;
}
slow = slow.next;
}
return val.length === 0;
};
let fizzBuzz = function(n) {
let result = [];
for (let i = 1; i <= n; i++) {
if (i % 3 === 0 && i % 5 === 0) {
result.push("FizzBuzz");
}
else if (i % 3 === 0) {
result.push("Fizz");
}
else if (i % 5 === 0) {
result.push("Buzz");
}
else {
result.push('' + i);
}
}
return result;
};
let generate = function(numRows) {
if (numRows === 0) return [];
let result = [];
for (let i = 1; i <= numRows;i++) {
let row = [];
for (let j = 0; j < i; j++) {
if (j === 0 || j === i - 1) {
row[j] = 1;
}
else {
row[j] = result[i - 2][j - 1] + result[i - 2][j];
}
}
result.push(row);
}
return result;
};
let isPalindrome = function(s) {
let start = 0, end = s.length - 1, regex = /\w/i;
while (start < end) {
if (!s[start].match(regex)) {
start++;
}
else if (!s[end].match(regex)) {
end--;
}
else {
if (s[start].toLowerCase() !== s[end].toLowerCase()) return false;
start++;
end--;
}
}
return true;
}
let romanToInt = function(s) {
if (!s) return 0;
let mapping = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
let result = 0;
for (let i = s.length - 1; i >= 0;) {
if (mapping[s[i]] > mapping[s[i - 1]]) {
result += mapping[s[i]] - mapping[s[i - 1]];
i -= 2;
}
else {
result += mapping[s[i]];
i -= 1;
}
}
return result;
}
Categories
Unique Paths (Iterative)
let uniquePaths = function(m, n) {
let getKey = (row, col) => `${row}${col}`;
let cache = { }
for (let row = 1; row <= m; row++) {
for (let col = 1; col <= n; col++) {
if (row === 1) {
cache[getKey(row, col)] = 1;
}
else if (col === 1) {
cache[getKey(row, col)] = 1;
}
else {
cache[getKey(row, col)] = cache[getKey(row-1, col)] + cache[getKey(row, col - 1)];
}
}
}
return cache[getKey(m,n)];
};
Categories
Island Perimeter
let islandPerimeter = function(grid) {
if (!grid || !grid.length) return 0;
let maxRow = grid.length,
maxCol = grid[0].length,
LAND = 1, VISITED = 2;
function calculatePerimeter(row, col) {
if (grid[row][col] === LAND) {
grid[row][col] = VISITED;
let perimeter = 4;
// check above;
if (row > 0
&& (grid[row - 1][col] === LAND || grid[row - 1][col] === VISITED)) {
perimeter = perimeter - 1;
perimeter += calculatePerimeter(row - 1, col);
}
// check below;
if (row < maxRow - 1
&& (grid[row + 1][col] === LAND || grid[row + 1][col] === VISITED)) {
perimeter = perimeter - 1;
perimeter += calculatePerimeter(row + 1, col);
}
// check left;
if (col > 0
&& (grid[row][col - 1] === LAND || grid[row][col - 1] === VISITED)) {
perimeter = perimeter - 1;
perimeter += calculatePerimeter(row, col - 1);
}
// check right;
if (col < maxCol - 1
&& (grid[row][col + 1] === LAND || grid[row][col + 1] === VISITED)) {
perimeter = perimeter - 1;
perimeter += calculatePerimeter(row, col + 1);
}
return perimeter; //?
}
return 0;
}
for (let row = 0; row < maxRow; row++) {
for (let col = 0; col < maxCol;col++) {
if (grid[row][col] === LAND) {
return calculatePerimeter(row, col);
}
}
}
return 0;
};