Hard Problem Walkthroughs | Phase 5

Interactive: Trapping Rain Water — watch the two pointers work

Elevation map [0,1,0,2,1,0,1,3,2,1,2,1]. The purple aux row underneath tracks water trapped at each index so far. The side with the smaller wall is always safe to settle — that's the whole proof.

Dynamic Programming Hards

#312Burst BalloonsInterval DPHard

Think-Aloud Process

Recognize pattern: "Remove elements one at a time, order matters for cost" → Interval DP
Key insight: Think LAST balloon to burst in range [i,j], not first. If k is last in [i,j], it sees nums[i-1] * nums[k] * nums[j+1]
Define state: dp[i][j] = max coins bursting all balloons in (i,j) exclusive, where i and j are fixed boundary balloons
Recurrence: dp[i][j] = max over all k in (i,j): dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]
Build order: Iterate by increasing length of interval

C++
int maxCoins(vector<int>& nums) {
    nums.insert(nums.begin(), 1); nums.push_back(1);  // pad with 1s
    int n=nums.size();
    vector<vector<int>> dp(n, vector<int>(n,0));
    // len = length of open interval (i,j)
    for(int len=2; len<n; len++) {
        for(int i=0; i+len<n; i++) {
            int j=i+len;
            for(int k=i+1; k<j; k++) {
                dp[i][j]=max(dp[i][j],
                    dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j]);
            }
        }
    }
    return dp[0][n-1];
}
    

Time: O(n³)Space: O(n²)

#410Split Array Largest SumBinary Search on AnswerHard

Think-Aloud Process

Recognize: "Minimize the maximum" → Binary Search on Answer
Search space: lo = max(nums) (can't be smaller), hi = sum(nums) (one piece)
Feasibility check: can we split into ≤ k pieces all ≤ mid?
Greedy feasibility: greedily extend current piece until it would exceed mid, then start new piece
Binary search: if feasible(mid), try smaller; else try larger

C++
bool canSplit(vector<int>& nums, int k, int maxSum) {
    int pieces=1, cur=0;
    for(int n:nums) {
        if(cur+n>maxSum) { pieces++; cur=0; }
        cur+=n;
    }
    return pieces<=k;
}
int splitArray(vector<int>& nums, int k) {
    int lo=*max_element(nums.begin(),nums.end());
    int hi=accumulate(nums.begin(),nums.end(),0);
    while(lo<hi) {
        int mid=lo+(hi-lo)/2;
        if(canSplit(nums,k,mid)) hi=mid;
        else lo=mid+1;
    }
    return lo;
}
    

Time: O(n log(sum))Space: O(1)

Graph Hards

#127Word LadderBFS Shortest PathHard

Think-Aloud Process

Recognize: "minimum steps to reach target" → BFS shortest path
Graph model: each word is a node, edge if words differ by 1 char
Optimization: don't build explicit graph. For each word, try all 26 letters at each position and check if result is in wordList (use unordered_set)
BFS level = transformation count: return level when endWord found
Further optimization: Bidirectional BFS reduces search space to O(b^(d/2)) from O(b^d)

C++
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(),wordList.end());
    if(!wordSet.count(endWord)) return 0;
    queue<string> q;
    q.push(beginWord);
    int steps=1;
    while(!q.empty()) {
        int sz=q.size();
        while(sz--) {
            string word=q.front(); q.pop();
            if(word==endWord) return steps;
            for(int i=0;i<word.size();i++) {
                char orig=word[i];
                for(char c='a';c<='z';c++) {
                    word[i]=c;
                    if(wordSet.count(word)) { q.push(word); wordSet.erase(word); }
                }
                word[i]=orig;
            }
        }
        steps++;
    }
    return 0;
}
    

Time: O(M² × N) M=word length, N=dict sizeSpace: O(M × N)

Tree Hards

#124Binary Tree Maximum Path SumTree DFS + Global MaxHard

Think-Aloud Process

Recognize: "path through any node, not root-to-leaf" → DFS with global variable
Key insight: At each node, the path CAN bend. But a path passed UP to parent can't bend.
Two values per node: (1) best path that goes THROUGH this node (update global max), (2) best single-arm extending UP to parent
Recurrence: gainLeft = max(0, dfs(left)), gainRight = max(0, dfs(right)). Through = node.val + gainLeft + gainRight. Return = node.val + max(gainLeft, gainRight)

C++
int maxPath;
int dfs(TreeNode* node) {
    if(!node) return 0;
    int L=max(0,dfs(node->left));
    int R=max(0,dfs(node->right));
    maxPath=max(maxPath, node->val+L+R);  // path through this node
    return node->val+max(L,R);            // arm going up to parent
}
int maxPathSum(TreeNode* root) {
    maxPath=INT_MIN;
    dfs(root);
    return maxPath;
}
    

Time: O(n)Space: O(h) recursion stack

#297Serialize and Deserialize Binary TreeTree BFS / DFSHard

Think-Aloud Process

Recognize: Need to encode tree as string and decode back exactly
Approach: Preorder DFS with null markers. "1,2,#,#,3,#,#" — when we see '#', it's null
Serialize: preorder DFS, write value or "#", comma-separated
Deserialize: parse tokens into queue, recursively build: pop front → if "#" return null, else create node and recurse left, right

C++
string serialize(TreeNode* root) {
    if(!root) return "#,";
    return to_string(root->val)+","+serialize(root->left)+serialize(root->right);
}
TreeNode* build(queue<string>& q) {
    string tok=q.front(); q.pop();
    if(tok=="#") return nullptr;
    TreeNode* node=new TreeNode(stoi(tok));
    node->left=build(q);
    node->right=build(q);
    return node;
}
TreeNode* deserialize(string data) {
    queue<string> q;
    string cur;
    for(char c:data) {
        if(c==',') { q.push(cur); cur=""; }
        else cur+=c;
    }
    return build(q);
}
    

Time: O(n)Space: O(n)

Array Hards

#42Trapping Rain WaterTwo PointersHard

Think-Aloud Process

Key insight: Water at position i = min(maxLeft[i], maxRight[i]) - height[i]
Naive: precompute maxLeft and maxRight arrays, O(n) time, O(n) space
Optimize to O(1) space: Two pointers. The side with smaller max determines water level.
Two pointer: lo=0, hi=n-1. Track maxL, maxR. If maxL ≤ maxR: water at lo = maxL - h[lo], move lo right. Else: water at hi = maxR - h[hi], move hi left.

C++
int trap(vector<int>& h) {
    int lo=0, hi=h.size()-1;
    int maxL=0, maxR=0, res=0;
    while(lo<hi) {
        if(h[lo]<=h[hi]) {
            maxL=max(maxL,h[lo]);
            res+=maxL-h[lo++];
        } else {
            maxR=max(maxR,h[hi]);
            res+=maxR-h[hi--];
        }
    }
    return res;
}
    

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

#239Sliding Window MaximumMonotonic DequeHard

Think-Aloud Process

Naive: For each window of size k, find max. O(nk) — too slow.
Key insight: Use monotonic decreasing deque. When we add a new element, all smaller elements in deque can never be the maximum for future windows.
Maintain deque: Keep indices. Pop back while deque.back() ≤ current. Pop front if out of window.
Front of deque = max of current window.

C++
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // stores indices, decreasing values
    vector<int> res;
    for(int i=0;i<nums.size();i++) {
        if(!dq.empty() && dq.front()<=i-k) dq.pop_front();  // out of window
        while(!dq.empty() && nums[dq.back()]<=nums[i]) dq.pop_back();  // prune smaller
        dq.push_back(i);
        if(i>=k-1) res.push_back(nums[dq.front()]);
    }
    return res;
}
    

Time: O(n)Space: O(k)

Design Hards

#295Find Median from Data StreamTwo HeapsHard

Think-Aloud Process

Recognize: "stream" + "median at any time" → can't sort per query (O(n log n) each). Need an incremental structure → Two Heaps.
Key insight: The median only cares about the boundary between the lower half and upper half. Keep a max-heap lo of the smaller half and a min-heap hi of the larger half — both tops ARE the boundary.
Invariants: every element of lo ≤ every element of hi, and |size(lo) − size(hi)| ≤ 1 (lo may hold one extra).
Insert: push into lo, move lo's top to hi (fixes ordering), then if hi got bigger, move hi's top back (fixes sizes). Always exactly 3 heap ops.
Median: odd count → lo.top(); even → average of the two tops. O(1).

C++
class MedianFinder {
    priority_queue<int> lo;                                // max-heap, smaller half
    priority_queue<int,vector<int>,greater<int>> hi;      // min-heap, larger half
public:
    void addNum(int num) {
        lo.push(num);                // 1. into lower half
        hi.push(lo.top()); lo.pop(); // 2. largest of lower → upper (restores order)
        if(hi.size() > lo.size()) {  // 3. rebalance sizes
            lo.push(hi.top()); hi.pop();
        }
    }
    double findMedian() {
        if(lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};
    

Dry Run · stream 5, 2, 8, 3

add 5: lo={5}, hi={} → median 5
add 2: lo push 2 → top 5 moves to hi → lo={2}, hi={5} → median (2+5)/2 = 3.5
add 8: lo push 8 → top 8 moves to hi → hi bigger → 5 comes back → lo={5,2}, hi={8} → median 5
add 3: lo push 3 → top 5 moves to hi → hi bigger → 5 comes back → lo={3,2}, hi={5,8} → median (3+5)/2 = 4 ✓

Time: O(log n) add, O(1) medianSpace: O(n)