Tag: breadth-first-search

Categories
Breadth First Search Leetcode Recursion Trie

Search Suggestion System (Trie)

let suggestedProducts = function(products, searchWord) {
    const MAX_RESULT_COUNT = 3;
    let root = {
        children: {}
    };

    function addToNode(word, index, node) {
        if (index >= word.length) {
            node.end = true;
            return;
        }
        //
        const child = node.children[word[index]];
        if (child) {
            addToNode(word, index + 1, child);
        }
        else {
            let child = {val: word[index], parent: node, children: {}};
            node.children[word[index]] = child;
            addToNode(word, index + 1, child);
        }
    }

    function getWord(leaf) {
        let node = leaf;
        let str = '';
        while (node) {
            if (node.val) str = node.val + str; //?
            node = node.parent; //?
        }

        return str; //?
    }

    function searchProducts(searchString) {

        let words = [];
        let nodes = [...Object.entries(root.children)], len = searchString.length;
        while (nodes.length) {

            let currentNodeLength = nodes.length;
            while (currentNodeLength > 0) {
                currentNodeLength--;

                const node = nodes.pop();
                const [key, val] = node;
                if (len > 0 && key === searchString[searchString.length - len]) {
                    nodes.unshift(...Object.entries(val.children));

                    if (len === 1 && val.end) {
                        words.push(getWord(val));
                    }
                } else if (len <= 0) {
                    if (val.end) words.push(getWord(val));
                    nodes.unshift(...Object.entries(val.children));
                }
            }
            len--;
        }

        return words.sort().slice(0, Math.min(MAX_RESULT_COUNT, words.length));
    }

    for(let product of products) {
        addToNode(product, 0, root);
    }


    let result = [];
    for (let i = 0; i < searchWord.length; i++) {
        result.push(searchProducts(searchWord.substring(0, i + 1))); //?
    }

    return result; //?
};
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
Binary Tree Breadth First Search

Level Order ZigZag Traversal

function levelOrderZigzag(root) {

    let queue = [root], result = [], direction = 0;
    function process(node) {
        result.push(node.val); //?
    }

    while (queue.length) {
        let level = [];
        while(queue.length) {
            const node = queue.pop();
            process(node);
            if (direction === 0) {
                if (node.left) level.push(node.left);
                if (node.right) level.push(node.right);
            }
            else {
                if (node.right) level.push(node.right);
                if (node.left) level.push(node.left);
            }
        }
        direction ^= 1;
        queue = level;
    }

    return result; //?
}
Categories
Binary Tree Breadth First Search

Level Order Tree Traversal

function levelOrder(root) {

    let queue = [root], result = [];
    function process(node) {
        result.push(node.val);
    }

    while (queue.length) {
        const node = queue.pop();
        process(node);
        if (node.left) queue.unshift(node.left);
        if (node.right) queue.unshift(node.right);
    }

    return result; //?
}
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;
}