Lab 04 — Optimization Pathway

Goal

Train the explicit transition from brute force to optimal: identify what the brute force wastes (repeated work, missed monotonicity, overlooked sortedness), then close that gap with a specific technique.

Background Concepts

The optimization checklist (canonical):

  1. Repeated work → memoize / DP
  2. Sortedness → two pointers, binary search, sweep line
  3. Monotonicity → binary search on answer
  4. Local + global structure → sliding window, prefix sums
  5. Pattern match to known DS → heap, monotonic stack/queue, segment tree, trie, union find
  6. State compression → bitmask, hash of state
  7. Math closed form → combinatorics, modular arithmetic, geometry
  8. Graph modeling → BFS/DFS/Dijkstra/topo even on non-graph problems
  9. Randomization / hashing → reservoir sampling, rolling hash
  10. Approximation / amortization → when exact O(N) is hard, amortize

Interview Context

The interviewer wants to see your thinking process during optimization, not just the answer. Narrate: “The brute is O(N^2) because we recompute the prefix sum on every iteration. If we precompute prefix sums once, each query is O(1) and total is O(N).”

Problem Statement

For each of the 7 brute force descriptions below, identify which optimization checklist item applies, and produce a one-paragraph optimized approach.

Problems:

  1. Brute: for each i, sum a[i..j] for all j; O(N^2). Goal: answer multiple range-sum queries.
  2. Brute: for each pair (i, j), check if a[i] + a[j] = target; O(N^2). Goal: find pair sum.
  3. Brute: generate all subsets, count those with sum K; O(2^N). N up to 30. Goal: count.
  4. Brute: for each query (l, r), find min in a[l..r]; O(N) per query, N queries → O(N^2). Goal: range min queries on static array.
  5. Brute: simulate game state recursively; many overlapping subproblems; O(2^depth). Goal: optimal game value.
  6. Brute: for each i, find next j > i with a[j] > a[i]; O(N^2). Goal: next-greater-element array.
  7. Brute: binary search would work if we knew the answer was in [L, R]. The answer is monotonic in some parameter. O(N · K) brute. Goal: find min K satisfying property.

Constraints

Assume N ≤ 10^5 for #1, #2, #4, #6, #7. N ≤ 30 for #3, allowing 2^N/2 meet-in-the-middle. N is the state-space size for #5.

Clarifying Questions

  • “Are queries online or offline?” — offline allows different algorithms (Mo’s, offline BIT)
  • “Is the array static or updated?” — static allows sparse table, dynamic needs Fenwick / segment tree

Examples

#1: prefix sums → query in O(1). #7: monotonic predicate → binary search the answer in O(log range).

Initial Brute Force

As stated above per problem.

Brute Force Complexity

As stated.

Optimization Path

For each problem, write the checklist item that applies and the optimized approach:

  1. Sortedness / static structure: prefix sums → O(N) preprocess, O(1) query
  2. Sortedness / hashing: hashmap of target - a[i] → O(N)
  3. State compression: subset-sum DP O(N · K), or meet-in-the-middle O(2^(N/2)) → fits N=30
  4. Pattern → known DS: sparse table O(N log N) preprocess, O(1) query (static); segment tree if dynamic
  5. Repeated work: memoization → O(unique states)
  6. Pattern → monotonic stack: O(N)
  7. Monotonicity: binary search on answer → O(log range × verify)

Final Expected Approach

For your deliverable: each of the 7 problems gets:

  • Checklist item identified
  • Optimized algorithm
  • Final complexity
  • One-line reasoning

Data Structures Used

  • Prefix sum array
  • Hashmap
  • DP table / memo dict
  • Sparse table (immutable RMQ) / segment tree
  • Monotonic stack
  • (Binary search needs no DS)

Correctness Argument

For each optimization, the correctness argument is “the brute force result is preserved because X”:

  • Prefix sums: sum(l..r) = prefix[r+1] - prefix[l] — algebraic identity
  • Hashmap pair sum: every pair (i, j) with i < j is examined exactly once when we process j and look up target - a[j]
  • Subset-sum DP: state (i, sum) covers all subsets of a[0..i] with given sum
  • Sparse table: range min over a range of length L is min(table[k][l], table[k][r - 2^k + 1]) where k = log2(L) — overlap is fine because min is idempotent
  • Memoization: same input → same output → cached
  • Monotonic stack: pop while top is not greater than current; top after popping is the next-greater for popped elements
  • Binary search on answer: predicate is monotonic by problem assumption

Complexity

Stated per problem.

Implementation Requirements

Implement #1, #2, #6 in your preferred language. Verify against brute force on random small inputs.

Tests

  • Smoke: given example
  • Edge: empty, single
  • Random: 50 random tests against brute force; on mismatch, dump input
  • Large: stress test at constraint maximum, time it

Follow-up Questions

  • For #1: what if the array is updated? → Fenwick tree
  • For #2: what if k-sum (k > 2)? → recurse to (k-1)-sum with target adjustment, or sort + multi-pointer
  • For #4: what about range max? Range gcd? Range sum? → which are idempotent (sparse table) vs which need segment tree
  • For #6: what about previous greater? Next smaller? → mirror the stack
  • For #7: what about minimum fractional answer? → binary search on real numbers with precision

Product Extension

The optimization checklist is a real code-review tool. When reviewing a colleague’s PR with O(N^2) in a hot path, run through this checklist mentally. 80% of N^2 → N transitions are one of: prefix sum, hashmap, sort + two-pointer, monotonic stack.

Language/Runtime Follow-ups

  • Python: prefix-sum approach gets a 5–10× speedup if you use NumPy np.cumsum instead of Python list.
  • Java: monotonic stack with Deque<Integer> (autoboxing) is slower than a plain int[] with manual top index.
  • C++: std::lower_bound / upper_bound give log-N binary search on sorted vectors with no manual implementation.
  • JavaScript: Map is generally faster than plain object for hashmap when keys are non-string.

Common Bugs

  • Prefix sum: off-by-one in prefix[r+1] - prefix[l]
  • Two-pointer: forgetting to advance one pointer
  • DP: wrong base case or wrong evaluation order
  • Sparse table: log table off-by-one
  • Monotonic stack: comparing > vs >= for the next-greater-or-equal variant
  • Binary search on answer: monotonicity direction reversed

Debugging Strategy

For each optimization, do stress testing: write brute, write optimal, run on 100 random small inputs, compare outputs. This catches off-by-one bugs that survive the given tests.

Deliverable

  1. The 7-problem structured analysis
  2. Real implementation + tests for #1, #2, #6
  3. A reflection paragraph: for which problem was the optimization checklist most useful? Was there a problem where you’d’ve gone the wrong direction without it?

Mastery Criteria

  • Correctly identified the optimization checklist item for all 7
  • Implemented #1, #2, #6 with passing tests including stress
  • Can explain why each optimization preserves correctness, not just that it’s faster
  • Found at least 1 bug via stress testing (good — that’s the point)