Categories
Binary Tree Depth First Search Leetcode Recursion

Path Sum I

let hasPathSum = function(root, sum) {

if (!root) return false;
if (sum - root.val === 0 && !root.left && !root.right) return true;

return hasPathSum(root.left, sum - root.val)
|| hasPathSum(root.right, sum - root.val);
};
Categories
Depth First Search Leetcode Recursion

Minesweeper

let updateBoard = function(board, click) {

    let maxRow = board.length,
        maxCol = board[0].length,
        MINE = 'M',
        BLANK = 'B',
        EMPTY = 'E',
        GAMEOVER = 'X';

    function isMine(row, col) {
        if (row < 0 || col < 0 || row >= maxRow || col >= maxCol) {
            return 0;
        }
        return board[row][col] === MINE ? 1 : 0;
    }

    function getMineCount(row, col) {
        let nearbyMines = 0;
        nearbyMines += isMine(row - 1, col - 1); // top left
        nearbyMines += isMine(row - 1, col); // top
        nearbyMines += isMine(row - 1, col + 1); // top right
        nearbyMines += isMine(row, col - 1); // left
        nearbyMines += isMine(row, col + 1); // right
        nearbyMines += isMine(row + 1, col - 1); // bottom left
        nearbyMines += isMine(row + 1, col); // bottom
        nearbyMines += isMine(row + 1, col + 1); // bottom right
        return nearbyMines;
    }

    function markAndExplore(row, col) {
        if (row < 0 || col < 0 || row >= maxRow || col >= maxCol) {
            return;
        }
        const data = board[row][col];
        if (data === EMPTY) {

            const mineCount = getMineCount(row, col);
            board[row][col] = mineCount > 0 ? `${mineCount}` : BLANK;

            if (mineCount === 0) {
                markAndExplore(row - 1, col - 1); // top left
                markAndExplore(row - 1, col); // top
                markAndExplore(row - 1, col + 1); // top right
                markAndExplore(row, col - 1); // left
                markAndExplore(row, col + 1); // right
                markAndExplore(row + 1, col - 1); // bottom left
                markAndExplore(row + 1, col); // bottom
                markAndExplore(row + 1, col + 1); // bottom right
            }
        }
    }

    let [x, y] = click;
    if (board[x][y] === MINE) {
        board[x][y] = GAMEOVER;
    }
    else {
        markAndExplore(x, y);
    }

    return board;
};
Categories
Depth First Search Leetcode Loop Recursion

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;

};
Categories
Depth First Search Leetcode Recursion

Max Area of Island

let maxAreaOfIsland = function(grid) {

if (!grid || !grid.length) return 0;

let max = 0,
maxRow = grid.length,
maxCol = grid[0].length,
LAND = 1, VISITED = 2;

function markAndGetTotal(row, col) {
if (row < 0 || row >= maxRow || col < 0 || col >= maxCol) return 0;
if (grid[row][col] === LAND) {
grid[row][col] = VISITED;

let result = 1;
// top
result += markAndGetTotal(row - 1, col);
// bottom
result += markAndGetTotal(row + 1, col);
// left
result += markAndGetTotal(row, col - 1);
/// right
result += markAndGetTotal(row, col + 1);
return result;
}
return 0;
}

for (let row = 0; row < maxRow;row++) {
for (let col = 0; col < maxCol;col++) {
if (grid[row][col] === LAND) {
const total = markAndGetTotal(row, col); //?
max = Math.max(total, max);
}
}
}

return max;
};
Categories
Array Leetcode Loop

Two Sum Less Than K

let twoSumLessThanK = function(A, K) {
let max = -1, start = 0, end = A.length - 1;
A.sort((a, b) => b - a); //?

while (start < end) {
let sum = A[start] + A[end];
if (sum < K) {
max = Math.max(sum, max);
end--;
}
else {
start++;
}
}

return max;
};
Categories
Depth First Search Leetcode Loop Matrix Recursion

Number Of Distinct Islands

if (!grid || !grid.length) return 0;

let numRows = grid.length,
numCols = grid[0].length,
LAND = 1, VISITED = 2;

function markAndVisit(row, col, island = [], level = 0) {
if (grid[row][col] === LAND) {
grid[row][col] = VISITED;
island.push('X' + level);

// up
if (row > 0 && grid[row - 1][col] === LAND) {
island.push('U' + level);
markAndVisit(row - 1, col, island, level + 1);
}

// down
if (row < numRows - 1 && grid[row + 1][col] === LAND) {
island.push('D' + level);
markAndVisit(row + 1, col, island, level + 1);
}

// left
if (col > 0 && grid[row][col - 1] === LAND) {
island.push('L' + level);
markAndVisit(row, col - 1, island, level + 1);
}

// right
if (col < numCols - 1 && grid && grid[row][col + 1] === LAND) {
island.push('R' + level);
markAndVisit(row, col + 1, island, level + 1);
}
}

return island;
}

let islands = new Set();
for (let row = 0; row < numRows;row++) {
for (let col = 0; col < numCols;col++) {
if (grid[row][col] === LAND) {
let island = markAndVisit(row, col);
// console.log(island);
if (island.length) islands.add(island.join(''));
}
}
}

// console.table(grid);
return islands.size;
Categories
Array Leetcode Loop String

Reorganize String

let reorganizeString = function(S) {
let chars = {}, max = 0;
for(let i = 0; i < S.length;i++) {
if (chars[S[i]]) {
chars[S[i]] = chars[S[i]] + 1;
max = Math.max(chars[S[i]], max);
}
else {
chars[S[i]] = 1;
}
}

console.log(max, Math.floor((S.length + 1) / 2));
if (max > (S.length + 1) / 2) {
return "";
}

let result = [], index = 0;
const keys = Object.keys(chars).sort((a, b) => chars[b] - chars[a]); //?
while (keys.length) { //?
const key = keys.shift(); //?
result[index] = key;

if (chars[key] - 1 > 0) {
chars[key] = chars[key] - 1;
keys.unshift(key); //?
}

index += 2; //?
if (index >= S.length) {
index = 1;
}
}

return result.join('');
};
Categories
Array Leetcode Loop

Prison After N Days

let  prisonAfterNDays = function(cells, N) {

let cache = {},
counter = 1,
cycle = false,
len = 8;
let dup = [...cells];

function getNextCycle(data) {
let lastCycle = data[1];
let cycleDays = counter - lastCycle;
console.log(lastCycle, cycleDays);
let nextCycle = N - ((N - lastCycle) % cycleDays); //?.
// let nextCycle = counter; //?
// while (nextCycle + counter < N) {
// nextCycle = nextCycle += cycleDays;
// }

return nextCycle; //?
}

while(counter <= N) {
let key = dup.join(''),
data = cache[key],
row = [];

if (data && !cycle) {
cycle = true;
counter = getNextCycle(data);
}

if (data) {
dup = data[0];
counter++; //?
}
else {
for (let i = 0; i < len; i++) {
row[i] = dup[i - 1] === dup[i + 1] ? 1 : 0;
}
cache[key] = [[...row], counter];
dup = cache[key][0];
counter++; //?
}
}

return dup;
};
Categories
Array Leetcode Loop Sort

Most Visited Website Pattern

let mostVisitedPattern = function(username, timestamp, website) {
    let map = new Map();
    for (let i = 0; i < username.length; i++) {
        if (map.has(username[i])) {
            map.get(username[i]).push([website[i], timestamp[i]]);
        }
        else {
            map.set(username[i], [[website[i], timestamp[i]]]);
        }
    }

    // get all possibilites
    let visitedPattern = {};
    let possibilityMap = new Map();
    for(let [user, visits] of map.entries()) {
        visitedPattern[user] = {};
        const value = visits.sort((a, b) => a[1] - b[1]).map(([a]) => a);

        if ( value.length < 3) continue;
        for (let i = 0; i < value.length - 2; i++) {
            for (let j = i + 1; j < value.length - 1; j++) {
                for (let k = j + 1; k < value.length; k++) {
                    let key = `${value[i]},${value[j]},${value[k]}`;
                    if(possibilityMap.has(key)) {
                        if(!visitedPattern[user][key]) {
                            possibilityMap.set(key, possibilityMap.get(key) + 1);
                            visitedPattern[user][key] = 1;
                        }
                    }
                    else {
                        possibilityMap.set(key, 1);
                        visitedPattern[user][key] = 1;
                    }
                }
            }
        }
    }

    const result = [...possibilityMap];
    return result.sort((a, b) => {
        if(a[1] < b[1]) {
            return 1;
        }
        else if (a[1] > b[1]) {
            return -1;
        }
        return a[0].localeCompare(b[0]);
    }).map(arr => arr[0]).shift().split(','); //?


    // result.pop(); //?
        // .map(arr => arr[0]).pop().split('|'); //?
};
Categories
Binary Tree Leetcode Recursion

Is Subtree

let isSubtree = function(mainTree, subTree) {

function isSame(left, right) {
if (left === right) return true;
if (left === null && right !== null) return false;
if (left !== null && right === null) return false;
if (left.val !== right.val) return false;
return isSame(left.left, right.left)
&& isSame(left.right, right.right);
}

if (mainTree === subTree) return true;
if (!mainTree) return false;
if (isSame(mainTree, subTree)) return true;

return isSubtree(mainTree.left, subTree) || isSubtree(mainTree.right, subTree);
};