HomeBytesheetsRoadmapsUI TemplatesUI ToolsStack Discussion
10 Topics
Chapter•360 Minutes

Hard DSA — Special Substrings, Monotonic Deques & Advanced DP

Master non-contiguous string matching, monotonic sub-array boundary calculations, prefix tree search optimizations, and multi-dimensional grid DP.

01. Minimum Window Subsequence

Difficulty:HardPattern:Two Pointers Contract ScanTime:O(|s1| * |s2|)Space:O(1)

Given strings s1 and s2, return the minimum contiguous substring $W$ of s1 such that s2 is a subsequence of $W$.

How It Works & Algorithmic Design

Solves using Two-Pointer Forward Match and Backward Contract Expansion:

  1. Forward Match: Advance i1 over s1 matching characters in s2 via i2++.
  2. Backward Contract: When i2 === s2.length (full subsequence matched):
    • Set end = i1.
    • Decrement i1 backward while contracting s2 index i2-- to find exact starting index start.
  3. Update Min Window: Check window length end - start + 1 against best answer.
  4. Resume: Reset i2 = 0 and resume i1 = start + 1.

Why This Approach Works Best

Combines forward scanning with backward contraction to evaluate optimal windows in $O(|s1| \times |s2|)$ time and $O(1)$ space.

Example Walkthrough
Input: s1 = "abcdebdde", s2 = "bde"
Target subsequence.
Matching Windows: "bcde" (len 4) and "bcdebdde" -> contracted to "bcde" and "bcde" / "bdde" (len 4).
Subsequence substrings.
Output: "bcde"
Shortest substring.

Answer: Minimum Window Subsequence implementation

function minWindow(s1, s2) {
  let i1 = 0, i2 = 0;
  let minLen = Infinity, startIdx = -1;
  while (i1 < s1.length) {
    if (s1[i1] === s2[i2]) {
      i2++;
      if (i2 === s2.length) {
        let end = i1;
        i2--;
        while (i2 >= 0) {
          if (s1[i1] === s2[i2]) i2--;
          i1--;
        }
        i1++;
        if (end - i1 + 1 < minLen) {
          minLen = end - i1 + 1;
          startIdx = i1;
        }
        i2 = 0;
      }
    }
    i1++;
  }
  return startIdx === -1 ? '' : s1.substring(startIdx, startIdx + minLen);
}
💡 Match sequence characters forward and shrink window backward to locate minimal length sub-strings.
Key Takeaways
  • Forward scan finds complete subsequence matches.
  • Backward contraction pinpoints the minimal left boundary.
  • Runs in $O(|s1| \times |s2|)$ time and $O(1)$ extra space.

02. Shortest Subarray with Sum at Least K

Difficulty:HardPattern:Prefix Sum + Monotonic DequeTime:O(n)Space:O(n)

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k.

How It Works & Algorithmic Design

Solves using Prefix Sum Array + Monotonic Double-Ended Queue (Deque):

  1. Prefix Sum: Build P[i] = P[i-1] + nums[i-1] of length $n + 1$.
  2. Monotonic Deque: Store indices $i$ in deque such that $P[i]$ is strictly increasing.
  3. Loop Index $i$ from $0$ to $n$:
    • Contract Left: While P[i] - P[deque[0]] >= k, update minLen = Math.min(minLen, i - deque.shift()).
    • Maintain Monotonicity: While P[i] <= P[deque[last]], pop back (a smaller prefix sum at a larger index is always a better left boundary choice).
    • Push $i$ onto deque.

Why This Approach Works Best

Handles negative numbers while finding valid sub-arrays in linear $O(n)$ time.

Example Walkthrough
Input: nums = [2,-1,2], k = 3
Target sum 3 with negative values.
Prefix Sums: P = [0, 2, 1, 3]. Subarray [2,-1,2] sum = P[3]-P[0] = 3.
Length 3 subarray.
Output: 3
Shortest subarray length.

Answer: Shortest Subarray with Sum at Least K implementation

function shortestSubarray(nums, k) {
  const n = nums.length;
  const P = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
  let minLen = Infinity;
  const deque = [];
  for (let i = 0; i <= n; i++) {
    while (deque.length && P[i] - P[deque[0]] >= k) {
      minLen = Math.min(minLen, i - deque.shift());
    }
    while (deque.length && P[i] <= P[deque[deque.length - 1]]) {
      deque.pop();
    }
    deque.push(i);
  }
  return minLen === Infinity ? -1 : minLen;
}
💡 Maintain monotonically increasing prefix sum indices in a deque to query minimal subarray lengths.
Key Takeaways
  • Works with negative array numbers unlike simple two-pointer sliding windows.
  • Popping larger prefix sums maintains monotonic deque structure.
  • Executes in $O(n)$ time.

03. Max Sum of Rectangle No Larger Than K

Difficulty:HardPattern:2D Interval + Prefix Binary SearchTime:O(m^2 * n log n)Space:O(n)

Given an $m \times n$ matrix and an integer $k$, return the max sum of a rectangle in the matrix such that its sum is no larger than $k$.

How It Works & Algorithmic Design

Solves using 1D Sub-Array Projection with Sorted Binary Search TreeSet:

  1. Row Interval Bounds: Fix top row r1 and bottom row r2 ($0 \le r1 \le r2 < m$).
  2. 1D Projection: Accumulate row values into 1D array sums[c] += matrix[r2][c].
  3. Binary Search Prefix Sums:
    • Maintain running sum currSum and prefix sums in a sorted array/TreeSet set = [0].
    • Find smallest P in set such that currSum - P <= k $\to$ P >= currSum - k.
    • If found, maxSum = Math.max(maxSum, currSum - P).
    • Insert currSum into set.

Why This Approach Works Best

Binary search prefix sets evaluate optimal rectangle bounds in $O(m^2 \cdot n \log n)$ time.

Example Walkthrough
Input Matrix: [[1,0,1],[0,-2,3]], k = 2
Matrix and target bound k.
Max Sub-matrix: Rectangle [[0, 1], [-2, 3]] has sum 2 <= k.
Bounded rectangle sum.
Output: 2
Max sum <= k.

Answer: Max Sum Rectangle No Larger Than K implementation

function maxSumSubmatrix(matrix, k) {
  const m = matrix.length, n = matrix[0].length;
  let maxSum = -Infinity;
  for (let l = 0; l < n; l++) {
    const rowSums = new Array(m).fill(0);
    for (let r = l; r < n; r++) {
      for (let i = 0; i < m; i++) rowSums[i] += matrix[i][r];
      const set = [0];
      let curr = 0;
      for (const sum of rowSums) {
        curr += sum;
        // Binary search for smallest val >= curr - k
        const target = curr - k;
        let low = 0, high = set.length - 1, match = -1;
        while (low <= high) {
          const mid = Math.floor((low + high) / 2);
          if (set[mid] >= target) { match = set[mid]; high = mid - 1; }
          else low = mid + 1;
        }
        if (match !== -1) maxSum = Math.max(maxSum, curr - match);
        // Insert curr in sorted array
        let pos = 0;
        while (pos < set.length && set[pos] < curr) pos++;
        set.splice(pos, 0, curr);
      }
    }
  }
  return maxSum;
}
💡 Compress matrix rows into 1D arrays and find maximum bounded sums using binary search prefix sets.
Key Takeaways
  • Converts 2D sub-matrix search into 1D prefix arrays.
  • Uses binary search (ceiling) to find sub-array sums $\le k$.
  • Runs in $O(m^2 \cdot n \log n)$ time.

04. Count of Range Sum

Difficulty:HardPattern:Prefix Sum + Merge SortTime:O(n log n)Space:O(n)

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

How It Works & Algorithmic Design

Solves using Prefix Sum Array + Modified Merge Sort:

  1. Prefix Sum Array: P[i] = P[i-1] + nums[i-1] for $0 \le i \le n$.
  2. Merge Sort Function countWhileMergeSort(left, right):
    • Divide P into left and right halves.
    • For each element $P[i]$ in left half, find two pointers $j$ and $k$ in right half such that $P[j] - P[i] \ge \text{lower}$ and $P[k] - P[i] > \text{upper}$.
    • Accumulate valid range count: count += (k - j).
    • Perform standard merge step to keep prefix sub-array sorted.

Why This Approach Works Best

Evaluates prefix sum pairs across splits in $O(n \log n)$ time.

Example Walkthrough
Input: nums = [-2, 5, -1], lower = -2, upper = 2
Target range [-2, 2].
Valid Ranges: Range sums [-2], [1], [2] lie in [-2, 2].
3 valid ranges.
Output: 3
Matching count.

Answer: Count of Range Sum implementation

function countRangeSum(nums, lower, upper) {
  const n = nums.length;
  const P = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
  function mergeSort(left, right) {
    if (right - left <= 1) return 0;
    const mid = Math.floor((left + right) / 2);
    let count = mergeSort(left, mid) + mergeSort(mid, right);
    let j = mid, k = mid;
    for (let i = left; i < mid; i++) {
      while (j < right && P[j] - P[i] < lower) j++;
      while (k < right && P[k] - P[i] <= upper) k++;
      count += k - j;
    }
    const sorted = [];
    let l = left, r = mid;
    while (l < mid && r < right) {
      if (P[l] <= P[r]) sorted.push(P[l++]);
      else sorted.push(P[r++]);
    }
    while (l < mid) sorted.push(P[l++]);
    while (r < right) sorted.push(P[r++]);
    for (let i = 0; i < sorted.length; i++) P[left + i] = sorted[i];
    return count;
  }
  return mergeSort(0, n + 1);
}
💡 Count prefix sum differences within [lower, upper] boundaries using two pointers during Merge Sort.
Key Takeaways
  • Converts range sums to prefix differences $P[j] - P[i]$.
  • Pointers $j$ and $k$ move monotonically during merge sort.
  • Optimal execution time $O(n \log n)$.

05. Minimum Cost to Merge Stones

Difficulty:HardPattern:Interval Dynamic ProgrammingTime:O(n^3 / k)Space:O(n^2)

There are n piles of stones arranged in a row. A move consists of merging exactly k consecutive piles into one pile. Return the minimum cost to merge all piles into one pile.

How It Works & Algorithmic Design

Solves using Interval Dynamic Programming with Pile Group Reductions:

  1. Feasibility Check: Return -1 if (n - 1) % (k - 1) !== 0.
  2. Prefix Sums: pref[i] to quickly compute pile segment sums.
  3. DP State: dp[i][j] = minimum cost to merge piles i...j into as few piles as possible.
  4. Interval Expansion Loop (len from k to n):
    • Step split point m from i to j-1 with stride k-1:
      • dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m+1][j]).
    • If piles i...j can be merged down to 1 pile ((j - i) % (k - 1) === 0):
      • dp[i][j] += pref[j+1] - pref[i].

Why This Approach Works Best

Interval DP systematically evaluates sub-pile combination choices in $O(n^3 / k)$ time.

Example Walkthrough
Input: stones = [3, 5, 1, 2, 6], k = 3
5 stone piles, merge 3 at a time.
Feasibility: (5 - 1) % (3 - 1) = 0 -> valid merge configuration.
Possible to merge to 1 pile.
Output: 25
Minimum merge cost.

Answer: Minimum Cost to Merge Stones implementation

function mergeStones(stones, k) {
  const n = stones.length;
  if ((n - 1) % (k - 1) !== 0) return -1;
  const pref = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + stones[i];
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = k; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;
      for (let m = i; m < j; m += k - 1) {
        dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
      }
      if ((j - i) % (k - 1) === 0) {
        dp[i][j] += pref[j + 1] - pref[i];
      }
    }
  }
  return dp[0][n - 1];
}
💡 Interval dynamic programming evaluating consecutive sub-pile merges.
Key Takeaways
  • Modulo feasibility check (n - 1) % (k - 1) === 0 validates if complete reduction is possible.
  • Step loop variable m by k - 1 to skip invalid pile split states.
  • Interval DP executes in $O(n^3 / k)$ time.

06. Cherry Pickup II (3D Grid DP)

Difficulty:HardPattern:3D Grid DPTime:O(R * C^2)Space:O(R * C^2)

You are given a rows x cols matrix grid. You have two robots: Robot 1 starts at (0, 0) and Robot 2 starts at (0, cols - 1). Return the maximum cherries collected by both robots.

How It Works & Algorithmic Design

Solves using 3D Simultaneous Grid Dynamic Programming:

  1. DP State: Let dp[r][c1][c2] be max cherries collected at row $r$ with Robot 1 at column $c_1$ and Robot 2 at column $c_2$.
  2. Grid Cherry Addition:
    • If $c_1 === c_2$, cherries gained = grid[r][c1].
    • Else, cherries gained = grid[r][c1] + grid[r][c2].
  3. Transition: For each candidate column move $(dc_1, dc_2) \in {-1, 0, 1}^2$:
    • dp[r][c1][c2] = cherry + max(dp[r+1][c1+dc1][c2+dc2]).

Why This Approach Works Best

Saves $O(2^R)$ exponential path choices by moving both robots simultaneously down row $r$ in $O(R \cdot C^2)$ time.

Example Walkthrough
Input Grid: [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
4x3 grid.
Dual Paths: Robot 1 moves (0,0)->(1,1)->(2,1)->(3,0). Robot 2 moves (0,2)->(1,1)->(2,2)->(3,2).
Optimized cherry collection paths.
Output: 24
Max total cherries.

Answer: Cherry Pickup II 3D DP implementation

function cherryPickup(grid) {
  const rows = grid.length, cols = grid[0].length;
  const memo = Map();
  function dfs(r, c1, c2) {
    if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return -Infinity;
    if (r === rows) return 0;
    const key = `${r},${c1},${c2}`;
    if (memo.has(key)) return memo.get(key);
    let cherries = c1 === c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2];
    let maxNext = -Infinity;
    for (let d1 = -1; d1 <= 1; d1++) {
      for (let d2 = -1; d2 <= 1; d2++) {
        maxNext = Math.max(maxNext, dfs(r + 1, c1 + d1, c2 + d2));
      }
    }
    const res = cherries + maxNext;
    memo.set(key, res);
    return res;
  }
  return dfs(0, 0, cols - 1);
}
💡 Advance both robots row by row, memoizing state using 3D dynamic programming grid.
Key Takeaways
  • Traversing both robots row by row simplifies state matching.
  • Handles cell overlaps using $c_1 === c_2$ check.
  • Runs in $O(R \cdot C^2)$ space and time.

07. Shortest Path Visiting All Nodes

Difficulty:HardPattern:Bitmask BFS State SearchTime:O(n * 2^n)Space:O(n * 2^n)

You have an undirected connected graph of n nodes. Return the length of the shortest path that visits every node.

How It Works & Algorithmic Design

Solves using BFS State Traversal with Bitmasking:

  1. State Definition: Queue stores (node, bitmask, distance).
  2. Target Bitmask: Goal mask = (1 << n) - 1.
  3. Queue Initialization: Push all nodes (i, 1 << i, 0) into queue (allowing search to begin from any arbitrary node).
  4. BFS Step:
    • Pop (curr, mask, dist).
    • If mask === targetMask, return dist.
    • For each neighbor in graph[curr]:
      • newMask = mask | (1 << neighbor).
      • If state (neighbor, newMask) is unvisited, mark visited and push to queue.

Why This Approach Works Best

BFS guarantees shortest path distance while bitmasking compresses graph visitation states in $O(n \cdot 2^n)$ time.

Example Walkthrough
Input Graph: [[1,2,3],[0],[0],[0]]
4 node star graph.
Optimal Route: 1 -> 0 -> 2 -> 0 -> 3 (4 total edge steps).
Visits all nodes.
Output: 4
Shortest path length.

Answer: Shortest Path Visiting All Nodes implementation

function shortestPathLength(graph) {
  const n = graph.length;
  const targetMask = (1 << n) - 1;
  const queue = [];
  const visited = new Set();
  for (let i = 0; i < n; i++) {
    const mask = 1 << i;
    queue.push([i, mask, 0]);
    visited.add(`${i},${mask}`);
  }
  while (queue.length) {
    const [node, mask, dist] = queue.shift();
    if (mask === targetMask) return dist;
    for (const neighbor of graph[node]) {
      const nextMask = mask | (1 << neighbor);
      const state = `${neighbor},${nextMask}`;
      if (!visited.has(state)) {
        visited.add(state);
        queue.push([neighbor, nextMask, dist + 1]);
      }
    }
  }
  return 0;
}
💡 BFS search tracking visited nodes via bitmask to find shortest path covering all graph vertices.
Key Takeaways
  • Initialize BFS with all nodes to test every starting point.
  • Bitmask state representation compresses node visitation sets.
  • Runs in $O(n \cdot 2^n)$ time.

08. Maximum Frequency Stack (FreqStack)

Difficulty:HardPattern:Frequency Map Stack BucketTime:O(1) Push / PopSpace:O(n)

Design a stack-like data structure that pushes and pops elements, where pop removes and returns the most frequent element in the stack. If there is a tie, the element closest to the top of the stack is popped.

How It Works & Algorithmic Design

Solves using Hash Map Frequency Counters + Stack Map Buckets:

  1. Freq Map: freqMap[val] stores element frequencies.
  2. Group Map: groupMap[freq] stores stack of elements sharing exact frequency freq.
  3. Max Frequency Track: Maintain integer maxFreq.
  4. Operations:
    • push(val): Increment freqMap[val], update maxFreq = Math.max(maxFreq, freq), push val to groupMap[freq].
    • pop(): Pop element x from groupMap[maxFreq]. Decrement freqMap[x]. If groupMap[maxFreq] becomes empty, decrement maxFreq--. Return x.

Why This Approach Works Best

Grouping elements by frequency stack buckets achieves $O(1)$ constant time for both push and pop operations.

Example Walkthrough
Operations: push(5), push(7), push(5), push(7), push(4), push(5), pop()
FreqStack calls.
Frequency State: 5 has freq 3 (most frequent).
Pops 5.
Output: 5
Popped most frequent element.

Answer: FreqStack implementation

class FreqStack {
  constructor() {
    this.freq = new Map();
    this.group = new Map();
    this.maxFreq = 0;
  }
  push(val) {
    const f = (this.freq.get(val) || 0) + 1;
    this.freq.set(val, f);
    this.maxFreq = Math.max(this.maxFreq, f);
    if (!this.group.has(f)) this.group.set(f, []);
    this.group.get(f).push(val);
  }
  pop() {
    const stack = this.group.get(this.maxFreq);
    const val = stack.pop();
    this.freq.set(val, this.freq.get(val) - 1);
    if (stack.length === 0) this.maxFreq--;
    return val;
  }
}
💡 Group elements in stack buckets indexed by frequency count for constant O(1) pops.
Key Takeaways
  • Maintains frequency mapping alongside stack bucket structures.
  • Tie breaking defaults automatically to LIFO order inside frequency stacks.
  • All operations execute in constant $O(1)$ time.

09. Minimum Number of Refueling Stops

Difficulty:HardPattern:Greedy Max-Heap Priority SearchTime:O(n log n)Space:O(n)

A car travels to target starting with startFuel liters. Along the way are gas stations where stations[i] = [position, fuel]. Return the minimum number of refueling stops to reach target.

How It Works & Algorithmic Design

Solves using Greedy Max-Heap Fuel Selection:

  1. Max-Heap: Store gas amounts of passed stations.
  2. Traversal: Loop through stations plus target position:
    • While current maxReach < station.position:
      • If heap is empty: cannot reach next station $\to$ return -1.
      • Pop largest available gas amount from heap: maxReach += maxHeap.pop(), stops++.
    • Push current station's fuel onto heap.
  3. Return: stops when target reached.

Why This Approach Works Best

Greedily refueling at the largest passed gas stations maximizes distance gained per stop in $O(n \log n)$ time.

Example Walkthrough
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Target and gas stations.
Greedy Stops: Refuel 60 at pos 10 (reach 70) -> Refuel 40 at pos 60 (reach 110).
2 total stops.
Output: 2
Minimum fuel stops.

Answer: Minimum Number of Refueling Stops implementation

function minRefuelStops(target, startFuel, stations) {
  const heap = []; // Max-Heap simulated
  let maxReach = startFuel, stops = 0, idx = 0;
  while (maxReach < target) {
    while (idx < stations.length && stations[idx][0] <= maxReach) {
      heap.push(stations[idx][1]);
      heap.sort((a, b) => b - a);
      idx++;
    }
    if (heap.length === 0) return -1;
    maxReach += heap.shift();
    stops++;
  }
  return stops;
}
💡 Greedily consume maximum available fuel from passed stations using a Max-Heap.
Key Takeaways
  • Store passed gas stations in Max-Heap instead of stopping immediately.
  • Pop largest fuel amount when current range cannot reach next milestone.
  • Executes in $O(n \log n)$ time.

10. Tallest Billboard (Difference State DP)

Difficulty:HardPattern:Difference State Dynamic ProgrammingTime:O(N * S)Space:O(S)

You are installing a billboard and want it to have the largest possible height. You have a collection of rods that can be welded together. Return the maximum possible height of your billboard installation.

How It Works & Algorithmic Design

Solves using Height Difference Dynamic Programming:

  1. DP Map State: Let dp[diff] be maximum shorter stand height achievable with height difference diff between left and right stands.
  2. Initialize: dp = { 0: 0 }.
  3. Rod Addition (For each rod $x$):
    • Copy current state map.
    • For each (diff, height) in current DP state:
      • Add to Taller Stand: newDiff = diff + x, updated height stays height.
      • Add to Shorter Stand: newDiff = |diff - x|, updated height becomes height + min(diff, x).
  4. Return: dp[0] (max height when left and right stands are equal).

Why This Approach Works Best

Keying states by height difference $\Delta$ compresses search complexity to $O(N \cdot S)$ time.

Example Walkthrough
Input: rods = [1, 2, 3, 6]
Available rod lengths.
Matched Stands: Left stand [1, 2, 3] = 6; Right stand [6] = 6.
Equal height stand pairs.
Output: 6
Max billboard height.

Answer: Tallest Billboard implementation

function tallestBillboard(rods) {
  let dp = new Map([[0, 0]]);
  for (const x of rods) {
    const copy = new Map(dp);
    for (const [diff, height] of copy) {
      // Option 1: Add to taller stand
      dp.set(diff + x, Math.max(dp.get(diff + x) || 0, height));
      // Option 2: Add to shorter stand
      const newDiff = Math.abs(diff - x);
      const newHeight = height + Math.min(diff, x);
      dp.set(newDiff, Math.max(dp.get(newDiff) || 0, newHeight));
    }
  }
  return dp.get(0) || 0;
}
💡 Maintain dynamic programming map tracking maximum stand height keyed by stand difference.
Key Takeaways
  • Keys dynamic state map by stand height difference $\Delta$.
  • Value stores maximum shorter stand height.
  • Final result is dp[0] where height difference is 0.