Month: May 2020

Categories
Breadth First Search Leetcode Recursion

Number of Islands

let numIslands = function(matrix) {

    if (!matrix.length) return 0;

    let land = 1, visited = 'X',
        counter = 0,
        maxRow = matrix.length - 1,
        maxCol = matrix[0].length - 1;

    function exploreAndMark(row, col) {
        if (row < 0 || col < 0 || row > maxRow || col > maxCol) {
            return;
        }

        if (matrix[row][col] === land) {
            matrix[row][col] = visited;

            // explore up
            exploreAndMark(row - 1, col);

            // explore down
            exploreAndMark(row + 1, col);

            // explore left
            exploreAndMark(row, col - 1);

            // explore right
            exploreAndMark(row, col + 1);
        }
    }

    for (let row = 0; row <= maxRow; row++) {
        for (let col = 0; col <= maxCol; col++) {
            if (matrix[row][col] === land) {
                counter++;
                exploreAndMark(row, col);
            }
        }
    }

    return counter;
}
Categories
Binary Search Recursion

Second highest number between two arrays

let secondHighest = function(arr1, arr2) {

    if (arr1.length === 1 && arr2.length === 1) {
        return Math.min(arr1[0], arr2[0]);
    }
    else if (arr1.length === 0 && arr2.length === 2) {
        return Math.min(arr2[0], arr2[1]);
    }
    else if (arr2.length === 0 && arr1.length === 2) {
        return Math.min(arr1[0], arr1[1]);
    }

    let mid1 = Math.ceil((arr1.length / 2) - 1)
    let mid2 = Math.ceil((arr2.length / 2) - 1);

    if (arr1[mid1] <= arr2[mid2]) {

        arr1 = arr1.slice(mid1 + 1);
        arr2 = arr2.slice(mid2);
    }
    else {
        arr1 = arr1.slice(mid1);
        arr2 = arr2.slice(mid2 + 1);
    }

    return secondHighest(arr1, arr2);
}
Categories
Leetcode

Two Sum

function twoSum(nums, target) {
    let result = [],
        cache = {};
    for (let i = 0; i < nums.length; i++) {
        let x = target - nums[i];
        if (cache[x] !== undefined) {
            result.push([cache[x], i]);
        }
        cache[nums[i]] = i;
    }

    return result;
};
Categories
Leetcode Parenthesis String

Valid Parenthesis

function validParenthesis(str) {

    let closingMap = {
        ')' : '(',
        ']' : '[',
        '}' : '{'
    }

    let chars = [];
    for(let i = 0; i < str.length; i++) {
        if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
            chars.push(str[i]);
        }
        else {
            let compare = chars.pop();
            if (closingMap[str[i]] !== compare) return false;
        }
    }
    return chars.length === 0;
}
Categories
Binary Search Recursion

Binary Search

function binarySearch(arr, n, start = 0, end = arr.length) {
    let mid = Math.floor((end + start) / 2);
    if (arr[mid] === n) return mid;

    if (start < end - 1) {
        if (n > arr[mid]) {
            return binarySearch(arr, n, mid, end);
        } else {
            return binarySearch(arr, n, start, mid);
        }
    }
    return -1;
}
Categories
Binary Tree Leetcode Recursion

Is Same Tree

let isSameTree = function(p, q) {

    if (p === q) return true;
    if (p?.val !== q?.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
Categories
Binary Tree Leetcode Recursion

Invert a Binary Tree

let invertTree = function(root) {

    if (root) {
        const right = root.right;
        root.right = invertTree(root.left)
        root.left = invertTree(right)
        return root;
    }
    return null;
};