Categories
Algorithms Javascript

Longest Common Substring in JS

Use the following javascript code to find the longest substring (unconnected) among two strings:

const minDistance = function (text1, text2) {
	const m = text1.length,
		n = text2.length,
		dp = new Array(m + 1).fill().map((v) => new Array(n + 1).fill(0));
	for (let i = 1; i <= m; i++)
		for (let j = 1; j <= n; j++)
			if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);

	return m + n - 2 * dp[m][n];
};
Categories
Algorithms Javascript

Dijkstra Algorithm in JS

const networkDelayTime = function (times, n, src) {
	const adjacencyList = new Map();

	for (let [start, end, cost] of times) {
		adjacencyList.set(
			start,
			(adjacencyList.get(start) || []).concat([[end, cost]])
		);
	}
	const queue = new MinPriorityQueue({
		compare: (a, b) => a[0] > b[0],
	});
	queue.enqueue([0, src]); // cost, start
	const visited = new Map();
	while (queue.size()) {
		const [cost, node] = queue.dequeue();
		if (visited.has(node)) continue;
		visited.set(node, cost);
		// if (city === dst) return cost;
		if (!adjacencyList.has(node)) continue;
		for (const [nextNode, nextCost] of adjacencyList.get(node)) {
			if (visited.has(nextNode) || visited.get(nextNode) >= cost)
				continue;
			queue.enqueue([cost + nextCost, nextNode]);
		}
	}
	return visited.size == n ? Math.max(...visited.values()) : -1;
};

T: O(N+ElogN)

S: O(N+E)

Categories
Algorithms Javascript

BST Iterative Preorder Traversal in JS

function preorder(root) {
	const stack = [];
	while (stack.length || root) {
		while (root) {
			stack.push(root);
			root = root.left;
		}
		root = stack.pop();
		console.log(root.val);
		root = root.right;
	}
};
Categories
Algorithms Javascript

Topological Sort in JS

Imagine you have a list of dependencies and prerequisites that form a graph. You can use topological sort graph algorithm in order to validate meeting all the requirements. Here is a BFS implementation of this algorithm in Javascript:

const canFinish = function (numCourses, prerequisites) {
	const rank = new Array(numCourses).fill(0),
		// rank["C" => 0, "OOP" = 1, "DS" = 1] -> how many dependencies
		dependent = new Array(numCourses).fill().map((v) => []);
		// dependent["C"] = ["OOP", "DS"];
	for (const [a, b] of prerequisites) {
		rank[a]++;
		dependent[b].push(a);
	}
	const queue = [];
	for (const i in rank) if (rank[i] == 0) queue.push(i);
	while (queue.length) {
		const node = queue.shift();
		for (const neighbour of dependent[node]) {
			rank[neighbour]--;
			if (rank[neighbour] == 0) queue.push(neighbour);
		}
	}
	return rank.every((v) => !Boolean(v));
};
Categories
Algorithms Javascript

Union Find in JS

Union Find is an algorithm that can be used to find disjoint sets, and cycles in a graph. Below are two implementations of this algorithm.

  1. Un-optimized
class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false; // Cycle
		this.root[u] = v;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

2. Optimized (Ranked)

class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
		this.rank = new Array(n).fill(1);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false;
		if (this.rank[u] > this.rank[v]) {
			this.root[v] = u;
			this.rank[u] += this.rank[v];
		} else {
			this.root[u] = v;
			this.rank[v] += this.rank[u];
		}
		return true;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}