Templates

backtracking1.js

function dfs(startIndex, path, res, [...additional states]) {
    if (isLeaf(path)) {
        res.push(new Array(path));
        return;
    }
    for (const edge of getEdges(startIndex, [...additional states])) {
        path.push(choice);
        if (...additionl statees) update(...additional states)
        dfs(startIndex + edge.length, path, res, [...addtional states]);
        path.pop();
        // revert(...additional states) if necessary, e.g. permutations
    }
}

backtracking2.js

function dfs(startIndex, target) {
    if (isLeaf(startIndex)) {
        return 1
    }
    int ans = initialValue;
    for (const edge of getEdges(startIndex, [...additional states])) {
        if (additional states) {
            update([...additional states]);
        }
        ans = aggregate(ans, dfs(startIndex + edge.length(), [...additional states])
        if (additional states) {
            revert([...additional states]);
        }
    }
    return ans;
}

bfs_graph.js

function bfs(root) {
    let queue = [root];
    let visited = new Set([root]);
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of get_neighbors(node)) {
            if (visited.has(neighbor)) continue;
            queue.push(neighbor);
            visited.add(neighbor);
        }
    }
}

bfs_matrix.js

num_rows = grid.length;
num_cols = grid[0].length;

function get_neighbors(coord) {
    const [row, col] = coord;
    const delta_row = [-1, 0, 1, 0];
    const delta_col = [0, 1, 0, -1];
    const res = [];
    for (let i = 0; i < delta_row.length; i++) {
        neighbor_row = row + delta_row[i];
        neighbor_col = col + delta_col[i];
        if (0 <= neighbor_row && neighbor_row < num_rows &&
          0 <= neighbor_col && neighbor_col < num_cols) {
              res.push([neighbor_row, neighbor_col]);
          }
    }
    return res;
}

function bfs(starting_node) {
    const queue = [starting_node];
    const visited = new Set([starting_node]);
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of get_neighbors(node)) {
            if (visited.has(neighbor)) continue;
            // Do stuff with the node if required
            // ...
            queue.push(neighbor);
            visited.add(neighbor);
        }
    }
}

bfs_matrix.js.js

num_rows = grid.length;
num_cols = grid[0].length;

function get_neighbors(coord) {
    const [row, col] = coord;
    const delta_row = [-1, 0, 1, 0];
    const delta_col = [0, 1, 0, -1];
    const res = [];
    for (let i = 0; i < delta_row.length; i++) {
        neighbor_row = row + delta_row[i];
        neighbor_col = col + delta_col[i];
        if (0 <= neighbor_row && neighbor_row < num_rows &&
          0 <= neighbor_col && neighbor_col < num_cols) {
              res.push([neighbor_row, neighbor_col]);
          }
    }
    return res;
}

function bfs(starting_node) {
    const queue = [starting_node];
    const visited = new Set([starting_node]);
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of get_neighbors(node)) {
            if (visited.has(neighbor)) continue;
            // Do stuff with the node if required
            // ...
            queue.push(neighbor);
            visited.add(neighbor);
        }
    }
}

bfs_tree.js

function bfs(root) {
    let queue = [root];
    while (queue.length > 0) {
        const node = queue.shift();
        for (const child of node.children) {
            if (isGoal(child)) {
                return FOUND(child);
            }
            queue.push(child);
        }
    }
    return NOT_FOUND;
}

binarySearch.js

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let first_true_index = -1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (feasible(mid)) {
            first_true_index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return first_true_index;
}

dfs_graph.js

function dfs(root, visited) {
    for (const neighbor of get_neighbors(root)) {
        if (visited.has(neighbor)) continue;
        visited.add(neighbor);
        dfs(neighbor, visited);
    }
}

dfs_tree.js

function dfs(root, target) {
    if (!root) return null;
    if (root.val == target) return root;
    left = dfs(root.left);
    if (left != null) return left;
    right = dfs(root.right);
    return right;
}

hash.js

let SmallestInfiniteSet = function() {
    this.isPresent = new HashSet();
    this.addedIntegers = new MinHeapPQ();
    this.currentInteger = 1;
};

SmallestInfiniteSet.prototype.popSmallest = function() {
    // If there are numbers in the min-heap, 
    // top element is lowest among all the available numbers.
    if (!this.addedIntegers.isEmpty()) {
        answer = this.addedIntegers.popMin();
        this.isPresent.remove(answer);
    }
    // Otherwise, the smallest number of large positive set 
    // denoted by 'current_integer' is the answer.
    else {
        answer = this.currentInteger;
        this.currentInteger += 1;
    }
    return answer;
};

SmallestInfiniteSet.prototype.addBack = function(num) {
    if (this.currentInteger <= num || this.isPresent.contains(num)) {
        return;
    }
    // We push 'num' in the min-heap if it isn't already present.
    this.addedIntegers.insert(num);
    this.isPresent.add(num);
};


// === MIN HEAP PRIORITY QUEUE CLASS === //
class MinHeapPQ {
    constructor() {
        this.heap = [];
    }

    // Helper methods to get parent, left and right child indices
    getParentIndex(index) {
        return Math.floor((index - 1) / 2);
    }
    getLeftChildIndex(index) {
        return 2 * index + 1;
    }
    getRightChildIndex(index) {
        return 2 * index + 2;
    }
    
    // Helper method to swap two elements in the heap
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // Helper method to get the minimum element in the heap
    peek() {
        if (this.heap.length === 0) {
            throw new Error("Heap is empty");
        }
        return this.heap[0];
    }

    // Helper method to insert an element into the heap
    insert(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = this.getParentIndex(currentIndex);
        while (currentIndex > 0 && this.heap[currentIndex] < this.heap[parentIndex]) {
            this.swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = this.getParentIndex(currentIndex);
        }
    }

    // Helper method to remove the minimum element from the heap
    popMin() {
        if (this.heap.length === 0) {
            throw new Error("Heap is empty");
        }
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            let currentIndex = 0;
            let leftChildIndex = this.getLeftChildIndex(currentIndex);
            let rightChildIndex = this.getRightChildIndex(currentIndex);
            while (
                (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[currentIndex]) || 
                (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[currentIndex])
            ) {
                const smallerChildIndex = (rightChildIndex >= this.heap.length || 
                    this.heap[leftChildIndex] < this.heap[rightChildIndex]) ? leftChildIndex : rightChildIndex;

                this.swap(currentIndex, smallerChildIndex);
                currentIndex = smallerChildIndex;
                leftChildIndex = this.getLeftChildIndex(currentIndex);
                rightChildIndex = this.getRightChildIndex(currentIndex);
            }
        }
        return min;
    }

    // Helper method to get the size of the heap
    size() {
        return this.heap.length;
    }
    // Helper method to check if the heap is empty
    isEmpty() {
        return this.heap.length === 0;
    }
}


// === HASH SET CLASS === //
class HashSet {
  constructor() {
    this.hash = {};
    this.size = 0;
  }

  add(value) {
    if (!this.contains(value)) {
      this.hash[value] = true;
      this.size++;
    }
  }

  remove(value) {
    if (this.contains(value)) {
      delete this.hash[value];
      this.size--;
    }
  }

  contains(value) {
    return this.hash.hasOwnProperty(value);
  }

  getSize() {
    return this.size;
  }

  isEmpty() {
    return this.size === 0;
  }

  clear() {
    this.hash = {};
    this.size = 0;
  }
}

monoStack.js

function monoStack(insertEntries) {
    const stack = [];
    for (let entry of insertEntries) {
        while (stack.length > 0 && stack[stack.length - 1] <= entry) {
            stack.pop();
            // Do something with the popped item here
        }
        stack.push(entry);
    }
}

slidingWindowFixed.js

function slidingWindowFixed(input, windowSize) {
    var ans = window = input[0..windowSize);
    for (var right = windowSize; right < input.length; ++right) {
        const left = right - windowSize;
        remove input[left] from window
        append input[right] to window
        ans = optimal(ans, window);
    }
    return ans;
}

slidingWindowFlexibleLonge.jsst

function slidingWindowFlexibleLongest(input) {
    initialize window, ans
    var left = 0;
    for (var right = 0; right < input.length; ++right) {
        append input[right] to window
        while (invalid(window)) {
            remove input[left] from window
            ++left;
        }
        ans = Math.max(ans, window);       // window is guaranteed to be valid here
    }
    return ans;
}

slidingWindowFlexibleShortest.js

function slidingWindowFlexibleShortest(input) {
    initialize window, ans
    var left = 0;
    for (var right = 0; right < input.length; ++right) {
        append input[right] to window
        while (valid(window)) {
            ans = Math.min(ans, window);   // window is guaranteed to be valid here
            remove input[left] from window
            ++left;
        }
    }
    return ans;
}

topoSort.js

function findInDegree(graph) {
    const inDegree = new Map();
    for (let node of graph.keys()) {
        inDegree.set(node, 0);
    }
    for (let node of graph.keys()) {
        for (neighbor of graph.get(node)) {
            inDegree.set(node, neighbor.get(node) + 1);
        }
    }
    return inDegree;
}

function topoSort(graph) {
    const res = [];
    const q = [];
    const inDegree = findInDegree(graph);
    for (let node of inDegree.keys()) {
        if (inDegree.get(node) == 0) {
            q.push(node);
        }
    }
    while (q.length > 0) {
        const node = q.shift();
        res.push(node);
        for (let neighbor of graph.get(node)) {
            inDegree.set(neighbor, inDegree.get(neighbor) - 1);
            if (inDegree.get(neighbor) == 0) {
                q.push(neighbor);
            }
        }
    }
    return (graph.size === res.length) ? res : null;
}

Trie.js

class Node {
    constructor(value) {
        this.value = value;
        this.children = new Map();
    }

    insert(s, idx) {
        // idx: index of the current character in s
        if (idx !== s.length) {
            if (this.children.has(s.charAt(idx))) {
                this.children.get(s.charAt(idx)).insert(s, idx + 1);
            } else {
                this.children.set(s.charAt(idx), new Node(s.charAt(idx)));
                this.children.get(s.charAt(idx)).insert(s, idx + 1);
            }
        }
    }
}

UnionFind.js

class UnionFind {
    constructor() {
        this.id = new Map();
    }

    find(x) {
        let y = this.id.has(x) ? this.id.get(x) : x;
        if (y != x) {
            y = this.find(y);
            this.id.set(x, y);
        }
        return y;
    }

    union(x, y) {
        this.id.set(this.find(x), this.find(y));
    }
}