FANG Interview Success: Learn These 5 LeetCode Algorithm Patterns

Sliding window

This technique involves creating a window of a fixed size and sliding it over an array or string while performing operations on its elements. It is useful in problems that require finding subarrays or substrings that meet certain criteria, such as the maximum sum subarray problem.

// O(n*k) solution for finding maximum sum of
// a subarray of size k
// Returns maximum sum in a subarray of size k.

function maxSum( arr, n, k){
    let max_sum = Number.MIN_VALUE;

    for (let i = 0; i < n - k + 1; i++) {
        let current_sum = 0;
        for (let j = 0; j < k; j++)
            current_sum = current_sum + arr[i + j];

        max_sum = Math.max(current_sum, max_sum);
    }

    return max_sum;
}

let arr = [ 1, 4, 2, 10, 2, 3, 1, 0, 20 ];
let k = 4;
let n = arr.length;
document.write(maxSum(arr, n, k));

List of problems on LeetCode: https://leetcode.com/tag/sliding-window/

Two-pointers

This technique involves using two-pointers that move through an array or string in a coordinated way. It is useful in problems that require finding pairs or triplets of elements that meet certain criteria, such as the two-sum problem.

//Two pointer technique based solution to find

function isPairSumExist(arr, arrLength, X)
{

    //First pointer
    var i = 0;

    //Cecond pointer
    var j = arrLength - 1;

    while (i < j) {

        // If we find a pair
        if (arr[i] + arr[j] == X)
            return true;

        // If sum of elements at current
        // pointers is less, move towards i++
        else if (arr[i] + arr[j] < X)
            i++;

        // If sum of elements at current
        // pointers is more,move towards j--
        else
            j--;
    }
    return false;
}


    var arr = [ 2, 3, 5, 8, 9, 10, 11 ];
    var val = 17;
    var arrSize =7;

    document.write(isPairSum(arr, arrSize, val));

List of problems on LeetCode: https://leetcode.com/tag/two-pointers/

Binary search

This technique involves dividing a sorted array or range of values in half at each step, discarding the half that does not contain the target value, and repeating the process until the target value is found or the range is empty. It is useful in problems that involve searching or finding a specific value in a sorted array, such as the search in a rotated sorted array problem.

function binarySearch(arr, l, r, x){
    if (r >= l) {
        let mid = l + Math.floor((r - l) / 2);

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then search left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        //Search in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }

    // Not found
    return -1;
}

List of problems on LeetCode: https://leetcode.com/tag/binary-search/

Breadth-first search

This technique involves exploring a graph or tree by visiting all the nodes at a given distance from the starting node before moving on to the nodes at the next distance. It is useful in problems that require finding the shortest path or distance between two nodes in a graph, such as a word ladder problem.

function bfsOfGraph(V, adj) {
    let bfs_traversal = [];
    let vis = [];
    for (let i = 0; i < V; i++) {
        vis.push(false);
    }
    for (let i = 0; i < V; ++i) {

        // To check if already visited
        if (!vis[i]) {
            let q = [];
            vis[i] = true;
            q.push(i);

            // BFS starting from ith node
            while (!q.empty()) {
                let g_node = q[0];
                q.shift();
                bfs_traversal.push(g_node);
                for (let j = 0; j < adj[g_node].length;
                    j++) {
                    let it = adj[g_node][j];
                    if (!vis[it]) {
                        vis[it] = true;
                        q.push(it);
                    }
                }
            }
        }
    }
    return bfs_traversal;

List of problems on LeetCode: https://leetcode.com/tag/breadth-first-search/

Depth-first search

This technique involves exploring a graph or tree by visiting as far as possible along each branch before backtracking. It is useful in problems that involve searching for a specific pattern or structure in a graph or tree, such as the maximum depth of a binary tree problem.

var inorderTraversal = function(root) {
    let result = [];
    dfs(root, result);
    return  result;

};

let dfs = (tree, result) => {
    if(tree !== null) {
        //Use tecursion for Deph-first search
        dfs(tree.left, result);
        result.push(tree.val);
        dfs(tree.right, result);
    }
}

List of problems on LeetCode: https://leetcode.com/tag/depth-first-search/

Blog

FANG Interview Success: Learn These 5 LeetCode Algorithm Patterns

Foxbuka

Sliding window

Two-pointers

Binary search

Breadth-first search

Depth-first search

Join Our Newsletter. No Spam, Only the good stuff.

Related