Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 225 Ā· Getting Started

How to Solve Algorithm Problems

A repeatable method for algorithm problems: understand, work examples, brute force, optimize, code, test. Includes edge cases, asserts, and reading constraints.

Most people who struggle with algorithm problems do not lack knowledge. They lack a process. They read the statement, panic, and start typing a half-formed idea. A reliable routine turns an intimidating blank page into a series of small, answerable questions, and it works the same way in an exam, an interview or a real project.

This lesson gives you that routine and applies it to a classic problem from start to finish: brute force first, then the better solution, then tests. You'll also learn two skills that make you faster: recognizing patterns, and reading the input limits to guess what complexity you need.

The six steps

  1. Understand. Restate the problem in your own words. What is the input? What is the output? What counts as valid?
  2. Work examples by hand. Make small examples, including tricky ones, and solve them on paper.
  3. Find a brute force. Describe the simplest correct approach, even if slow. Estimate its cost.
  4. Optimize. Find where the brute force wastes work, and remove the waste with a better structure or idea.
  5. Code. Write clean code for the approach you chose. Name things well.
  6. Test. Run your examples, edge cases, and a comparison against the brute force.
TEXT
 understand -> examples -> brute force -> optimize -> code -> test
      ^                                                        |
      +----------------- found a bug or a gap? ----------------+

Skipping step 1 or 2 is the most common error. If you cannot solve three small examples by hand, you can't yet write a program that does.

A worked example: two numbers that add up

Problem. Given a list of integers nums and an integer target, return the positions of two different items whose values add up to target. Assume exactly one answer exists.

Step 1: understand

  • Input: a list of integers and a target. Output: two indexes, not values.
  • "Two different items" means you can't use the same position twice. But two items with the same value at different positions are fine.
  • Questions to ask: can there be negatives? Is the list sorted? How long can it be? Is there always an answer?

Step 2: examples

TEXT
nums = [2, 7, 11, 15], target = 9   ->  [0, 1]       (2 + 7)
nums = [3, 2, 4],      target = 6   ->  [1, 2]       (2 + 4, not 3 + 3)
nums = [3, 3],         target = 6   ->  [0, 1]       (equal values, different spots)

The second example is a trap: 3 + 3 = 6, but there is only one 3. Good examples expose misunderstandings before you code.

Step 3: brute force

Try every pair. For each position i, look at every later position j and test whether the two add up.

Python Brute force: try every pair

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It is correct. Its cost is the number of pairs, n(n-1)/2, which grows with the square of n. For 1,000 items that is 499,500 checks; for a million it is about 500 billion. Too slow for large input, but a perfect reference to compare against later.

Step 4: optimize

Ask: where is the waste? For each nums[i] we scan the rest of the list looking for target - nums[i]. We are searching for one specific number. If only we could answer "have I seen the number target - x, and where?" instantly. That is exactly what a dictionary does.

The idea: walk through the list once. For each value x at index i, check whether target - x is already in a dict of values seen so far. If yes, you have the pair. If not, remember x and move on.

Python Optimized: one pass with a dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trace for [3, 2, 4] with target 6:

TEXT
i=0  x=3  need=3  seen={}          3 not seen        -> remember 3 at 0
i=1  x=2  need=4  seen={3:0}       4 not seen        -> remember 2 at 1
i=2  x=4  need=2  seen={3:0,2:1}   2 IS seen at 1    -> answer [1, 2]

Notice we check before inserting. That is what stops [3, 2, 4] from answering [0, 0] for the lone 3, and it still handles [3, 3]: the first 3 is stored, the second 3 finds it.

Complexity. One pass of n steps, each a dictionary lookup that takes about constant time: O(n) time. The dictionary may hold up to n entries: O(n) space. Compare with brute force: O(n²) time, O(1) space. We traded memory for speed, the bargain from the introduction. Both estimates are explained in Big O Notation.

Edge cases checklist

Run these through your code before you call it done:

  • Empty input and one item.
  • Duplicates and all-equal items.
  • Negative numbers and zero.
  • Already sorted, reverse sorted.
  • Smallest and largest allowed values (overflow does not exist in Python, but huge numbers get slower).
  • No answer: what should you return? State it in the problem and in your function.
  • Off-by-one at both ends of every loop and slice.

Testing with assert

An assert statement stops the program with an error if its condition is false, which makes it the simplest test tool. Collect cases in a list and check them all. A powerful extra trick is brute-force comparison: run the optimized and the brute-force solution on many random small inputs and check they agree. Seed the random generator so runs repeat.

Python Tests with assert and a brute-force check

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice what the random test checks: not that both functions return the same indexes (several pairs could be valid), but that both agree on whether an answer exists, and that the returned pair really works. Decide what "correct" means before you test.

When a test fails, the assert ..., (nums, target) message prints the exact input that broke. Shrink it to the smallest failing input by hand; small inputs are far easier to trace.

Read the constraints: guess the complexity you need

Problems state limits such as 1 <= n <= 100000. These are not decoration; they tell you which complexity will finish in time. A computer does very roughly 10⁷ to 10⁸ simple operations per second, and Python is at the slow end of that range. Use this table as a starting guess:

Input size n Complexity that usually fits
up to about 10 O(n!) or O(2ⁿ · n), try everything
up to about 20 O(2ⁿ), subsets and bitmasks
up to about 500 O(n³)
up to about 5,000 O(n²)
up to about 100,000 O(n log n)
up to about 1,000,000 O(n) or O(n log n) with a light constant
10⁹ or more O(log n) or O(1), a formula or binary search

Let the computer do this arithmetic for you:

Python Estimating work from the constraints

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

So with n = 100,000, an O(n²) brute force needs 10 billion steps, 100 times the budget. That single observation tells you to look for a sort, a hash map or a two-pointer pass instead. See the complexity cheat sheet for a reference.

Recognize the pattern

Experienced solvers don't invent everything from scratch; they recognize a shape and reach for a known tool. A starter checklist, with the chapter that teaches each:

If the problem says... Think about...
"pair / triple that sums to...", sorted array two pointers
"longest / shortest subarray or substring with a property" sliding window
"have I seen this before?", counting, grouping hash table
"range sum" queries prefix sums
"matching brackets", "next greater element" stack
"level by level", "shortest path in an unweighted graph" breadth-first search
"all combinations / arrangements" backtracking
"minimum / maximum / count the ways", overlapping choices dynamic programming
"sorted input" or "monotonic yes/no" binary search
"k largest / smallest", "always the best next" heap

If none fits, simplify: solve a smaller version, solve a special case, or draw the problem. And when stuck, return to brute force. A slow, correct solution beats an unfinished clever one, and optimizing it often reveals the trick.

Common mistakes

  • Coding too early. Ten minutes of examples save an hour of debugging.
  • Never writing the brute force. You lose both a safe answer and a test oracle.
  • Trusting one example. A solution that passes the sample may fail on duplicates or empty input.
  • Optimizing before it's correct. Get a right answer first.
  • Forgetting to say the complexity. Always finish with time and space, and why.
  • Changing a list while looping over it, and off-by-one slices.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. Which step comes immediately before writing the optimized code?

    Brute force shows what the problem needs, and spotting the repeated or wasted work points to the better structure or idea.
  2. 2. Why does two_sum_fast check the dictionary before inserting the current value?

    Checking first means the current item is not yet in seen, so it can only pair with an earlier item at a different index. Equal values at different positions still work.
  3. 3. What is the time complexity of the one-pass dictionary solution for two sum?

    It makes a single pass over n items, and each dictionary lookup and insert takes about constant time.
  4. 4. A problem has n up to 100,000. Which approach is most likely to be fast enough?

    n squared would need about 10 billion steps. O(n log n) needs under two million for n = 100,000.
  5. 5. Why compare a fast solution to a brute force on random small inputs?

    A slow but obviously correct solution is a trustworthy oracle. Disagreements point to bugs in the optimized code.

Summary

  • Follow the routine: understand, examples, brute force, optimize, code, test.
  • Work small examples by hand first, including tricky ones that expose misunderstandings.
  • The brute force gives a safe answer and a baseline; ask where it wastes work to find the improvement.
  • Two sum goes from O(n²) time and O(1) space to O(n) time and O(n) space with a dictionary.
  • Check edge cases: empty, single, duplicates, negatives, no answer, off-by-one.
  • Test with assert, hand-written cases and seeded random comparison against the brute force.
  • Read the constraints: n up to 10⁵ means aim for O(n log n) or better. Recognize patterns, then pick the matching tool.

Next: Big O Notation, the language for describing how an algorithm's work grows with its input.