Tag: recursion

Categories
Array Binary Search Leetcode Recursion

Search Matrix

let searchMatrix = function(matrix, target) {
    if(!matrix.length) return false;

    function search(startRow, endRow, startCol, endCol) {
        console.log(startRow, endRow, startCol, endCol);
        let midRow = Math.floor((startRow + endRow) / 2); //?
        let midCol = Math.floor((startCol + endCol) / 2); //?


        if (startRow < endRow && startCol < endCol) {
            const midValue = matrix[midRow][midCol]; //?
            if(midValue === target) {
                return true;
            }
            if (midValue < target) {
                return search(midRow + 1, endRow, startCol, endCol)
                        || search(startRow, endRow, midCol + 1, endCol);
            }
            else {
                return search(startRow, midRow, startCol, endCol)
                    || search(startRow, endRow, startCol, midCol);
            }
        }

        return false;
    }

    return search(0, matrix.length, 0, matrix[0].length);
};
Categories
Breadth First Search Leetcode Recursion

Oranges Rotting

let orangesRotting = function(grid) {

    const FRESH = 1,
          ROTTEN = 2,
          VISITED = -1;
    let rotten = [],
        totalFresh = 0,
        totalEmpty = 0,
        total = 0;

    function getAdjacents(row, col) {
        let result = [];
        // check top
        if (row > 0 && grid[row -1][col] === FRESH) {
            grid[row -1][col] = VISITED;
            result.push([row - 1, col]);
        }

        // check bottom
        if (row < grid.length - 1 && grid[row + 1][col] === FRESH) {
            grid[row +1][col] = VISITED;
            result.push([row + 1, col]);
        }

        // check left;
        if (col > 0 && grid[row][col - 1] === FRESH) {
            grid[row][col - 1] = VISITED;
            result.push([row, col - 1]);
        }

        // check right
        if (col < grid[row].length - 1 && grid[row][col + 1] === FRESH) {
            grid[row][col + 1] = VISITED;
            result.push([row, col + 1]);
        }

        return result;
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            const data = grid[i][j];
            if (data === ROTTEN) {
                rotten.push(...getAdjacents(i, j));
            }
            else if (data === FRESH || data === VISITED) {
                totalFresh++;
            }
            else {
                totalEmpty++;
            }
            total++;
        }
    }

    totalFresh -= rotten.length;
    let minute = 0;
    while (rotten.length) {
        let len = rotten.length;
        while (len --> 0) {
            let point = rotten.pop();
            let [row, col] = point;
            grid[row][col] = ROTTEN;
            rotten.unshift(...getAdjacents(row, col));
        }

        totalFresh -= rotten.length;
        minute++;
    }

    if (total === totalEmpty) return 0;

    let hasFreshOranges = totalFresh > 0;
    if (hasFreshOranges) return -1;

    return minute;
};
Categories
Leetcode Parenthesis Recursion String

Decode String

let decodeString = function(str) {

    if (str.indexOf("[") < 0) {
        return str;
    }

    let openingIndex = [];
    let newStr = "";
    for (let i = 0; i < str.length; i++) {
        if (str[i] === "[") {
            openingIndex.push(i);
            newStr += str[i];
        }
        else if (str[i] === "]") {
            let opening = openingIndex.pop();
            let allMultipliers = str.substring(0, opening).match(/\d+/g);
            let multiplier = allMultipliers[allMultipliers.length - 1];
            let data = str.substring(opening + 1, i);
            if (data.indexOf("[") < 0) {
                newStr = newStr.substring(0, newStr.lastIndexOf("[") - multiplier.length) + data.repeat(multiplier);
                console.log({opening, multiplier, data, newStr});
            }
            else {
                newStr += str[i];
            }
        }
        else {
            newStr += str[i];
        }
    }

    return decodeString(newStr);
};
Categories
Leetcode Recursion

Reverse LinkedList (Recursion)

let reverseLinkedList = function(root, reverse = new ListNode(0)) {
    if (root) {
        let toAdd = root;
        let next = root.next;

        let reversedNext = reverse.next;
        toAdd.next = reversedNext;
        reverse.next = toAdd;

        reverseLinkedList(next, reverse);
    }
    return reverse.next;
}
Categories
Leetcode Recursion String

Look and Say

let lookAndSay = function(nth, number = "1") {
    if (nth === 1) return number;

    let index = 0,
        counter = 1,
        currentNumber = "";

    let result = "";
    while (index < number.length) {
        if (index === 0) {
            currentNumber = number[index];
        }
        else if (currentNumber === number[index]) {
            counter++;
        }
        else if (currentNumber !== number[index]) {
            result = `${result}${counter}${currentNumber}`;//?
            counter = 1;
            currentNumber = number[index];
        }

        index++;
    }

    result = `${result}${counter}${currentNumber}`;//?

    return lookAndSay(--nth, result);
}
Categories
Recursion Sort

Merge Sort

let mergeSort = function(numbers) {

    function mergeSort(arr) {
        if (arr.length === 1) return arr;
        let center = Math.floor(arr.length / 2);
        let left = arr.slice(0, center);
        let right = arr.slice(center);
        return merge(mergeSort(left), mergeSort(right));
    }
    
    function merge(left, right) {
        let results = [];
        while (left.length && right.length) {
            if (left[0] < right[0]) {
                results.push(left.shift());
            }
            else {
                results.push(right.shift());
            }
        }

        return [...results, ...left, ...right];
    }

    return mergeSort(numbers);
}
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

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;
};