Chapter•480 Minutes

Items per page

Hard DSA — Advanced Graphs, Trees, and Priority Queues

Master complex graph connectivity, topological ordering, shortest path algorithms, median tracking heaps, and advanced tree transformations.

01. Alien Dictionary

Difficulty:HardPattern:Topological Sort / Kahn BFSTime:O(V + E)Space:O(V + E)

There is a new alien language that uses the Latin alphabet. However, the order among the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings inside words are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in lexicographically increasing order.

How It Works & Algorithmic Design

Solves using Directed Graph Construction with Kahn's Topological Sort:

Graph Nodes: Initialize adjacency list adj and in-degree map inDegree for every unique character.
Edge Construction: Compare adjacent words word1 and word2:
- Find first mismatch index $k$: char1 = word1[k], char2 = word2[k].
- Add directed edge char1 -> char2 and increment inDegree[char2]++.
- Edge Case: if word2 is a prefix of word1 (e.g., "abc" before "ab"), language order is invalid $\to$ return "".
Kahn's BFS: Process nodes with inDegree === 0 using a queue.
Cycle Detection: If result length does not match total unique characters, a cycle exists $\to$ return "".

Why This Approach Works Best

Topological sorting detects illegal circular dependencies while producing a valid linear character ordering in $O(V + E)$ time.

Example Walkthrough

Input: words = ["wrt","wrf","er","ett","rftt"]

Sorted alien words list.

Extracted Rules: 't'->'f', 'w'->'e', 'r'->'t', 'e'->'r'

Character ordering graph edges.

Output: "wertf"

Valid alien alphabet order.

Answer: Alien Dictionary Topological Sort implementation

function alienOrder(words) {
  const adj = {}, inDegree = {};
  for (const w of words) {
    for (const c of w) {
      inDegree[c] = 0;
      adj[c] = new Set();
    }
  }
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    if (w1.length > w2.length && w1.startsWith(w2)) return '';
    for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
      if (w1[j] !== w2[j]) {
        if (!adj[w1[j]].has(w2[j])) {
          adj[w1[j]].add(w2[j]);
          inDegree[w2[j]]++;
        }
        break;
      }
    }
  }
  const queue = [];
  for (const c in inDegree) if (inDegree[c] === 0) queue.push(c);
  let res = '';
  while (queue.length) {
    const c = queue.shift();
    res += c;
    for (const neighbor of adj[c]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return res.length === Object.keys(inDegree).length ? res : '';
}

💡 Build graph edges from adjacent word differences and perform Kahn's BFS topological sort.

Key Takeaways

Extract character dependency directed edges by comparing adjacent words.
Prefix check (e.g. "abc" before "ab") catches illegal invalid input dictionary states.
Runs in $O(V + E)$ time where $V$ is unique characters and $E$ is extracted ordering rules.

02. Find Median from Data Stream

Difficulty:HardPattern:Two Priority Queues / Dynamic MedianTime:Add O(log n), Query O(1)Space:O(n)

Implement a data structure MedianFinder that supports adding numbers from a data stream and finding the median of all elements added so far.

How It Works & Algorithmic Design

Solves using Two Heaps (Max-Heap for Lower Half, Min-Heap for Upper Half):

Data Structure: Maintain maxHeap (stores smaller numbers) and minHeap (stores larger numbers).
addNum(num):
- Push num to maxHeap.
- Balance values: pop root of maxHeap and push to minHeap.
- Balance sizes: if minHeap.size > maxHeap.size, pop root of minHeap and push to maxHeap.
findMedian():
- If maxHeap.size > minHeap.size, median = maxHeap.peek().
- Else, median = (maxHeap.peek() + minHeap.peek()) / 2.

Why This Approach Works Best

Inserts numbers in $O(\log n)$ time and queries median in optimal $O(1)$ constant time.

Example Walkthrough

Stream Operations: addNum(1) -> addNum(2) -> findMedian() -> addNum(3) -> findMedian()

Dynamic insertions.

Median States: After 1,2: median = (1+2)/2 = 1.5. After 1,2,3: median = 2.

Calculates running median.

Output: [1.5, 2.0]

Result sequence.

Answer: Median Finder using Two Priority Queues

class MedianFinder {
  constructor() {
    this.small = []; // Max Heap simulated via sorted array insertion
    this.large = []; // Min Heap simulated
  }
  addNum(num) {
    this.small.push(num);
    this.small.sort((a, b) => b - a);
    this.large.push(this.small.shift());
    this.large.sort((a, b) => a - b);
    if (this.large.length > this.small.length) {
      this.small.push(this.large.shift());
      this.small.sort((a, b) => b - a);
    }
  }
  findMedian() {
    if (this.small.length > this.large.length) return this.small[0];
    return (this.small[0] + this.large[0]) / 2;
  }
}

💡 Balance max-heap and min-heap to access stream median in constant O(1) time.

Key Takeaways

Max-heap stores lower half; Min-heap stores upper half.
Heap size difference is kept at most 1.
addNum takes $O(\log n)$ and findMedian takes $O(1)$ time.

03. Binary Tree Maximum Path Sum

Difficulty:HardPattern:Tree Post-Order DFSTime:O(n)Space:O(h)

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. Return the maximum path sum of any non-empty path.

How It Works & Algorithmic Design

Solves using Recursive Post-Order DFS Branch Traversal:

Global Max Variable: Set maxSum = -Infinity.
DFS Function gain(node):
- Base Case: if node === null, return 0.
- Compute max gain from subtrees (ignore negative sums):
  - leftGain = Math.max(0, gain(node.left))
  - rightGain = Math.max(0, gain(node.right))
- Local inverted-V path sum: currentPathSum = node.val + leftGain + rightGain.
- Update global max: maxSum = Math.max(maxSum, currentPathSum).
- Return single branch gain to parent: node.val + Math.max(leftGain, rightGain).

Why This Approach Works Best

Evaluates paths making turning points at any node while passing straight branch sums up to parents in $O(n)$ time and $O(h)$ space.

Example Walkthrough

Input Tree: [-10, 9, 20, null, null, 15, 7]

Binary tree root.

Max Path: 15 -> 20 -> 7 gives max sum = 15 + 20 + 7 = 42

Inverted-V path through node 20.

Output: 42

Maximum path sum.

Answer: Binary Tree Maximum Path Sum implementation

function maxPathSum(root) {
  let maxSum = -Infinity;
  function gain(node) {
    if (!node) return 0;
    const leftGain = Math.max(0, gain(node.left));
    const rightGain = Math.max(0, gain(node.right));
    maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
    return node.val + Math.max(leftGain, rightGain);
  }
  gain(root);
  return maxSum;
}

💡 Compute maximum gain from left and right subtrees and update running global maximum sum.

Key Takeaways

Use Math.max(0, gain) to prune negative path sum contributions.
Node splits into two branches locally, but returns only one branch to its parent.
Linear time complexity $O(n)$.

04. Word Ladder II

Difficulty:HardPattern:BFS Graph Distance + Backtracking DFSTime:O(N * L^2)Space:O(N * L)

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord.

How It Works & Algorithmic Design

Solves using Bidirectional BFS Level Graph Construction + Backtracking DFS:

BFS Level Mapping: Perform BFS starting from beginWord. Build distance map distMap[word] storing shortest steps from beginWord to every reachable dictionary word.
DFS Path Backtracking: Backtrack from endWord down to beginWord:
- Only step to neighbor words where distMap[neighbor] === distMap[current] - 1.
Return: All collected minimum length paths.

Why This Approach Works Best

Decoupling minimum distance calculation (BFS) from path generation (DFS) prevents combinatorial path explosion.

Example Walkthrough

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Target conversion.

Shortest Paths: ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]

Length 5 paths.

Output: List of both 5-step shortest paths.

All minimum transformations.

Answer: Word Ladder II BFS + DFS implementation

function findLadders(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return [];
  wordSet.add(beginWord);
  const dist = new Map();
  const queue = [beginWord];
  dist.set(beginWord, 0);
  while (queue.length) {
    const curr = queue.shift();
    const d = dist.get(curr);
    for (let i = 0; i < curr.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const next = curr.substring(0, i) + String.fromCharCode(c) + curr.substring(i + 1);
        if (wordSet.has(next) && !dist.has(next)) {
          dist.set(next, d + 1);
          queue.push(next);
        }
      }
    }
  }
  if (!dist.has(endWord)) return [];
  const res = [];
  function dfs(word, path) {
    if (word === beginWord) {
      res.push([beginWord, ...path]);
      return;
    }
    const d = dist.get(word);
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const prev = word.substring(0, i) + String.fromCharCode(c) + word.substring(i + 1);
        if (dist.get(prev) === d - 1) {
          dfs(prev, [word, ...path]);
        }
      }
    }
  }
  dfs(endWord, []);
  return res;
}

💡 Build shortest distance level graph using BFS, then generate valid minimum paths using DFS backtracking.

Key Takeaways

BFS measures shortest levels; DFS reconstructs exact matching paths.
Backtracking backwards from endWord reduces redundant branching.
Time complexity $O(N \cdot L^2)$.

05. Critical Connections in a Network (Tarjan's Bridges)

Difficulty:HardPattern:Tarjan Bridge Finding DFSTime:O(V + E)Space:O(V + E)

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections. Return all critical connections (bridges) whose removal disconnects the network.

How It Works & Algorithmic Design

Solves using Tarjan's Bridge Finding DFS Algorithm:

Tracking Arrays: Maintain discoveryTime array and lowestTime array initialized to -1.
DFS Logic dfs(node, parent, time):
- Set discoveryTime[node] = lowestTime[node] = time++.
- For each neighbor in adjacency list:
  - If neighbor === parent, continue.
  - If unvisited (discoveryTime[neighbor] === -1):
    - Recurse dfs(neighbor, node, time).
    - Update lowestTime[node] = Math.min(lowestTime[node], lowestTime[neighbor]).
    - Bridge Condition: If lowestTime[neighbor] > discoveryTime[node], connection (node, neighbor) is a critical bridge! Push to result.
  - If already visited: lowestTime[node] = Math.min(lowestTime[node], discoveryTime[neighbor]).

Why This Approach Works Best

Finds all graph bridges in a single pass $O(V + E)$ linear time without testing node removals iteratively.

Example Walkthrough

Input Network: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

4 connected servers.

Bridge Analysis: [0,1,2] forms a cycle, but edge [1,3] is the only path to node 3.

Removing [1,3] disconnects node 3.

Output: [[1,3]]

Critical bridge connection.

Answer: Tarjan's Critical Connections implementation

function criticalConnections(n, connections) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of connections) {
    adj[u].push(v); adj[v].push(u);
  }
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const bridges = [];
  let time = 0;
  function dfs(u, parent) {
    disc[u] = low[u] = time++;
    for (const v of adj[u]) {
      if (v === parent) continue;
      if (disc[v] === -1) {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) bridges.push([u, v]);
      } else {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }
  dfs(0, -1);
  return bridges;
}

💡 Traverse graph via DFS tracking discovery times and low link values to detect bridge edges.

Key Takeaways

Bridge condition low[v] > disc[u] means neighbor v cannot reach any ancestor of u.
Tarjan's algorithm finds all network bottlenecks in single DFS pass.
Linear time complexity $O(V + E)$.

06. Reconstruct Itinerary

Difficulty:HardPattern:Hierholzer Eulerian Path DFSTime:O(E log E)Space:O(V + E)

You are given a list of airline tickets where tickets[i] = [from_i, to_i]. Reconstruct the itinerary in order and return it. All tickets must be used, starting from 'JFK'. If there are multiple valid itineraries, return the itinerary that has the smallest lexical order.

How It Works & Algorithmic Design

Solves using Hierholzer's Eulerian Path DFS Algorithm:

Sorted Adjacency Map: Build directed graph using a Min-Heap/Priority Queue for destination neighbors to enforce lexicographical traversal.
Hierholzer's Post-Order DFS dfs(airport):
- While adj[airport] is not empty:
  - Pop smallest destination neighbor next = adj[airport].poll().
  - Recurse dfs(next).
- Push airport onto result stack.
Return: Reverse result stack.

Why This Approach Works Best

Hierholzer's algorithm traverses every graph edge (ticket) exactly once in $O(E \log E)$ time, handling back-tracking dead-ends naturally.

Example Walkthrough

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Flight ticket pairs.

Eulerian Path: "JFK" -> "MUC" -> "LHR" -> "SFO" -> "SJC"

All tickets visited in order.

Output: ["JFK","MUC","LHR","SFO","SJC"]

Final itinerary.

Answer: Reconstruct Itinerary Hierholzer implementation

function findItinerary(tickets) {
  const adj = {};
  for (const [from, to] of tickets) {
    if (!adj[from]) adj[from] = [];
    adj[from].push(to);
  }
  for (const from in adj) adj[from].sort();
  const res = [];
  function dfs(airport) {
    const dests = adj[airport];
    while (dests && dests.length) {
      dfs(dests.shift());
    }
    res.push(airport);
  }
  dfs('JFK');
  return res.reverse();
}

💡 Traverse smallest airport neighbors via Eulerian path DFS and reverse accumulated post-order stack.

Key Takeaways

Guarantees all directed edges (tickets) are consumed exactly once.
Sorting airport neighbors satisfies smallest lexicographical choice requirement.
Reversing post-order traversal stack yields the correct path order.

07. Shortest Path to Get All Keys

Difficulty:HardPattern:BFS Grid + Bitmask StateTime:O(m * n * 2^K)Space:O(m * n * 2^K)

You are given an $m \times n$ grid where lowercase letters 'a'-'f' are keys, uppercase letters 'A'-'F' are locks, '#' is a wall, and '@' is starting position. Return the minimum number of moves to acquire all keys.

How It Works & Algorithmic Design

Solves using BFS State Space Traversal with Bitmasking:

Key Bitmasking: Identify total key count $K$. Goal state bitmask is (1 << K) - 1.
Visited Set 3D State: Track visited[r][c][bitmask] to allow revisiting grid cells when carrying new key sets.
BFS Queue Entry: (r, c, bitmask, steps).
Cell Evaluation:
- Step onto key 'a'-'f': update newMask = bitmask | (1 << (char - 'a')).
- Step onto lock 'A'-'F': allowed if (bitmask & (1 << (char - 'A'))) !== 0.
- Reaching newMask === goalMask: return steps + 1 instantly.

Why This Approach Works Best

Bitmask state representation transforms multi-key path finding into a clean shortest path BFS graph search in $O(m \times n \times 2^K)$ time.

Example Walkthrough

Input Grid: ["@.a..","###.#","b.A.B"]

2 keys ('a','b') and 2 locks ('A','B').

Shortest Path: Collect 'a' -> move down to 'b' -> unlock 'A' and 'B'.

8 total steps.

Output: 8

Minimum steps.

Answer: Shortest Path All Keys Bitmask BFS implementation

function shortestPathAllKeys(grid) {
  const m = grid.length, n = grid[0].length;
  let startR = 0, startC = 0, keyCount = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      const ch = grid[r][c];
      if (ch === '@') { startR = r; startC = c; }
      else if (ch >= 'a' && ch <= 'f') keyCount++;
    }
  }
  const targetMask = (1 << keyCount) - 1;
  const queue = [[startR, startC, 0, 0]];
  const visited = new Set([`${startR},${startC},0`]);
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (queue.length) {
    const [r, c, mask, steps] = queue.shift();
    if (mask === targetMask) return steps;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] === '#') continue;
      const ch = grid[nr][nc];
      let newMask = mask;
      if (ch >= 'a' && ch <= 'f') newMask |= (1 << (ch.charCodeAt(0) - 97));
      if (ch >= 'A' && ch <= 'F' && !(mask & (1 << (ch.charCodeAt(0) - 65)))) continue;
      const keyState = `${nr},${nc},${newMask}`;
      if (!visited.has(keyState)) {
        visited.add(keyState);
        queue.push([nr, nc, newMask, steps + 1]);
      }
    }
  }
  return -1;
}

💡 Traverse grid via BFS storing position and key bitmask to reach all keys in minimal steps.

Key Takeaways

Use bitmask to record collected keys efficiently.
Visited tracking requires [row, col, keyMask] tuple state.
Guarantees shortest path moves using BFS traversal.

08. Trapping Rain Water II (3D Surface)

Difficulty:HardPattern:3D Min-Heap Boundary Inward SearchTime:O(M * N log(M * N))Space:O(M * N)

Given an $m \times n$ integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

How It Works & Algorithmic Design

Solves using Min-Heap Priority Queue Grid Boundary Shrinking:

Boundary Priority Queue: Push all outer boundary cells (r, c, height) into Min-Heap. Mark cells as visited.
Min-Height Processing: Maintain running maxBoundaryHeight = 0. While heap is not empty:
- Pop smallest boundary cell (r, c, h).
- Update maxBoundaryHeight = Math.max(maxBoundaryHeight, h).
- Evaluate 4 neighbors (nr, nc):
  - If unvisited: mark visited, accumulate trapped water Math.max(0, maxBoundaryHeight - heightMap[nr][nc]), and push neighbor to Min-Heap.

Why This Approach Works Best

Shrinking boundaries inward from lowest boundary height simulates water containment physics in $O(m \cdot n \log(m \cdot n))$ time.

Example Walkthrough

Input Grid: [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]

3D terrain matrix.

Water Volume: Inner valleys hold 4 total units of water.

Physics containment sum.

Output: 4

Trapped volume.

Answer: Trapping Rain Water II 3D implementation

function trapRainWater(heightMap) {
  const m = heightMap.length, n = heightMap[0].length;
  if (m < 3 || n < 3) return 0;
  const visited = Array.from({ length: m }, () => new Array(n).fill(false));
  const heap = []; // Simulated Min-heap array
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (r === 0 || r === m - 1 || c === 0 || c === n - 1) {
        visited[r][c] = true;
        heap.push([heightMap[r][c], r, c]);
      }
    }
  }
  heap.sort((a, b) => a[0] - b[0]);
  let water = 0, maxBoundary = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (heap.length) {
    const [h, r, c] = heap.shift();
    maxBoundary = Math.max(maxBoundary, h);
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < m && nc < n && !visited[nr][nc]) {
        visited[nr][nc] = true;
        if (heightMap[nr][nc] < maxBoundary) water += maxBoundary - heightMap[nr][nc];
        heap.push([heightMap[nr][nc], nr, nc]);
        heap.sort((a, b) => a[0] - b[0]);
      }
    }
  }
  return water;
}

💡 Pop lowest boundary height from priority queue and expand inward to trap surface water.

Key Takeaways

Boundary items must be pushed into Priority Queue first.
Water spill height is determined by lowest surrounding wall.
Runs in $O(M \cdot N \log(M \cdot N))$ time.

09. Minimum Cost to Make at Least One Valid Path in a Grid

Difficulty:HardPattern:0-1 BFS DequeTime:O(m * n)Space:O(m * n)

Given an $m \times n$ grid where each cell has a sign pointing right, left, down, or up, return the minimum cost to make at least one valid path from (0,0) to (m-1,n-1).

How It Works & Algorithmic Design

Solves using 0-1 BFS with Double-Ended Queue (Deque):

Distance Matrix: Maintain cost[r][c] initialized to Infinity. Set cost[0][0] = 0.
Deque Logic:
- If moving in cell's existing sign direction: weight 0 $\to$ push neighbor to FRONT of Deque.
- If changing cell sign direction: weight 1 $\to$ push neighbor to BACK of Deque.
Return: cost[m-1][n-1] when destination is popped.

Why This Approach Works Best

0-1 BFS evaluates shortest paths with 0 and 1 edge weights in optimal linear $O(m \times n)$ time without $O(V \log V)$ Dijkstra overhead.

Example Walkthrough

Input Grid: [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

Grid with direction arrows.

Min Cost Path: Changing 3 arrows gives valid path to end.

3 total direction changes required.

Output: 3

Minimum modification cost.

Answer: Minimum Cost Grid Path 0-1 BFS implementation

function minCost(grid) {
  const m = grid.length, n = grid[0].length;
  const cost = Array.from({ length: m }, () => new Array(n).fill(Infinity));
  cost[0][0] = 0;
  const deque = [[0, 0]];
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]]; // 1:right, 2:left, 3:down, 4:up
  while (deque.length) {
    const [r, c] = deque.shift();
    if (r === m - 1 && c === n - 1) return cost[r][c];
    for (let i = 0; i < 4; i++) {
      const nr = r + dirs[i][0], nc = c + dirs[i][1];
      if (nr >= 0 && nc >= 0 && nr < m && nc < n) {
        const w = (grid[r][c] === i + 1) ? 0 : 1;
        if (cost[r][c] + w < cost[nr][nc]) {
          cost[nr][nc] = cost[r][c] + w;
          if (w === 0) deque.unshift([nr, nc]);
          else deque.push([nr, nc]);
        }
      }
    }
  }
  return cost[m - 1][n - 1];
}

💡 Process zero-cost direction steps before one-cost direction changes using a double-ended queue.

Key Takeaways

0-cost edges get prepended (unshift/addFirst); 1-cost edges get appended (push/addLast).
Optimal linear $O(m \times n)$ algorithm for graphs with binary edge weights.
Avoids PriorityQueue $O(V \log V)$ overhead.

10. Swim in Rising Water

Difficulty:HardPattern:Dijkstra Priority QueueTime:O(n^2 log n)Space:O(n^2)

You are given an $n \times n$ integer matrix grid where each cell represents the elevation at that point. Rain starts falling and time $t$ increases. You can swim between adjacent cells if elevation at both cells is at most $t$. Return the least time until you can reach (n-1, n-1).

How It Works & Algorithmic Design

Solves using Modified Dijkstra's Algorithm:

Min-Heap Priority Queue: Store (maxElevationOnPath, r, c).
Initialization: Push (grid[0][0], 0, 0) to heap. Mark grid[0][0] visited.
Dijkstra Loop:
- Pop element (t, r, c) with smallest path elevation.
- If r === n-1 && c === n-1, return t instantly.
- For each unvisited neighbor (nr, nc):
  - newTime = Math.max(t, grid[nr][nc]).
  - Push (newTime, nr, nc) into heap.

Why This Approach Works Best

Greedily picks paths minimizing maximum water height in $O(n^2 \log n)$ time.

Example Walkthrough

Input Grid: [[0,2],[1,3]]

2x2 grid.

Dijkstra Route: (0,0) [h=0] -> (1,0) [h=1] -> (1,1) [h=3]

Max height on path is 3.

Output: 3

Minimum swim time.

Answer: Swim in Rising Water Dijkstra implementation

function swimInWater(grid) {
  const n = grid.length;
  const visited = Array.from({ length: n }, () => new Array(n).fill(false));
  const heap = [[grid[0][0], 0, 0]]; // Simulated Min-Heap
  visited[0][0] = true;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [t, r, c] = heap.shift();
    if (r === n - 1 && c === n - 1) return t;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && !visited[nr][nc]) {
        visited[nr][nc] = true;
        heap.push([Math.max(t, grid[nr][nc]), nr, nc]);
      }
    }
  }
  return 0;
}

💡 Find path minimizing maximum cell elevation using priority queue traversal.

Key Takeaways

Path cost is determined by max single elevation encountered.
Dijkstra expands search along globally lowest required water levels.
Time complexity $O(n^2 \log n)$.

01. Alien Dictionary

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Alien Dictionary Topological Sort implementation

02. Find Median from Data Stream

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Median Finder using Two Priority Queues

03. Binary Tree Maximum Path Sum

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Binary Tree Maximum Path Sum implementation

04. Word Ladder II

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Word Ladder II BFS + DFS implementation

05. Critical Connections in a Network (Tarjan's Bridges)

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Tarjan's Critical Connections implementation

06. Reconstruct Itinerary

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Reconstruct Itinerary Hierholzer implementation

07. Shortest Path to Get All Keys

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Shortest Path All Keys Bitmask BFS implementation

08. Trapping Rain Water II (3D Surface)

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Trapping Rain Water II 3D implementation

09. Minimum Cost to Make at Least One Valid Path in a Grid

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Minimum Cost Grid Path 0-1 BFS implementation

10. Swim in Rising Water

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Swim in Rising Water Dijkstra implementation

STAY UPDATED WITH BYTES!