Leet Code Algos

binary-search.js

const search = (nums, target) => {
    let start = 0;
    let end = nums.length - 1;

    while (start <= end) {
        let mid = Math.floor((end + start) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        if (nums[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return -1;
};

minheap.js

function Heap () {
    let values = [];

    this.swap = (a, b) => {
        [values[a], values[b]] = [values[b], values[a]];
        return b;
    };

    this.push = (val) => {
        let index = values.push(val) - 1;

        while (index > 0) {
            let parent = Math.floor((index - 1) / 2);

            if (values[index] >= values[parent]) {
                break;
            }

            index = this.swap(index, parent);
        }
    };

    this.pop = () => {
        let index = this.swap(values.length - 1, 0);
        
        const result = values.pop();

        while (index * 2 + 1 < values.length) {
            const left = index * 2 + 1;
            const right = index * 2 + 2;

            const min = right < values.length && values[right] < values[left] ? right : left;

            if (values[index] <= values[min]) {
                break;
            }

            index = this.swap(index, min);
        }

        return result;
    };
};

// Test

const h = new Heap();

for (let i = 0; i < 1_000; ++i) {
    h.push(Math.floor(Math.random() * 1000));
}

let acc = -Infinity;

for (let i = 0; i < 1_000; ++i) {
    const val = h.pop();

    console.assert(val >= acc, 'pop failed');
    acc = val;
}

top-sort.js

const fill = (n, p) =>
    new Array(n).fill(0).map((_, i) => p(i));

function canFinish (n, edges) {
    const hash = fill(n, () => []);
    const incoming_edges = fill(n, () => 0);

    for (let [to, from] of edges) {
        hash[from].push(to);
        incoming_edges[to] += 1;
    }

    let count = 0;
    let stack = fill(n, (i) => i).filter(($) => incoming_edges[$] === 0);

    while (stack.length) {
        const node = stack.pop();

        for (let neighbor of hash[node]) {
            incoming_edges[neighbor] -= 1;

            if (incoming_edges[neighbor] === 0) {
                stack.push(neighbor);
            }
        }

        count += 1; // or push to the result stack
    }

    return count === n;
};

union-find.js

const solve = (n, edges, source, destination) => {
  const parent = [];
  
  for (let i = 0; i < n; ++i) {
    parent[i] = i;
  };
  
  const find = (n) =>
    parent[n] === n ? n : find(parent[n]);
  
  const union = (a, b) => {
    parent[find(a)] = find(b);
  };
  
  for (let i = 0; i < edges.length; ++i) {
    union(edges[i][0], edges[i][1]);
  };
  
  return find(source) === find(destination);
};