Skip to main content
FREE Mock interview & resume review with Sumit. Free right now, no payment needed.Book a slot

JioCoder 450 DSA Concepts, Part 2: Sliding Window to KMP (Phases 10–18)

Concept lessons for Phases 10 to 18 of the JioCoder 450 DSA roadmap: sliding window, heaps, trees, graphs, DSU, DP, tries and string matching, with JavaScript code.

Sumit KumarUpdated Oct 22, 202624 min readDSA
JioCoder 450 DSA Concepts, Part 2: Sliding Window to KMP (Phases 10–18)

This is Part 2 of the concept lessons for the JioCoder 450 DSA Roadmap. It covers Phases 10 to 18. Each lesson explains the idea, the key points to remember, its time complexity and a JavaScript implementation. The numbers match the question numbers in the roadmap checklist.

Phase 10: Sliding Window & Two Pointers#

230. Longest Substring Without Repeating Characters#

This is the classic sliding window. Keep a window [l, r] that is always valid. Expand r one step at a time; when the window becomes invalid, move l forward until it's valid again.

  • Template: for each r, add s[r]; while invalid, remove s[l] and l++; update the answer with r - l + 1.
  • Both pointers only move forward, so the total work is O(n).
  • Here 'invalid' means a character repeats. Store the last index of each character to jump l directly.
  • For 'count subarrays with exactly K', compute atMost(K) - atMost(K - 1).

Complexity: Time O(n) · Space O(alphabet)

JavaScript
function lengthOfLongestSubstring(s) {
  const last = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    if (last.has(s[r]) && last.get(s[r]) >= l) l = last.get(s[r]) + 1;
    last.set(s[r], r);
    best = Math.max(best, r - l + 1);
  }
  return best;
}

Phase 11: Heaps#

242. Introduction to Priority Queues using Binary Heaps#

A priority queue always gives you the smallest (min-heap) or largest (max-heap) element first. It's usually built as a binary heap: a complete binary tree stored in an array.

  • For index i: left child 2i + 1, right child 2i + 2, parent ⌊(i - 1) / 2⌋.
  • Heap property: every parent is ≤ its children (min-heap) or ≥ (max-heap). Only the root is guaranteed to be the min/max.
  • Peek the top in O(1); push and pop in O(log n). Building a heap from an array takes O(n).
  • Use it for top-K problems, merging sorted lists, Dijkstra and running medians.

Complexity: Peek O(1) · Push/Pop O(log n) · Build O(n)

JavaScript
// heap stored as an array
const heap = [1, 3, 5, 7, 9, 8];
const parent = i => (i - 1) >> 1;
const left = i => 2 * i + 1, right = i => 2 * i + 2;
console.log(heap[0]); // min element

243. Min Heap and Max Heap Implementation#

Push adds the element at the end and 'bubbles it up' while it's smaller than its parent. Pop moves the last element to the root and 'sinks it down' toward the smaller child.

  • For a max-heap, flip the comparisons (or store negative values in a min-heap).
  • JavaScript has no built-in heap, so keep this class handy for interviews.

Complexity: Push/Pop O(log n)

JavaScript
class MinHeap {
  constructor() { this.h = []; }
  push(x) {
    const h = this.h; h.push(x);
    let i = h.length - 1;
    while (i > 0 && h[(i - 1) >> 1] > h[i]) { [h[i], h[(i - 1) >> 1]] = [h[(i - 1) >> 1], h[i]]; i = (i - 1) >> 1; }
  }
  pop() {
    const h = this.h, top = h[0], last = h.pop();
    if (h.length) {
      h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2 * i + 1, r = l + 1;
        if (l < h.length && h[l] < h[s]) s = l;
        if (r < h.length && h[r] < h[s]) s = r;
        if (s === i) break;
        [h[i], h[s]] = [h[s], h[i]]; i = s;
      }
    }
    return top;
  }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
}

Phase 13: Binary Trees#

275. Introduction to Trees#

A tree is a hierarchy of nodes connected by edges, with one root and no cycles. In a binary tree, each node has at most two children: left and right.

  • Terms: root (top), leaf (no children), height (longest root-to-leaf path), depth (distance from root), subtree.
  • Full binary tree: every node has 0 or 2 children. Complete: all levels full except possibly the last, filled left to right. Perfect: all levels completely full. Balanced: height is O(log n).
  • A perfect binary tree of height h has 2^(h+1) - 1 nodes.
  • Real examples: the DOM, file systems, org charts, and the JSON you parse every day.

276. Binary Tree Representation in C++#

Each node is an object holding a value and two pointers, left and right. An empty child is null.

  • In C++: struct Node { int data; Node* left; Node* right; }; and create nodes with new Node(val).
  • In JavaScript, a class with val, left and right does the same job (see code).
  • Trees can also be stored in arrays (like heaps) when they're complete.
JavaScript
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
//      1
//     / \
//    2   3
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

277. Binary Tree Representation in Java#

Same structure as in C++: a class with a value and references to the left and right child.

  • In Java: class Node { int data; Node left, right; Node(int d) { data = d; } }.
  • Java uses references instead of pointers, but the idea is identical.
  • The JavaScript TreeNode class in the previous item works the same way.

278. Binary Tree Traversals#

Traversal means visiting every node once. Depth-first traversals go deep before wide; breadth-first (level order) goes level by level.

  • Preorder: Root, Left, Right. Good for copying or serialising a tree.
  • Inorder: Left, Root, Right. On a BST this gives sorted order.
  • Postorder: Left, Right, Root. Good for deleting a tree or computing heights bottom-up.
  • Level order uses a queue: push the root, then repeatedly pop a node and push its children.
  • Recursive versions use O(h) stack space; iterative versions use an explicit stack.

Complexity: Time O(n) · Space O(h) for DFS, O(width) for BFS

JavaScript
function preorder(n, out = []) { if (!n) return out; out.push(n.val); preorder(n.left, out); preorder(n.right, out); return out; }
function inorder(n, out = [])  { if (!n) return out; inorder(n.left, out); out.push(n.val); inorder(n.right, out); return out; }
function postorder(n, out = []) { if (!n) return out; postorder(n.left, out); postorder(n.right, out); out.push(n.val); return out; }

282. Level Order Traversal#

Visit nodes level by level from left to right using a queue (Breadth-First Search on a tree).

  • Process one level at a time by recording the queue size before the inner loop.
  • This one template solves zigzag traversal, left/right view, maximum width and minimum depth.

Complexity: Time O(n) · Space O(width)

JavaScript
function levelOrder(root) {
  const res = [];
  if (!root) return res;
  let q = [root];
  while (q.length) {
    res.push(q.map(n => n.val));
    const next = [];
    for (const n of q) { if (n.left) next.push(n.left); if (n.right) next.push(n.right); }
    q = next;
  }
  return res;
}

307. Requirements to construct a unique Binary Tree (Theory)#

To rebuild exactly one binary tree from traversals, you need inorder plus either preorder or postorder.

  • Preorder (or postorder) tells you which node is the root.
  • Inorder tells you which nodes go left of the root and which go right.
  • Preorder + postorder alone is not enough: if a node has one child, you can't tell whether it's left or right.
  • Inorder alone, or preorder alone, is never enough for a general binary tree.

312. Morris Inorder Traversal#

Morris traversal does inorder in O(1) extra space, with no recursion and no stack, by temporarily linking each node's inorder predecessor back to it.

  • If the current node has no left child, visit it and go right.
  • Otherwise find the rightmost node in its left subtree (its predecessor). If that node's right is null, point it to current and go left. If it already points to current, remove the link, visit current and go right.
  • The tree is restored to its original shape by the end.

Complexity: Time O(n) · Space O(1)

JavaScript
function morrisInorder(root) {
  const res = [];
  let cur = root;
  while (cur) {
    if (!cur.left) { res.push(cur.val); cur = cur.right; continue; }
    let pre = cur.left;
    while (pre.right && pre.right !== cur) pre = pre.right;
    if (!pre.right) { pre.right = cur; cur = cur.left; }
    else { pre.right = null; res.push(cur.val); cur = cur.right; }
  }
  return res;
}

Phase 14: Binary Search Trees#

314. Introduction to BST#

A Binary Search Tree keeps every value in the left subtree smaller than the node, and every value in the right subtree larger. This makes search work like binary search.

  • Search, insert and delete take O(h): O(log n) if the tree is balanced, O(n) if it degenerates into a line.
  • Inorder traversal of a BST gives values in sorted order. Many BST problems reduce to this fact.
  • Minimum is the leftmost node; maximum is the rightmost.
  • Balanced variants (AVL, Red-Black) keep h = O(log n); they power TreeMap / std::map.

Complexity: Search/Insert/Delete O(h)

JavaScript
function searchBST(root, x) {
  while (root && root.val !== x) root = x < root.val ? root.left : root.right;
  return root;
}

Phase 15: Graphs#

330. Graph and Types#

A graph is a set of nodes (vertices) connected by edges. Trees, maps, social networks and dependency lists are all graphs.

  • Undirected: edges go both ways (friendship). Directed: edges have a direction (follows, prerequisites).
  • Weighted: each edge has a cost (road distance). Unweighted: all edges cost the same.
  • Cyclic vs acyclic. A Directed Acyclic Graph (DAG) is what you topologically sort.
  • Degree: number of edges touching a node. In directed graphs, split into in-degree and out-degree. In an undirected graph, the sum of degrees = 2 × number of edges.
  • A path is a sequence of connected nodes; a connected component is a group of nodes all reachable from each other.

331. Graph Representation (C++)#

Two common ways to store a graph: an adjacency matrix and an adjacency list.

  • Adjacency matrix: an n × n grid where adj[u][v] = 1 (or the weight) if there's an edge. O(n²) space, O(1) edge check. Good for dense graphs.
  • Adjacency list: for each node, a list of its neighbours. O(V + E) space. The default choice for interview problems.
  • For weighted graphs, store pairs: [neighbour, weight].
  • In C++: vector<vector<int>> adj(n); add an undirected edge with adj[u].push_back(v); adj[v].push_back(u);.
JavaScript
function buildGraph(n, edges, directed = false) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    if (!directed) adj[v].push(u);
  }
  return adj;
}

332. Graph Representation (Java)#

Same two representations as in C++, with Java collections.

  • Java: List<List<Integer>> adj = new ArrayList<>(); then add an empty list per node.
  • Weighted edges: store int[] {neighbour, weight} in each list.
  • The JavaScript buildGraph in the previous item is the equivalent.

333. Connected Components#

A connected component is a group of nodes where every node can reach every other. To count components, start a BFS/DFS from every unvisited node; each start is a new component.

  • Keep one visited array across all searches.
  • Problems like Number of Provinces and Number of Islands are exactly this.
  • Disjoint Set Union is another way to count components.

Complexity: Time O(V + E)

JavaScript
function countComponents(n, adj) {
  const seen = new Array(n).fill(false);
  let count = 0;
  const dfs = u => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs(v); };
  for (let i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); }
  return count;
}

334. BFS#

Breadth-First Search explores the graph level by level from a start node, using a queue. It visits all nodes at distance 1, then distance 2, and so on.

  • Mark a node visited when you push it into the queue, not when you pop it, so it's never added twice.
  • In an unweighted graph, BFS gives the shortest path (fewest edges) from the start to every node.
  • Multi-source BFS (push several starts at once) solves Rotten Oranges and 0/1 Matrix.

Complexity: Time O(V + E) · Space O(V)

JavaScript
function bfs(adj, start) {
  const seen = new Array(adj.length).fill(false), order = [];
  const q = [start]; seen[start] = true;
  for (let i = 0; i < q.length; i++) {
    const u = q[i]; order.push(u);
    for (const v of adj[u]) if (!seen[v]) { seen[v] = true; q.push(v); }
  }
  return order;
}

335. DFS#

Depth-First Search goes as deep as possible along one path before backtracking. It's naturally written with recursion (or an explicit stack).

  • Used for connected components, cycle detection, topological sort, flood fill and finding bridges.
  • In very deep graphs, recursion can overflow the call stack; switch to an iterative stack if needed.

Complexity: Time O(V + E) · Space O(V)

JavaScript
function dfs(adj, start) {
  const seen = new Array(adj.length).fill(false), order = [];
  (function go(u) {
    seen[u] = true; order.push(u);
    for (const v of adj[u]) if (!seen[v]) go(v);
  })(start);
  return order;
}

340. Cycle Detection in Undirected Graph (BFS)#

In an undirected graph, if you reach an already-visited node that isn't the node you just came from (the parent), there's a cycle.

  • Store [node, parent] in the queue (or pass parent in DFS).
  • Run it from every unvisited node, because the graph may have several components.

Complexity: Time O(V + E)

JavaScript
function hasCycleUndirected(n, adj) {
  const seen = new Array(n).fill(false);
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    const q = [[s, -1]]; seen[s] = true;
    for (let i = 0; i < q.length; i++) {
      const [u, p] = q[i];
      for (const v of adj[u]) {
        if (!seen[v]) { seen[v] = true; q.push([v, u]); }
        else if (v !== p) return true;
      }
    }
  }
  return false;
}

349. Cycle Detection in Directed Graph (DFS)#

In a directed graph, a cycle exists if DFS reaches a node that is still on the current recursion path. Track two arrays: visited, and 'on the current path'.

  • When you enter a node, mark it on-path; when you leave, unmark it.
  • Reaching a visited node that's no longer on the path is fine (it's a cross edge, not a cycle).
  • Alternative: run Kahn's algorithm; if it can't process every node, there's a cycle.

Complexity: Time O(V + E)

JavaScript
function hasCycleDirected(n, adj) {
  const state = new Array(n).fill(0); // 0 = new, 1 = on path, 2 = done
  const dfs = u => {
    state[u] = 1;
    for (const v of adj[u]) {
      if (state[v] === 1) return true;
      if (state[v] === 0 && dfs(v)) return true;
    }
    state[u] = 2; return false;
  };
  for (let i = 0; i < n; i++) if (state[i] === 0 && dfs(i)) return true;
  return false;
}

350. Topological Sort (DFS)#

A topological order lists the nodes of a DAG so every edge u → v has u before v. Think of course prerequisites or build steps.

  • Only possible when the graph has no cycle.
  • DFS method: after finishing all of a node's neighbours, push the node onto a stack. Reversing the finish order gives a topological order.
  • There can be many valid orders.

Complexity: Time O(V + E)

JavaScript
function topoDFS(n, adj) {
  const seen = new Array(n).fill(false), stack = [];
  const dfs = u => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs(v); stack.push(u); };
  for (let i = 0; i < n; i++) if (!seen[i]) dfs(i);
  return stack.reverse();
}

351. Kahn's Algorithm (BFS)#

Kahn's algorithm builds a topological order with BFS: repeatedly take a node with in-degree 0, output it, and reduce the in-degree of its neighbours.

  • Start with all nodes whose in-degree is 0 in the queue.
  • If the output has fewer than n nodes, the graph has a cycle. This is how Course Schedule is solved.

Complexity: Time O(V + E)

JavaScript
function kahn(n, adj) {
  const indeg = new Array(n).fill(0);
  for (const list of adj) for (const v of list) indeg[v]++;
  const q = [], order = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  for (let i = 0; i < q.length; i++) {
    const u = q[i]; order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return order.length === n ? order : []; // [] means cycle
}

359. Dijkstra's Algorithm#

Dijkstra finds the shortest distance from a source to every node in a graph with non-negative edge weights. It always expands the closest unfinished node next.

  • Set dist[source] = 0 and everything else to Infinity. Push (0, source) into a min-heap.
  • Pop the smallest distance; skip it if it's outdated. For each neighbour, if dist[u] + w is smaller, update and push.
  • Does not work with negative edge weights. Use Bellman-Ford for those.

Complexity: Time O((V + E) log V) with a heap

JavaScript
// adj[u] = [[v, w], ...]. Simple version: the array is sorted each step.
// For large graphs, use the MinHeap class from Phase 11 instead.
function dijkstra(n, adj, src) {
  const dist = new Array(n).fill(Infinity); dist[src] = 0;
  const pq = [[0, src]];
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) if (d + w < dist[v]) { dist[v] = d + w; pq.push([dist[v], v]); }
  }
  return dist;
}

360. Why Priority Queue in Dijkstra's#

The priority queue always hands Dijkstra the node with the smallest known distance. Because weights are non-negative, that distance can never get smaller later, so the node is finalised.

  • With a plain queue you'd process nodes in arbitrary order and might relax the same node many times.
  • With a min-heap, each pop is O(log V), giving O((V + E) log V) overall.
  • A Set (ordered set) also works and lets you delete outdated entries instead of skipping them.

367. Bellman Ford Algorithm#

Bellman-Ford finds shortest paths even with negative edge weights by relaxing every edge V - 1 times.

  • A shortest path has at most V - 1 edges, so V - 1 rounds are enough.
  • Run one more round: if any distance still improves, the graph has a negative cycle.
  • Slower than Dijkstra, so use it only when negative weights exist.

Complexity: Time O(V · E)

JavaScript
function bellmanFord(n, edges, src) {   // edges = [[u, v, w], ...]
  const dist = new Array(n).fill(Infinity); dist[src] = 0;
  for (let i = 0; i < n - 1; i++)
    for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) return null; // negative cycle
  return dist;
}

368. Floyd Warshall Algorithm#

Floyd-Warshall finds the shortest path between every pair of nodes. For each possible middle node k, it checks whether going through k improves the path from i to j.

  • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every k, i, j, with k as the outermost loop.
  • Handles negative edges. If dist[i][i] becomes negative, there's a negative cycle.
  • Good for small graphs (n up to a few hundred).

Complexity: Time O(V³) · Space O(V²)

JavaScript
function floyd(dist) {          // dist is an n x n matrix, Infinity for no edge
  const n = dist.length;
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
  return dist;
}

370. Minimum Spanning Tree (Theory)#

A spanning tree connects all V nodes of a graph using exactly V - 1 edges and no cycles. The Minimum Spanning Tree (MST) is the spanning tree with the smallest total edge weight.

  • Only defined for connected, undirected, weighted graphs.
  • Real use: connecting cities with the least cable or road.
  • Two standard algorithms: Prim's (grow one tree from a start node) and Kruskal's (add cheapest edges that don't form a cycle).

371. Prim's Algorithm#

Prim's grows the MST from one node. At every step it adds the cheapest edge that connects a node inside the tree to a node outside it.

  • Use a min-heap of [weight, node]. Pop the cheapest; skip if the node is already in the tree; otherwise add its weight and push its edges.
  • Very similar in shape to Dijkstra, but the key is the edge weight, not the total distance.

Complexity: Time O(E log V)

JavaScript
function prim(n, adj) {   // adj[u] = [[v, w], ...]
  const inTree = new Array(n).fill(false);
  const pq = [[0, 0]];
  let total = 0;
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [w, u] = pq.shift();
    if (inTree[u]) continue;
    inTree[u] = true; total += w;
    for (const [v, wt] of adj[u]) if (!inTree[v]) pq.push([wt, v]);
  }
  return total;
}

372. Disjoint Set (Union by Rank)#

Disjoint Set Union (DSU, or Union-Find) keeps track of which elements belong to the same group and can merge groups quickly.

  • find(x) returns the leader (root) of x's group. union(a, b) merges the two groups.
  • Path compression: during find, point every node on the path straight to the root.
  • Union by rank: attach the shorter tree under the taller one so trees stay flat.
  • With both tricks, each operation is almost O(1) (inverse Ackermann).
  • Used in Kruskal's algorithm, counting components and detecting cycles in undirected graphs.

Complexity: Almost O(1) per operation

JavaScript
class DSU {
  constructor(n) { this.p = [...Array(n).keys()]; this.rank = new Array(n).fill(0); }
  find(x) { return this.p[x] === x ? x : (this.p[x] = this.find(this.p[x])); }
  union(a, b) {
    a = this.find(a); b = this.find(b);
    if (a === b) return false;
    if (this.rank[a] < this.rank[b]) [a, b] = [b, a];
    this.p[b] = a;
    if (this.rank[a] === this.rank[b]) this.rank[a]++;
    return true;
  }
}

373. Disjoint Set (Union by Size)#

Same as union by rank, but instead of tree height you track the number of elements in each group and attach the smaller group under the larger one.

  • Size is easier to reason about than rank and also gives you the group size for free (useful in Making a Large Island).
  • Keep path compression in find.

Complexity: Almost O(1) per operation

JavaScript
class DSUSize {
  constructor(n) { this.p = [...Array(n).keys()]; this.size = new Array(n).fill(1); }
  find(x) { return this.p[x] === x ? x : (this.p[x] = this.find(this.p[x])); }
  union(a, b) {
    a = this.find(a); b = this.find(b);
    if (a === b) return false;
    if (this.size[a] < this.size[b]) [a, b] = [b, a];
    this.p[b] = a; this.size[a] += this.size[b];
    return true;
  }
}

374. Kruskal's Algorithm#

Kruskal's builds the MST by sorting all edges by weight and adding them one by one, skipping any edge that would create a cycle. DSU checks for cycles.

  • If union(u, v) succeeds, the edge joins two different groups and is safe to add.
  • Stop after adding V - 1 edges.

Complexity: Time O(E log E)

JavaScript
// uses the DSU class from "Disjoint Set (Union by Rank)"
function kruskal(n, edges) {   // edges = [[u, v, w], ...]
  edges.sort((a, b) => a[2] - b[2]);
  const dsu = new DSU(n);
  let total = 0;
  for (const [u, v, w] of edges) if (dsu.union(u, v)) total += w;
  return total;
}

381. Bridges in Graph#

A bridge is an edge whose removal splits the graph into more pieces. Tarjan's algorithm finds all bridges in one DFS.

  • tin[u]: time when DFS first reached u. low[u]: the earliest tin reachable from u's subtree using at most one back edge.
  • For a tree edge u → v, if low[v] > tin[u], then v's subtree can't reach u or above any other way, so u-v is a bridge.
  • Same idea gives Critical Connections in a Network.

Complexity: Time O(V + E)

JavaScript
function bridges(n, adj) {
  const tin = new Array(n).fill(-1), low = new Array(n).fill(0), res = [];
  let timer = 0;
  const dfs = (u, p) => {
    tin[u] = low[u] = timer++;
    for (const v of adj[u]) {
      if (v === p) continue;
      if (tin[v] === -1) {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > tin[u]) res.push([u, v]);
      } else low[u] = Math.min(low[u], tin[v]);
    }
  };
  for (let i = 0; i < n; i++) if (tin[i] === -1) dfs(i, -1);
  return res;
}

382. Articulation Point in Graph#

An articulation point (cut vertex) is a node whose removal disconnects the graph. Found with the same tin/low DFS as bridges.

  • For a non-root u with child v: if low[v] >= tin[u], u is an articulation point.
  • The DFS root is an articulation point only if it has more than one DFS child.
  • Note the >= here versus > for bridges.

Complexity: Time O(V + E)

383. Kosaraju's Algorithm (SCC)#

A Strongly Connected Component (SCC) in a directed graph is a group where every node can reach every other. Kosaraju's finds all SCCs with two DFS passes.

  • Pass 1: DFS on the original graph and record nodes by finish time.
  • Reverse every edge.
  • Pass 2: take nodes in decreasing finish time; each DFS on the reversed graph from an unvisited node collects exactly one SCC.

Complexity: Time O(V + E)

JavaScript
function kosaraju(n, adj) {
  const seen = new Array(n).fill(false), order = [];
  const dfs1 = u => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs1(v); order.push(u); };
  for (let i = 0; i < n; i++) if (!seen[i]) dfs1(i);
  const rev = Array.from({ length: n }, () => []);
  adj.forEach((list, u) => list.forEach(v => rev[v].push(u)));
  seen.fill(false);
  let count = 0;
  const dfs2 = u => { seen[u] = true; for (const v of rev[u]) if (!seen[v]) dfs2(v); };
  for (let i = n - 1; i >= 0; i--) if (!seen[order[i]]) { count++; dfs2(order[i]); }
  return count;
}

Phase 16: Dynamic Programming#

384. Dynamic Programming Introduction#

Dynamic Programming (DP) solves a problem by breaking it into overlapping subproblems and storing each answer so it's computed only once.

  • DP applies when a problem has overlapping subproblems (the same smaller question comes up again and again) and optimal substructure (the best answer is built from best answers to smaller parts).
  • Memoisation (top-down): write the plain recursion, then cache results in an array or map.
  • Tabulation (bottom-up): fill a table from the smallest subproblem upward with loops. No recursion stack.
  • Space optimisation: if each state only needs the previous one or two, keep just those values.
  • How to approach any DP: (1) express the problem in terms of an index, (2) try all choices at that index, (3) take the min/max/sum as the problem asks, (4) add memoisation, then convert to tabulation.

Complexity: Fibonacci: plain recursion O(2ⁿ) → memoised O(n) → O(1) space

JavaScript
// memoisation
function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  return (memo[n] = fib(n - 1, memo) + fib(n - 2, memo));
}
// tabulation with O(1) space
function fibIter(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

Phase 17: Tries#

440. Implement Trie (Insert, Search, StartsWith)#

A Trie (prefix tree) stores words character by character. Each node has children for the next letters and a flag marking the end of a word. Words with a common prefix share the same path.

  • Insert, search and startsWith all take O(L) where L is the word length, regardless of how many words are stored.
  • Used for autocomplete, spell check and search-box suggestions, which makes it a good one for frontend developers to know.
  • A binary trie (children 0 and 1) solves Maximum XOR problems.

Complexity: Each operation O(L)

JavaScript
class Trie {
  constructor() { this.root = {}; }
  insert(w) { let n = this.root; for (const c of w) n = n[c] ??= {}; n.end = true; }
  #walk(s) { let n = this.root; for (const c of s) { n = n[c]; if (!n) return null; } return n; }
  search(w) { return this.#walk(w)?.end === true; }
  startsWith(p) { return this.#walk(p) !== null; }
}

Phase 18: Strings: Advanced Algorithms#

449. Hashing in Strings (Theory)#

String hashing turns a string into a number so two strings can be compared in O(1) instead of O(L). A rolling (polynomial) hash lets you compute the hash of any substring quickly.

  • hash(s) = s[0]·pᴸ⁻¹ + s[1]·pᴸ⁻² + ... + s[L-1], all taken modulo a large prime m. p is a small prime like 31 or 131.
  • Precompute prefix hashes; then the hash of any substring s[l..r] comes out in O(1).
  • Different strings can have the same hash (a collision). Using a big modulus or two different hashes makes that very unlikely.
  • Foundation for Rabin-Karp and for counting distinct substrings.

450. Rabin Karp Algorithm#

Rabin-Karp finds a pattern in a text by comparing hashes. It slides a window the size of the pattern across the text, updating the window's hash in O(1) per step.

  • Rolling update: remove the leftmost character's contribution, multiply by the base, add the new character.
  • When the hashes match, compare the actual characters to rule out a collision.
  • Average O(n + m). Worst case O(n·m) if there are many collisions.

Complexity: Average O(n + m)

JavaScript
function rabinKarp(text, pat) {
  const B = 131, M = 1_000_000_007, m = pat.length, res = [];
  if (m > text.length) return res;
  let hp = 0, ht = 0, pow = 1;
  for (let i = 0; i < m; i++) {
    hp = (hp * B + pat.charCodeAt(i)) % M;
    ht = (ht * B + text.charCodeAt(i)) % M;
    if (i < m - 1) pow = (pow * B) % M;
  }
  for (let i = 0; ; i++) {
    if (hp === ht && text.substr(i, m) === pat) res.push(i);
    if (i + m >= text.length) break;
    ht = (ht - text.charCodeAt(i) * pow % M + M) % M;
    ht = (ht * B + text.charCodeAt(i + m)) % M;
  }
  return res;
}

451. Z-Function#

The Z-array stores, for each position i, the length of the longest substring starting at i that matches a prefix of the string.

  • Pattern search: build Z for pattern + '$' + text; any position where Z equals the pattern length is a match.
  • Computed in O(n) by keeping a window [l, r] that matches the prefix and reusing earlier values inside it.

Complexity: Time O(n)

JavaScript
function zFunction(s) {
  const n = s.length, z = new Array(n).fill(0);
  for (let i = 1, l = 0, r = 0; i < n; i++) {
    if (i < r) z[i] = Math.min(r - i, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (i + z[i] > r) { l = i; r = i + z[i]; }
  }
  return z;
}

452. KMP Algorithm / LPS (pi) array#

KMP searches for a pattern in O(n + m) without ever moving backward in the text. It precomputes the LPS array: for each prefix of the pattern, the length of the longest proper prefix that is also a suffix.

  • On a mismatch, instead of restarting the pattern from 0, jump to lps[j - 1], because that many characters are already known to match.
  • The LPS array alone answers problems like Longest Happy Prefix and Shortest Palindrome.
  • Example: for 'aabaaab', lps = [0,1,0,1,2,2,3].

Complexity: Time O(n + m) · Space O(m)

JavaScript
function buildLPS(p) {
  const lps = new Array(p.length).fill(0);
  for (let i = 1, len = 0; i < p.length; ) {
    if (p[i] === p[len]) lps[i++] = ++len;
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}
function kmpSearch(t, p) {
  const lps = buildLPS(p), res = [];
  for (let i = 0, j = 0; i < t.length; ) {
    if (t[i] === p[j]) { i++; j++; if (j === p.length) { res.push(i - j); j = lps[j - 1]; } }
    else if (j) j = lps[j - 1];
    else i++;
  }
  return res;
}
Next

Go back to the JioCoder 450 roadmap to tick off the problems, or continue with Concepts Part 1 (Phases 1 to 9).

Key takeaways#

  • Sliding window and monotonic stack each turn O(n²) scans into O(n).
  • BFS gives shortest paths in unweighted graphs; Dijkstra handles non-negative weights.
  • DSU makes Kruskal and component counting almost O(1) per step.
  • Every DP starts as plain recursion, then memoisation, then tabulation.
  • KMP and Z-function match patterns in linear time.

Article discussion

(0)

Join the discussion — login to comment and help other developers.

Login to comment