Lab 03 — Brute Force First

Goal

Internalize the discipline of always producing a brute force before optimizing — even when the optimal is obvious. The brute force is your correctness oracle, your fallback, and your communication anchor.

Background Concepts

  • Brute force as a baseline: it must be correct, even if slow
  • Brute force as oracle: cross-check optimal output with brute on random small inputs
  • Brute force as recovery: when stuck, you have something to deliver

Interview Context

Many candidates hear a problem, immediately recognize the optimal pattern, and start coding. The interviewer can’t tell whether they understand the problem or just memorized the answer. State the brute force first, even if it takes 30 seconds. Then, “I see this can be optimized to O(N log N) using … — would you like me to go straight to that, or step through a middle approach?”

Problem Statement

For each of the 5 problems below, in 10 minutes total:

  1. State the brute force in pseudocode
  2. State its complexity
  3. State the optimization path (one or two sentences)

Problems:

  1. Two Sum: find indices i, j such that a[i] + a[j] == target
  2. Maximum Subarray: maximum sum contiguous subarray
  3. Longest Substring Without Repeating Characters
  4. Trapping Rain Water: given heights, total water trapped
  5. Median Of Two Sorted Arrays

Constraints

For each problem, assume N ≤ 10^5 for sizing.

Clarifying Questions

For each problem, ask: “Are we returning the value or the actual subarray/indices?” — this affects implementation but not the brute-force complexity.

Examples

For Two Sum, brute is for i: for j > i: if a[i] + a[j] == target: return [i,j]. Test on [2,7,11,15], target=9 → [0,1].

Initial Brute Force

Per problem:

  1. Two Sum: O(N^2) double loop
  2. Maximum Subarray: O(N^3) — three nested loops (i, j, sum) — or O(N^2) with running sum
  3. Longest Substring No Repeat: O(N^2) or O(N^3) — for each pair (i, j), check if substring has duplicates (set construction is O(N) per pair, so O(N^3))
  4. Trapping Rain Water: O(N^2) — for each index, find max-left and max-right by scanning
  5. Median Of Two Sorted Arrays: O(N+M) — merge then take median; even simpler O((N+M) log(N+M)) — concatenate + sort

Brute Force Complexity

As listed above. Be explicit about which O(N^k) you mean.

Optimization Path

  1. Two Sum: Hashmap of seen values → O(N).
  2. Maximum Subarray: Kadane’s running sum, reset to 0 if negative → O(N).
  3. Longest Substring No Repeat: Sliding window with hashset → O(N).
  4. Trapping Rain Water: Two-pointer with running max-left, max-right → O(N); or precompute prefix/suffix max → O(N) space.
  5. Median Of Two Sorted Arrays: Binary search on partition → O(log min(N,M)).

Final Expected Approach

In the deliverable, write:

Problem K:
  Brute force pseudocode: ...
  Brute complexity: O(...)
  Optimization sketch: <pattern> → O(...)
  Why the optimization works (1 sentence)

Data Structures Used

For each problem, identify the diff between brute force DS and optimized DS — that diff is usually where the optimization lives.

Correctness Argument

For brute force, correctness is by exhaustive enumeration — usually trivial. For the optimized version, the correctness lives in why exhaustive enumeration is unnecessary (e.g., “if a[i] is the answer’s left half, then target - a[i] must be in the seen set”).

Complexity

Stated per problem above.

Implementation Requirements

For this lab, write the brute force only for problems 1, 2, 3 in your preferred language. Run on the given examples. Do not write the optimal version. The exercise is to make the brute force a habit.

Tests

For each implemented brute force:

  • Smoke: 1 given example
  • Edge: empty / single
  • Random: 10 random small inputs (N ≤ 20), check no crash, plausible output

Follow-up Questions

  • For Two Sum: what if there can be multiple valid pairs? Return all? First found?
  • For Trapping Rain Water: what about 2D version (Trapping Rain Water II)? — different algorithm (heap-based BFS).
  • For Median: what if K-th smallest instead of median? — same binary-search-on-partition idea.

Product Extension

In production code review, the brute force is often the only defensible code if you can’t justify the optimal. Reviewers prefer “obviously correct slow code” over “supposedly fast code with a subtle bug” — until the optimization is properly tested.

Language/Runtime Follow-ups

  • Python: brute force should still complete for N ≤ 10^3 in <1s. Use it as oracle.
  • Java: beware of Integer boxing in HashMap<Integer, Integer> for Two Sum — measurable slowdown.
  • C++: brute force in C++ for N ≤ 5 · 10^3 finishes in well under 1s, useful for stress testing.

Common Bugs

  • Off-by-one: for j = i+1 vs for j = i (Two Sum: must j > i unless duplicates allowed)
  • Maximum Subarray: starting max_so_far = 0 instead of -infinity fails on all-negative arrays
  • Sliding Window No-Repeat: not removing characters from the set when shrinking the window
  • Trapping Rain Water: using < vs <= when comparing left and right pointers

Debugging Strategy

When the optimal disagrees with the brute on a small input: trust the brute. The brute is by construction correct. Your optimized version has the bug.

This is the stress testing pattern:

  1. Write brute (slow, correct)
  2. Write optimal (fast, suspicious)
  3. Generate random small inputs
  4. Compare outputs; on mismatch, print the input and inspect

Deliverable

In a notebook:

  1. For each of the 5 problems, the structured block (brute pseudocode, complexity, optimization sketch).
  2. For problems 1, 2, 3: real code for the brute force, with smoke + edge + random tests.
  3. A 3-sentence reflection: which problem was hardest to resist writing the optimal first?

Mastery Criteria

  • Wrote a brute force for all 5 in <2 minutes each (verbally or on paper)
  • Stated the brute force complexity correctly
  • Stated the optimization path in one sentence
  • Resisted the urge to write the optimal first
  • Used the brute force as oracle in at least one stress test