How to Approach a Problem

You open a new problem, read it once, and your mind goes blank. Or you start typing straight away, get halfway, and realise you are solving the wrong thing. Both happen to everyone.

Experienced people do not have a better memory for tricks. They have a routine that gets them from "no idea" to working code without a flash of insight. Here it is in seven steps, then one problem solved from start to finish.

#The seven steps

1. Restate the problem in your own words. Name the input, the output, and the size limits. Ask what happens in the odd cases: empty input, no answer, ties.
2. Solve a small example by hand. Use 5 to 8 items. Watch what you do; that is a first algorithm.
3. Write the brute force. The most obvious correct method, even if it is slow. Work out its cost.
4. Find the waste. What does the brute force compute again and again, or check when it could not possibly matter?
5. Pick a pattern that removes that waste. The cheat table below helps.
6. Write the code for the better method.
7. Test edge cases by hand or by running them: empty, one item, all the same, the answer at each end.

Steps 1 and 2 feel slow. Skip them and you pay later, debugging an answer to a question nobody asked.

#A worked problem

Your phone counts your steps each day. Your goal is 8,000 a day. Given the daily counts, find your longest streak: the most days in a row on which you hit the goal.

#1. Restate it

Input: a list of whole numbers steps, one per day in order, and a number goal. Output: one number, the length of the longest run of neighbouring days where every day has steps[i] >= goal.

The odd cases need decisions before any code exists. Exactly 8,000 counts as hitting the goal ("at least"). If no day hits the goal, the answer is 0. An empty list also gives 0. Suppose the app keeps up to 100,000 days of history: that is the size to plan for.

#2. Solve a small example by hand

Take a week: 8,200, 9,100, 4,000, 8,500, 10,200, 9,000, 2,500. Mark each day: ✓ ✓ ✗ ✓ ✓ ✓ ✗. The runs of ticks have lengths 2 and 3, so the answer is 3.

Notice what your eyes did: you scanned once and counted ticks, starting over at each cross. Keep that in mind.

#3. Write the brute force

The most literal method: try every day as the start of a streak, walk forward while the goal is met, and keep the longest walk.

function longestStreakSlow(steps, goal) {
  let best = 0;
  for (let start = 0; start < steps.length; start++) {
    let length = 0;
    while (start + length < steps.length && steps[start + length] >= goal) {
      length++;
    }
    best = Math.max(best, length);
  }
  return best;
}

def longest_streak_slow(steps, goal):
    best = 0
    for start in range(len(steps)):
        length = 0
        while start + length < len(steps) and steps[start + length] >= goal:
            length += 1
        best = max(best, length)
    return best

It is correct, which gives you something to test against. Its cost: if every day hits the goal, the walks have lengths n, n − 1, ..., 1. That sum is about n²/2 (see Math for Algorithms). With 100,000 days that is 5 billion steps. Too slow.

#4. Find the waste

Look at the walks that start inside the long streak.

Two kinds of waste show up. A walk that starts in the middle of a streak can never beat the walk that started at the beginning of it. And when one walk stops at day 6, the next walk re-checks the same days only to stop at day 6 again.

A good question to ask: "What do I know about today, given what I knew yesterday?" If today hits the goal, the streak ending today is the streak ending yesterday plus 1. If it does not, the streak ending today is 0. One number carried from day to day replaces all the walks.

#5. Pick a pattern

This is the simplest pattern there is: one pass, carrying a running value. You saw it already as "best so far" in What Is an Algorithm. Here you carry two values: the current streak and the best streak. It is also the simplest case of a sliding window.

#6. Write the code

best = 0, current = 0for each day d:  if d >= goal: current = current + 1  else: current = 0  best = max(best, current)return best

function longestStreak(steps, goal) {
  let best = 0;
  let current = 0; // length of the streak that ends today
  for (const day of steps) {
    current = day >= goal ? current + 1 : 0;
    best = Math.max(best, current); // update every day
  }
  return best;
}
 
longestStreak([8200, 9100, 4000, 8500, 10200, 9000, 2500], 8000); // 3

def longest_streak(steps, goal):
    best = 0
    current = 0  # length of the streak that ends today
    for day in steps:
        current = current + 1 if day >= goal else 0
        best = max(best, current)  # update every day
    return best
 
longest_streak([8200, 9100, 4000, 8500, 10200, 9000, 2500], 8000)  # 3

#7. Test the edge cases

Run each by hand through the one-pass code:

• []: the loop never runs, returns 0. Correct.
• [3000, 5000]: no day hits, current stays 0, returns 0. Correct.
• [8000]: exactly the goal counts, returns 1. Correct.
• [9000, 9000, 9000]: every day hits, returns 3. Correct.
• [2000, 9000, 9000]: the best streak is at the very end, returns 2. Correct. This case catches the most bugs (see below).

Also run both versions on many random small lists and check they agree. That finds bugs that staring never will.

#Which pattern fits

Problems give off signals. Treat this table as a starting point, not a rule.

The size limits are a signal too. At a few hundred million simple steps per second, they tell you roughly what cost you can afford:

#Common mistakes

#Check yourself

#What to practise next

This finishes the foundations. Next, Arrays starts the everyday tools, and the patterns in the table above come one lesson at a time. Use the seven steps on every problem you practise, even the easy ones, until they are a habit.