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
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:
- Forward Match: Advance
i1overs1matching characters ins2viai2++. - Backward Contract: When
i2 === s2.length(full subsequence matched):- Set
end = i1. - Decrement
i1backward while contractings2indexi2--to find exact starting indexstart.
- Set
- Update Min Window: Check window length
end - start + 1against best answer. - Resume: Reset
i2 = 0and resumei1 = 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.
s1 = "abcdebdde", s2 = "bde""bcde" (len 4) and "bcdebdde" -> contracted to "bcde" and "bcde" / "bdde" (len 4)."bcde"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);
}- 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
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):
- Prefix Sum: Build
P[i] = P[i-1] + nums[i-1]of length $n + 1$. - Monotonic Deque: Store indices $i$ in
dequesuch that $P[i]$ is strictly increasing. - Loop Index $i$ from $0$ to $n$:
- Contract Left: While
P[i] - P[deque[0]] >= k, updateminLen = 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.
- Contract Left: While
Why This Approach Works Best
Handles negative numbers while finding valid sub-arrays in linear $O(n)$ time.
nums = [2,-1,2], k = 3P = [0, 2, 1, 3]. Subarray [2,-1,2] sum = P[3]-P[0] = 3.3Answer: 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;
}- 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
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:
- Row Interval Bounds: Fix top row
r1and bottom rowr2($0 \le r1 \le r2 < m$). - 1D Projection: Accumulate row values into 1D array
sums[c] += matrix[r2][c]. - Binary Search Prefix Sums:
- Maintain running sum
currSumand prefix sums in a sorted array/TreeSetset = [0]. - Find smallest
Pinsetsuch thatcurrSum - P <= k$\to$P >= currSum - k. - If found,
maxSum = Math.max(maxSum, currSum - P). - Insert
currSumintoset.
- Maintain running sum
Why This Approach Works Best
Binary search prefix sets evaluate optimal rectangle bounds in $O(m^2 \cdot n \log n)$ time.
[[1,0,1],[0,-2,3]], k = 2Rectangle [[0, 1], [-2, 3]] has sum 2 <= k.2Answer: 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;
}- 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
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:
- Prefix Sum Array:
P[i] = P[i-1] + nums[i-1]for $0 \le i \le n$. - Merge Sort Function
countWhileMergeSort(left, right):- Divide
Pinto 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.
- Divide
Why This Approach Works Best
Evaluates prefix sum pairs across splits in $O(n \log n)$ time.
nums = [-2, 5, -1], lower = -2, upper = 2Range sums [-2], [1], [2] lie in [-2, 2].3Answer: 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);
}- 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
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:
- Feasibility Check: Return
-1if(n - 1) % (k - 1) !== 0. - Prefix Sums:
pref[i]to quickly compute pile segment sums. - DP State:
dp[i][j]= minimum cost to merge pilesi...jinto as few piles as possible. - Interval Expansion Loop (
lenfromkton):- Step split point
mfromitoj-1with stridek-1:dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m+1][j]).
- If piles
i...jcan be merged down to 1 pile ((j - i) % (k - 1) === 0):dp[i][j] += pref[j+1] - pref[i].
- Step split point
Why This Approach Works Best
Interval DP systematically evaluates sub-pile combination choices in $O(n^3 / k)$ time.
stones = [3, 5, 1, 2, 6], k = 3(5 - 1) % (3 - 1) = 0 -> valid merge configuration.25Answer: 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];
}- Modulo feasibility check
(n - 1) % (k - 1) === 0validates if complete reduction is possible. - Step loop variable
mbyk - 1to skip invalid pile split states. - Interval DP executes in $O(n^3 / k)$ time.
06. Cherry Pickup II (3D Grid DP)
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:
- 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$. - Grid Cherry Addition:
- If $c_1 === c_2$, cherries gained =
grid[r][c1]. - Else, cherries gained =
grid[r][c1] + grid[r][c2].
- If $c_1 === c_2$, cherries gained =
- 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.
[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]Robot 1 moves (0,0)->(1,1)->(2,1)->(3,0). Robot 2 moves (0,2)->(1,1)->(2,2)->(3,2).24Answer: 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);
}- 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
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:
- State Definition: Queue stores
(node, bitmask, distance). - Target Bitmask: Goal mask =
(1 << n) - 1. - Queue Initialization: Push all nodes
(i, 1 << i, 0)into queue (allowing search to begin from any arbitrary node). - BFS Step:
- Pop
(curr, mask, dist). - If
mask === targetMask, returndist. - For each neighbor in
graph[curr]:newMask = mask | (1 << neighbor).- If state
(neighbor, newMask)is unvisited, mark visited and push to queue.
- Pop
Why This Approach Works Best
BFS guarantees shortest path distance while bitmasking compresses graph visitation states in $O(n \cdot 2^n)$ time.
[[1,2,3],[0],[0],[0]]1 -> 0 -> 2 -> 0 -> 3 (4 total edge steps).4Answer: 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;
}- 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)
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:
- Freq Map:
freqMap[val]stores element frequencies. - Group Map:
groupMap[freq]stores stack of elements sharing exact frequencyfreq. - Max Frequency Track: Maintain integer
maxFreq. - Operations:
push(val): IncrementfreqMap[val], updatemaxFreq = Math.max(maxFreq, freq), pushvaltogroupMap[freq].pop(): Pop elementxfromgroupMap[maxFreq]. DecrementfreqMap[x]. IfgroupMap[maxFreq]becomes empty, decrementmaxFreq--. Returnx.
Why This Approach Works Best
Grouping elements by frequency stack buckets achieves $O(1)$ constant time for both push and pop operations.
push(5), push(7), push(5), push(7), push(4), push(5), pop()5 has freq 3 (most frequent).5Answer: 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;
}
}- 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
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:
- Max-Heap: Store gas amounts of passed stations.
- 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++.
- If heap is empty: cannot reach next station $\to$ return
- Push current station's fuel onto heap.
- While current
- Return:
stopswhen 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.
target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]Refuel 60 at pos 10 (reach 70) -> Refuel 40 at pos 60 (reach 110).2Answer: 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;
}- 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)
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:
- DP Map State: Let
dp[diff]be maximum shorter stand height achievable with height differencediffbetween left and right stands. - Initialize:
dp = { 0: 0 }. - 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 staysheight. - Add to Shorter Stand:
newDiff = |diff - x|, updated height becomesheight + min(diff, x).
- Add to Taller Stand:
- 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.
rods = [1, 2, 3, 6]Left stand [1, 2, 3] = 6; Right stand [6] = 6.6Answer: 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;
}- 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.