Pseudocode and Problem-Solving Protocol

Phase 0, Weeks 4–5

The gap between people who struggle with medium problems and people who solve hard ones is rarely intelligence or language knowledge. It’s process. This document gives you a repeatable, auditable process for going from problem statement to correct, optimized code — one that forces you to think before you type. Use this protocol on every non-trivial problem you solve for the rest of the 9 months.

---

1. Why Pseudocode First Is Not Slow

The counterintuitive truth: writing pseudocode before code makes you faster, not slower.

Here’s the math. If you go directly to code:

• You might implement a wrong approach, realize it at test time, and rewrite from scratch.

• You spend mental energy on syntax while also trying to reason about correctness.

• Bugs are harder to locate because you don’t have a reference “specification” for what the code should do.

If you write pseudocode first:

• Wrong approaches are caught in 2 minutes of pseudocode tracing, not 20 minutes of debugging.

• You reason about correctness at the algorithm level, then translate mechanically.

• The pseudocode is your test oracle: does the code match the pseudocode?

Experienced competitive programmers write pseudocode (or at minimum, a high-level comment sketch) on almost every non-trivial problem. It is not a beginner habit — it’s a professional one.

---

2. The 4-Step Problem-Solving Protocol

Apply this to every problem where the solution isn’t immediately obvious.

Step 1: Understand + Examples

Before writing anything, do three things:

1. Restate the problem in your own words. If you can’t, you don’t understand it.

2. Identify the input and output types precisely. “Array of integers” vs “sorted array of distinct integers” vs “array of integers possibly with duplicates” — these are different problems.

3. Run the provided examples by hand. Then create one edge case: empty input, single element, all-same elements, maximum size. What should the output be?

Time budget: 3–5 minutes. Do not skip this.

Step 2: Brute Force Out Loud

State the most naive solution that is obviously correct, even if it’s O(n³) or O(2ⁿ). Say it aloud or write it in 2–3 lines of pseudocode. Analyze its complexity.

This step does two things:

• Confirms you understand the problem (a brute force that doesn’t work means you misread the problem).

• Establishes a baseline that you will then optimize.

Time budget: 2–3 minutes.

Step 3: Optimize With Invariants

Ask: what is the brute force wasting? Common patterns:

• Recomputing the same value? → Cache it (DP, memoization, prefix sums)

• Scanning the entire array each time? → Maintain a data structure (sliding window, heap, sorted set)

• Ignoring structure in the input? → Exploit sorted order, monotonicity, or range constraints

Write the optimized algorithm as pseudocode. Trace it on your examples from Step 1. Write the loop invariant for any non-trivial loop.

Time budget: 5–10 minutes.

Step 4: Code

Translate the pseudocode to code. This should be the least intellectually demanding step — you’ve already solved the problem. Focus on:

• Correct loop bounds (check your invariant)

• Correct edge case handling

• Clean variable names that match your pseudocode

Time budget: 10–15 minutes.

---

3. Pseudocode Conventions

Pseudocode is algorithm-description language, not a specific language. Use whatever notation is clear. These conventions are widely used and unambiguous:

ALGORITHM Name(input: type) → output: type

// Single line comment
/* Multi-line comment */

// Variables
x ← 5          // assignment
arr[i]          // array indexing (0-based assumed unless stated)
arr[lo..hi]     // slice (inclusive bounds)

// Control flow
if condition then
    statements
else
    statements
end if

for i ← 0 to n-1 do      // inclusive range
    statements
end for

while condition do
    statements
end while

return value

// Functions
CALL FunctionName(args)   // or just FunctionName(args) if obvious

// Arithmetic
x ← x + 1
x ← x * 2
x ← x // 2    // integer division
x ← x mod m   // modulo

// Boolean
and, or, not   // logical operators

Key rule: Pseudocode should be readable to any programmer regardless of language background. If your pseudocode looks like Python, Java, or C++ — that’s fine, as long as it’s clear.

---

4. Loop Invariants for Three Algorithms

4.1 Linear Search

ALGORITHM LinearSearch(arr[0..n-1], target) → index or -1

invariant: target does not appear in arr[0..i-1]

for i ← 0 to n-1 do
    if arr[i] = target then
        return i
    end if
end for
return -1

Invariant: “Before iteration i, we know target is not in arr[0..i-1].”

• Initialization: Before i=0, arr[0..-1] is empty — trivially target is not in it. ✓

• Maintenance: We checked arr[i-1] and it wasn’t target, so target is not in arr[0..i]. ✓

• Termination: i = n. Invariant: target is not in arr[0..n-1] = the whole array → return -1. ✓

4.2 Insertion Sort

ALGORITHM InsertionSort(arr[0..n-1])

invariant: arr[0..i-1] is sorted

for i ← 1 to n-1 do
    key ← arr[i]
    j ← i - 1
    while j >= 0 and arr[j] > key do
        arr[j+1] ← arr[j]
        j ← j - 1
    end while
    arr[j+1] ← key
end for

Invariant: “After the i-th iteration of the outer loop, arr[0..i] is sorted.”

• Initialization: Before i=1, arr[0..0] is a single element — trivially sorted. ✓

• Maintenance: We insert arr[i] into its correct position in arr[0..i-1], producing sorted arr[0..i]. ✓

• Termination: i = n. arr[0..n-1] is sorted. ✓

The inner while loop has its own invariant: “arr[j+2..i] holds elements that were originally arr[j+1..i-1], all greater than key, shifted right by one.” Trace this on paper once.

4.3 Binary Search

ALGORITHM BinarySearch(arr[0..n-1], target) → index or -1
// Precondition: arr is sorted in non-decreasing order

invariant: if target ∈ arr, then target ∈ arr[lo..hi]

lo ← 0, hi ← n-1
while lo <= hi do
    mid ← (lo + hi) // 2
    if arr[mid] = target then
        return mid
    else if arr[mid] < target then
        lo ← mid + 1
    else
        hi ← mid - 1
    end if
end while
return -1

Invariant: “If target exists in arr, it must be in arr[lo..hi].”

Already derived in 03_mathematical_thinking.md. The key: every branch preserves the invariant because the array is sorted, so we eliminate halves that are provably wrong.

---

5. Preconditions and Postconditions

A precondition is what must be true before calling a function. A postcondition is what is guaranteed to be true after it returns.

Writing these makes your code self-documenting and makes bugs obvious.

// Precondition:  arr is non-null, n >= 0
// Postcondition: returns index i such that arr[i] = target,
//                or -1 if no such index exists
ALGORITHM BinarySearch(arr, n, target)

Why this matters: When you get a wrong answer on LeetCode, the first question is: “Did the caller satisfy the precondition?” If your binary search assumes a sorted array and the input isn’t sorted — that’s a precondition violation. The function is correct; the call site is wrong.

Get in the habit of writing these as comments when you code.

---

6. Mental Trace Tables

Before running code, trace it on a small example in a table. This catches logic errors in 3 minutes that would take 15 minutes to debug.

Example: Trace binary search on arr = [1, 3, 5, 7, 9], target = 7

Iteration	lo	hi	mid	arr[mid]	Action
1	0	4	2	5	5 < 7, so lo = 3
2	3	4	3	7	7 == 7, return 3

Correct. This trace took 30 seconds and confirms the algorithm.

How to use it: Pick a representative example (not trivial, not huge). Trace every variable that matters. If the trace diverges from expected output, you found your bug.

For recursive algorithms, draw the call tree instead of a flat table. Write the return value at each node.

---

What Most Engineers Skip

They go straight to code. Every. Single. Time.

The result: they spend 40 minutes debugging a solution that was fundamentally flawed at the algorithm level. A 5-minute pseudocode trace would have caught it at step 3.

The other failure mode: they write a brute force, it works, they submit it, it TLEs, and they don’t know why — because they never analyzed complexity before coding. Step 2 of the protocol (brute force + complexity analysis) forces you to know what you’re signing up for before you start typing.

One more: not writing loop invariants → off-by-one errors that are nearly impossible to reason about. The invariant makes the loop bounds obvious. while lo < hi vs while lo <= hi is decided by the invariant, not by guessing and checking.

---

Return to README.md · Next: 05_exit_criteria_and_projects.md