How to start solving a problem?

In this article

• Example 1: assembling furniture
• Example 2: a hard jigsaw puzzle
• Fewer cues, more trial and error
• Example 3: Two Sum, in Lua
• Scan again as you go
• How the cue scan feeds the other moves
• You will miss cues, and that is how you learn them
• When the wording changes, the code changes
• Do it before your next problem

Before you write any code, read the problem and list what the finished answer must do. That list is a cue scan. Each item is a cue: a detail in the problem, such as a word, a phrase or an example, that tells you something about the answer. You do not need to know any algorithms to do this. You need to read slowly and ask, for each detail, “what does this change about what I hand back?”

A cue scan is not a one-time step. You do it before you start, and again each time you finish a piece of work. The second time, you check what you built against the list, and you look for cues you could not see at the start.

The three examples below use the same move. The first two have no code. They are things you have probably done many times without a name for them. Giving the move a name does two things. It shows that you already have the habit, before any algorithm is involved. And it lets you notice when you miss a cue, so you can learn to spot it next time.

Example 1: assembling furniture

You buy a bookshelf. The box holds a pile of boards, a bag of screws, and a manual made of drawings.

Before you pick up a screwdriver, you match the real parts to the drawings. You probably do this without thinking about it, and without a name for it. It is a cue scan. Its cues come from three places: what the manual says, what it shows, and what you already know.

The text in the manual states some of them:

• The parts list says “4x” next to the shelf board. All four must end up in the shelf.
• Screw A and screw B have different letters, so they are not the same screw.

The drawings show others, without words:

• One board in the drawing is twice as long as the rest. That is the side panel, so you find the longest boards in the box.
• One panel has a row of small holes and a notch cut out of one corner. Its outline looks nothing like the plain shelves, so you can pick it out of the pile at a glance.
• The screws are drawn at their real size. You hold each screw against the drawing to tell A from B.
• The door in the final drawing has its hinges on the left.

Experience gives you the rest. If you have built furniture before, you know that the finished, smooth edge of a board faces out, and that the side with the pre-drilled holes usually faces in. The manual does not say this. You learned it from building the last shelf wrong. (That is, assuming you have ever assembled furniture. If not, we guess this was a bad example.)

Without the scan. You skip the matching and start screwing parts together. The frame goes up fast. Screws A and B look alike, so you grab whichever is closest. An hour later you have a solid shelf, two problems and no way to fix either without starting over:

• The doors open from the right, because you hung them by feel. The hinge holes are already drilled, so moving them means new holes.
• The last two brackets need the long screws, and only short ones are left. The long ones are holding up the shelves, where the short ones would have done.

Each mistake came from a cue that was in the box the whole time: a letter in the parts list, a hinge in a drawing, a screw drawn at its real size.

Example 2: a hard jigsaw puzzle

You open a 1000-piece puzzle. The box shows a harbor at sunset.

Read the box the same way. Its cues come from two places.

The text on the box states them:

• “1000 pieces.” Done means all 1000 are used and none is left over.

The picture shows them, without saying them in words:

• The finished puzzle must look like this picture.
• Most of the top half is sky, all one color.

Nobody wrote “the sky is in the top half.” You read it off the finished image. Anyone can find these cues, even on their first puzzle, by looking carefully at the text and the picture.

Someone who has done puzzles before sees one more cue when they tip the pieces out: some pieces have a flat side. Those are the edges, and the edges are the easiest place to start, because a flat side tells you where a piece goes. Neither the text nor the picture says this. You learn it by doing puzzles. On your first puzzle, the flat sides are in front of you the whole time, and you still might not notice them, or know what they are good for.

Code problems have the same three sources. Some cues are stated in the problem text, like “return the indices.” Some are shown in the examples: an example answer of {1, 2} shows the order and the counting without a word of explanation. Careful reading finds both. The third kind only stands out once you have seen the technique it points to. Missing those early on is normal.

Even the flat sides only help with part of the job. They make the edges easy, but they do not finish the sky.

Without the scan. You skip the box and invent your own rule: “blue pieces are sky.” You put every blue piece in the top half. The sky fills quickly and feels like progress. Then the bottom half stalls. The harbor water is blue too, and its pieces are scattered through your sky. Now you have to take apart work that looked finished to find the pieces that belong lower down.

The box never said “blue means sky.” You assumed it, because it was true for most of the pieces. A cue scan writes down what is stated, so a guess like this shows up as a guess before you build on it.

Fewer cues, more trial and error

The more structured information a problem gives you, the less you have to guess.

Take away the picture on the puzzle box. You would still start with the flat edges, because experience tells you to. But you would lose the cue that the blue pieces go near the top. You would have to try pieces against each other far more often.

Take away the furniture manual. Now nothing tells you which board goes where. At almost every step you would have to hold each part against each other part and see whether they fit.

Trying every possibility like this is called brute force. It works, but it is slow, and it gets slower as the problem grows. Every cue you find cuts down the number of things you have to try.

This site gives you a safety net here. We do not ask you to invent new algorithms. Every problem on the site has a known solution: the algorithms are well-established ways of solving problems that come up across computer science, and in concurrent system design in particular. So when you are stuck, you know the problem can be solved, and that the cues to solve it are there to find.

Real-world problems come with no such promise. Professional problem solvers, such as mathematicians and engineers, often work on problems nobody knows how to solve, and most attempts end in a dead end. In 1904 Henri Poincaré posed a question about the shape of three-dimensional spaces, after finding a flaw in his own earlier claim from 1900.poincare He never solved it. Over the next century, Max Dehn,dehn J. H. C. Whitehead,whitehead R. H. Bing,bing Christos Papakyriakopoulospapakyriakopoulos and Wolfgang Hakenhaken each tried a route that did not work. Grigori Perelman finally solved it in preprints posted in 2002 and 2003,perelman about a hundred years after the question was asked.clay

The conjecture is itself a hard real-world problem, and asking it was part of the work. Before Poincaré could state it, he had to invent the tools to do so: the fundamental group, a way to describe the loops in a space, appeared in his papers of 1894 and 1895.analysis-situs Then he got the question wrong once before he got it right.

Failing to solve a problem is not the same as failing. Poincaré never solved his own question, but it was solved, and the work it set off moved mathematics forward along the way. Whitehead’s failed proof left behind a new object, now called the Whitehead manifold, that taught topologists something they had not known.whitehead-gain And Poincaré solved plenty of other problems: he won a prize for the 60th birthday of King Oscar II of Sweden, awarded in 1889, for work on how three bodies move under gravity, and he is counted among the discoverers of special relativity.poincare-work The struggle with a hard problem pays off for the person who struggles, and for everyone who builds on the attempt.

On this site, the dead ends have already been found for you. Your job is to read the cues well enough to take the route that works.

Example 3: Two Sum, in Lua

Here is the Two Sum problem as the site states it:

Given a table of integers nums and an integer target, return the indices of the two numbers that add up to target. You may assume that each input has exactly one solution, and you may not use the same element twice. Lua tables are 1-based: the expected answer is {1, 2}, not {0, 1}. Return the earlier position first.

Read each phrase and write down what it changes:

Cue in the problem	What it changes in your answer
“return the indices”	Hand back positions, not the numbers. Keep track of where each number is.
“two numbers”	Look at pairs of positions.
“exactly one solution”	As soon as you find a pair that works, you are done.
“may not use the same element twice”	The two positions must be different.
“1-based”	The first position is 1.
“earlier position first”	Put the smaller position first.

Now each line of a plain, imperative solution comes from one of those cues:

function two_sum(nums, target)
  for i = 1, #nums do                -- 1-based: start at position 1
    for j = i + 1, #nums do          -- different elements: j starts after i
      if nums[i] + nums[j] == target then
        return {i, j}                -- indices, earlier first; one solution, so stop here
      end
    end
  end
  return {}                          -- not reached when a solution is guaranteed
end

return {i, j} sits inside both loops. That is only correct because the problem says there is exactly one solution, so the first pair you find is the answer. The cue decides where the function ends.

j = i + 1 keeps the two positions different. It does not stop two equal numbers from being used. With {3, 3} and target 6, the answer is {1, 2}: the same value, but two different elements. “Do not use the same element twice” is about positions, not values.

Without the scan

Here are two first attempts that skip the scan. Both run and both fail a test, and each failure points you at the wrong part of the code.

Returning the numbers. You remember “find two numbers that add up to the target” and write:

return {nums[i], nums[j]}

For {2, 7, 11, 15} and target 9, this returns {2, 7}. The test expects {1, 2}. The numbers are right, so the loops look right, and it is easy to spend a while checking the addition. The bug is one phrase you did not read: “return the indices.”

Using the same element twice. You write both loops the same way:

for i = 1, #nums do
  for j = 1, #nums do

For {3, 2, 4} and target 6, the first pair checked is i = 1, j = 1: 3 + 3 = 6. The function returns {1, 1}. The test expects {2, 3}. The sum really is 6, so the code looks correct when you trace it. The bug is “you may not use the same element twice.”

Neither fix needed a better algorithm. Each needed only a phrase that was already in the problem.

Scan again as you go

A cue scan is not only for the start. Each time you finish a piece of work, step back and read it the way you read the problem.

On the puzzle, that means stepping back from the table. From a distance you notice that the harbor water is a darker, greener blue than the sky. Nothing in the box told you that. Your own half-built puzzle did. It is a new cue, and it fixes the “blue means sky” mistake before it costs you an hour.

Code works the same way. Say you write the faster version of Two Sum. It keeps a notebook, a table called seen, of every number it has passed and where it was. A natural first attempt writes each number into the notebook, then checks the notebook for its partner:

local seen = {}
for i, value in ipairs(nums) do
  seen[value] = i                      -- write it down
  local complement = target - value
  if seen[complement] ~= nil then      -- then look for its partner
    return {seen[complement], i}
  end
end

Run it on {3, 2, 4} with target 6. At position 1 the code writes down 3, then looks for 6 - 3 = 3, and finds it: the 3 it just wrote. It returns {1, 1}. The test expects {2, 3}.

This is a false positive: the code reports a match that is not there. It is confusing because nothing looks broken. The notebook works, and the arithmetic is right.

You read the cue at the start, and you understood it. It did not save you, because the bug did not exist yet. It appeared when you chose an order for two lines. So step back and read the new code against the list you already have: “the two positions must be different.” Ask: can the lookup ever find the number I am standing on? With the save first, it can. Swap the two steps, so the code looks for a partner among the numbers before this one, and only then writes the current one down:

local seen = {}
for i, value in ipairs(nums) do
  local complement = target - value
  if seen[complement] ~= nil then      -- look among earlier numbers only
    return {seen[complement], i}
  end
  seen[value] = i                      -- then write this one down
end

To watch this order step by step, trace the Two Sum hash scan flowchart. It asks whether the partner is already in the notebook before it writes the current number down. The chart counts positions from 0, not from 1 as Lua does.

The scan did not give you the notebook. That idea comes from knowing the technique. But the order of those two lines comes straight from a cue you wrote down before you wrote any code.

Each time you build something, read it against your list again, and look for new cues the problem did not give you.

How the cue scan feeds the other moves

The cue scan is the first of several moves this site uses to describe solving a problem. Your list of cues is what each later move works from.

To see the moves in order on this same problem, follow How a strong solver approaches Two Sum. It opens with a cue scan of the Two Sum statement, then asks you to predict what the solver does next, one move at a time. That replay uses Elixir, so its positions count from 0.

Hypothesis. A hypothesis is your first guess at an approach, said plainly enough to test. For example: “check every pair with two loops, and stop at the first pair that adds up.” The cue list is what the guess has to satisfy. “Exactly one solution” is why stopping at the first pair is allowed. A guess that breaks a cue is wrong before you write any code.

Counterexample hunt. Next you try to break the guess on purpose, with the input most likely to defeat it. The cue list tells you where to aim. Each cue suggests an input:

• “May not use the same element twice”: try {3, 2, 4} with target 6, where one number plus itself hits the target.
• Equal values at different positions are allowed: try {3, 3} with target 6.

Conjecture, kill it, pivot covers this move and what to do when the guess breaks.

Implement. Implementing is where each cue becomes a line of code: j = i + 1, return {i, j}, and in the notebook version the order of the check and the save. Implement makes the same point about that order: “Lookup happens before insertion, so a match comes from an earlier position.”

Debug. When a test fails, the first question to ask is: which cue does this output break? {2, 7} instead of {1, 2} breaks “return the indices.” {1, 1} breaks “the two positions must be different.” That points you at the line to fix, instead of at the arithmetic, which was right all along. A failing test is a cue too: it is information about your code, the way the two blues were information about the puzzle. Trace test shows how to watch what the code actually does once you know where to look.

You will miss cues, and that is how you learn them

A cue scan does not need to catch everything on the first read. Its job is to give you a list to check your work against later.

You will miss cues, especially early on. Some are on the page and easy to skim past, like “indices,” until one costs you 20 minutes. Others you cannot see yet, because you have not met the technique they point to. Experienced solvers seem to spot cues by instinct. They have missed more of them before, and remembered.

So when a bug turns out to come from a missed cue, take one more step after the fix. Ask: which phrase in the problem would have told me this? Write it down. The site calls this move Retrospect: looking back after solving to see which cue should have pointed you there sooner. The Two Sum notebook bug is a good example. Once it has cost you a false positive, “check before you save” is a cue you will notice in every problem that keeps a notebook.

When the wording changes, the code changes

Here is the same problem, reworded:

Return how many pairs of positions add up to target.

“How many” means you can no longer stop at the first pair, because you must count all of them. Three lines change:

function count_pairs(nums, target)
  local count = 0                    -- "how many": keep a running total
  for i = 1, #nums do
    for j = i + 1, #nums do
      if nums[i] + nums[j] == target then
        count = count + 1            -- note it, and keep looking
      end
    end
  end
  return count                       -- answer only after every pair is checked
end

For {3, 3, 3} and target 6, the answer is 3: positions (1, 2), (1, 3) and (2, 3).

The words “how many” moved the return out of the loop. A cue scan catches that kind of change before you write the code, not after the tests fail.

Some wording changes do more than move a line. They change the whole approach. Two more versions of the same problem, without the solutions:

The numbers are sorted from smallest to largest. Return the positions of two numbers that add up to target.

“Sorted” is a cue the original problem never gave you. Your two loops still work, but sorting opens a much faster route: start one finger at each end of the list and move them toward each other. Two pointers explains how.

Return whether any group of the numbers, of any size, adds up to target.

This looks like a small change: “any group” instead of “two numbers.” It is not. With two numbers you check pairs. With any group you have to consider every possible combination, and their number doubles with each number you add to the list. No one knows a method that stays fast for every list. When the numbers are small, dynamic programming makes it manageable, and P vs NP explains why no general fast method is known.

A few words changed, and the problem went from a quick check of pairs to one of the hardest-known kinds of problem.

If you are new to algorithms, you are not expected to see that coming. “Any group” looks like a small change, and a careful reading will not tell you how much it costs. Someone who has already tried to solve a problem like this, and watched their program slow to a crawl as the list grew, sees it at once. It is the flat edge of the puzzle again: a cue that comes from experience, not from the page. What a beginner can do is notice that the wording changed, and ask what that change means before writing code.

Do it before your next problem

Before you write code, write two lines:

• “The answer must…” What do you hand back, in what order, and what if there is no answer?
• “I must not assume…” What sounds true but is not stated? For example, that the numbers are sorted, or that all values are different.

There is an old joke about a dairy farmer who asks a physicist why his cows give so little milk. The physicist works on it for weeks, then comes back: “I have a solution. But it only works for a spherical cow, in a vacuum.” The second line is where you catch yourself assuming a spherical cow: the numbers are sorted, the values are all different, the input is never empty. Unless the problem says so, the cow is not spherical.

If you cannot finish those lines, read the problem again. If you can, start coding, and check each line of your code against them.