Data Structures & Algorithms (DSA) Module 1 – Foundations: problems, correctness and complexity
From brute force to optimal: a working method
Restate a problem, write the brute force, name its bottleneck and improve it one justified step at a time, keeping the slow version as a check.
What you will learn
- Describe a problem by its inputs, outputs and constraints before writing code
- Derive a brute-force solution and name its bottleneck operation
- Improve a solution step by step and justify each step
- Check a faster solution against the brute force on many inputs
Before you start
On this page
Most problems in this track are solved the same way: first an answer that is slow but obviously right, then a faster one with a reason why it is still right. This lesson walks through that method on one problem, step by step, and then shows why the slow answer is worth keeping after the fast one exists.
The problem: references that appear twice
A payment system gives every payment a reference such as PAY000417203. After a bug in its retry logic, some
payments were written to the day’s log twice. The job: list every reference that appears more than once.
Step 1: restate it before writing code
Write down what goes in, what must come out and how big the input can get. The size matters most, because it tells you how much work you can afford.
- Input: a list of n references, each a short string.
- Output: every reference that appears more than once, listed once each, in sorted order.
- Size: up to about 100,000 references a day.
Then work small cases by hand, choosing the awkward ones on purpose: nothing at all, a single item, everything equal,
and items that repeat more than twice. Short names such as "A" stand for whole references here:
| Input | Output | Why it is worth trying |
|---|---|---|
[] |
[] |
An empty day must not crash anything |
["A"] |
[] |
One payment cannot be a duplicate |
["A", "A", "A"] |
["A"] |
Three copies are still one duplicated reference |
["B", "A", "B", "A"] |
["A", "B"] |
Several duplicates, reported in sorted order |
Writing these down settles questions the first description left open, such as whether a reference seen three times is reported once or twice.
Step 2: write the brute force
A brute force solves the problem in the most direct way, usually by trying every possibility, without worrying
about speed. Here that means comparing every pair of positions. duplicates_pairwise below does exactly that; it is
easy to believe because it checks everything.
duplicates/duplicates.py
"""Three ways to find the payment references that appear more than once in a day's log."""
def duplicates_pairwise(refs):
"""Brute force: compare every pair of positions."""
found = set()
for i in range(len(refs)):
for j in range(i + 1, len(refs)):
if refs[i] == refs[j]:
found.add(refs[i])
return sorted(found)
def duplicates_sorted(refs):
"""Sort a copy first: equal references then sit next to each other."""
ordered = sorted(refs)
found = []
for i in range(1, len(ordered)):
if ordered[i] == ordered[i - 1] and (not found or found[-1] != ordered[i]):
found.append(ordered[i])
return found
def duplicates_hashed(refs):
"""Remember every reference seen so far in a set: one pass, one lookup per reference."""
seen = set()
found = set()
for ref in refs:
if ref in seen:
found.add(ref)
else:
seen.add(ref)
return sorted(found)duplicates/compare_duplicates.py
import random
from duplicates import duplicates_hashed, duplicates_pairwise, duplicates_sorted
def make_log(n, repeats, seed):
"""A made-up day's log: n references, of which `repeats` copy an earlier one."""
rng = random.Random(seed)
refs = [f"PAY{rng.randrange(10**9):09d}" for _ in range(n - repeats)]
refs += rng.sample(refs, repeats)
rng.shuffle(refs)
return refs
class Counted(str):
"""A reference that counts how often sorted() compares it (sorted() compares with <)."""
comparisons = 0
def __lt__(self, other):
Counted.comparisons += 1
return str.__lt__(self, other)
# 1. The three answers agree, on small cases and on a generated log.
for refs in ([], ["A"], ["A", "A", "A"], ["B", "A", "B", "A"]):
assert duplicates_pairwise(refs) == duplicates_sorted(refs) == duplicates_hashed(refs)
log = make_log(2_000, repeats=3, seed=1)
answer = duplicates_pairwise(log)
assert answer == duplicates_sorted(log) == duplicates_hashed(log)
print(f"All three agree: {len(answer)} references appear twice in a log of {len(log):,}")
# 2. How many basic steps each one takes.
print(f"{'n':>9} {'pairs compared':>16} {'sorting + scan':>16} {'set lookups':>12}")
for n in (1_000, 10_000, 100_000):
refs = [Counted(r) for r in make_log(n, repeats=3, seed=n)]
Counted.comparisons = 0
duplicates_sorted(refs)
sort_steps = Counted.comparisons + (n - 1) # sorted()'s comparisons, then one check per neighbour
print(f"{n:>9,} {n * (n - 1) // 2:>16,} {sort_steps:>16,} {n:>12,}")Output
All three agree: 3 references appear twice in a log of 2,000
n pairs compared sorting + scan set lookups
1,000 499,500 9,687 1,000
10,000 49,995,000 130,163 10,000
100,000 4,999,950,000 1,632,014 100,000
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 compare_duplicates.py
The program first checks that all three functions give the same answers on the hand-worked cases and on a made-up log of 2,000 references, then gives the basic steps each one takes on logs of 1,000, 10,000 and 100,000 references. Only the sort’s comparisons have to be counted while it runs. The other two columns follow from the code, for every input of that size: the two loops of the pairwise version always compare all n(n − 1)/2 pairs, and the set version makes one lookup per reference. At 100,000 references the pairwise version makes about five billion comparisons, far too many for a report someone is waiting for.
Step 3: name the bottleneck
Ask which step repeats more often than it needs to. In the pairwise version, every reference is searched for again in the whole rest of the list: the bottleneck is repeated searching. Most bottlenecks you will meet have a usual remedy, and the modules of this track teach each one:
| If the slow part is … | try … |
|---|---|
| searching the same data again and again | sorting it once, or a hash set or map |
| recomputing sums over ranges | prefix sums |
| checking pairs in a sorted list | two indices that move towards each other |
| finding the smallest or largest item many times | a heap |
| solving the same smaller problem many times | dynamic programming |
Step 4: improve, and say why it is still right
Each improvement comes with one sentence that explains why it gives the same answer. “It passed the samples” is not such a sentence: samples show that a solution works on a few inputs, not on all of them.
Sort first. duplicates_sorted sorts a copy of the log, then compares each reference with the one before it.
Why that is right: in sorted order, all copies of a reference sit next to each other, so every duplicated reference
has an equal neighbour, and comparing neighbours finds them all. The cost is the sort, which Python’s documentation
gives as O(n log n), plus one pass. To count the sort’s comparisons, the program wraps each reference in a class that
counts calls to <, the only comparison Python’s sorting uses. On random logs it came to a little under n log₂ n
comparisons: about 1.5 million for 100,000 references, before the 99,999 neighbour checks of the scan.
Remember what you have seen. duplicates_hashed keeps a set of the references met so far. Why that is right:
when the loop reaches a reference, seen holds exactly the references before it, so the reference is a duplicate
exactly when it is already in seen. Checking x in seen takes the same short time on average however big the set
is (O(1), as the documentation’s table puts it), so the whole pass costs n lookups.
Both faster versions spend memory to save time: a sorted copy of the log, or a set of up to n references. That is the time and space trade-off you will meet throughout this track. Sorting first is also a named strategy: the CS2023 curriculum gives finding duplicates via a sorted copy as its example of “instance simplification”, turning the input into an easier form before solving the problem.
Step 5: keep the brute force as a check
A fast solution is easier to get wrong than a slow one, and the brute force is the perfect thing to test it against. This example solves a second problem three ways: count the pairs of positions whose values differ by exactly d. One check runs all three on worked examples, then compares the two faster ones with the brute force on 300 random lists, with three values of d each. The lists come from a fixed seed, so every run tests the same lists.
Python · pairs_difference.py
import random
from bisect import bisect_left, bisect_right
from collections import Counter
def pairs_brute(nums, d):
"""How many pairs of positions i < j have values that differ by exactly d (d >= 0)."""
total = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if abs(nums[i] - nums[j]) == d:
total += 1
return total
def pairs_sorted(nums, d):
"""Sort, then binary-search for each value's partners, x + d, to its right."""
ordered = sorted(nums)
total = 0
for i, x in enumerate(ordered):
total += bisect_right(ordered, x + d, i + 1) - bisect_left(ordered, x + d, i + 1)
return total
def pairs_counted(nums, d):
"""Count each value once, then multiply the counts of v and v + d."""
count = Counter(nums)
if d == 0:
return sum(c * (c - 1) // 2 for c in count.values()) # a value pairs with its own copies
return sum(c * count[v + d] for v, c in count.items())
CASES = [([], 2, 0), ([5], 0, 0), ([1, 3, 5], 2, 2), ([3, 1], 2, 1), ([4, 4, 4], 0, 3), ([1, 1, 2, 2], 1, 4), ([-2, 0, 2], 2, 2)]
rng = random.Random(42)
randoms = [[rng.randint(-5, 5) for _ in range(rng.randint(0, 12))] for _ in range(300)]
for nums, d, expected in CASES:
assert pairs_brute(nums, d) == expected, (nums, d)
print(f"pairs_brute: right on {len(CASES)} worked examples")
for solve in (pairs_sorted, pairs_counted):
for nums, d, expected in CASES:
assert solve(nums, d) == expected, (solve.__name__, nums, d)
for nums in randoms:
for d in (0, 1, 3):
assert solve(nums, d) == pairs_brute(nums, d), (solve.__name__, nums, d)
print(f"{solve.__name__}: right on {len(CASES)} worked examples, agrees with pairs_brute on {len(randoms) * 3} random cases")Output
pairs_brute: right on 7 worked examples pairs_sorted: right on 7 worked examples, agrees with pairs_brute on 900 random cases pairs_counted: right on 7 worked examples, agrees with pairs_brute on 900 random cases
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 pairs_difference.py
JavaScript · pairs_difference.mjs
/** How many pairs of positions i < j have values that differ by exactly d (d >= 0). */
function pairsBrute(nums, d) {
let total = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (Math.abs(nums[i] - nums[j]) === d) total++;
}
}
return total;
}
/** First position from `lo` whose value is not less than x (or, with `after`, not at most x). */
function bound(sorted, x, lo, after) {
let hi = sorted.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (sorted[mid] < x || (after && sorted[mid] === x)) lo = mid + 1;
else hi = mid;
}
return lo;
}
/** Sort, then binary-search for each value's partners, x + d, to its right. */
function pairsSorted(nums, d) {
const sorted = [...nums].sort((a, b) => a - b);
let total = 0;
sorted.forEach((x, i) => {
total += bound(sorted, x + d, i + 1, true) - bound(sorted, x + d, i + 1, false);
});
return total;
}
/** Count each value once, then multiply the counts of v and v + d. */
function pairsCounted(nums, d) {
const count = new Map();
for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
let total = 0;
for (const [v, c] of count) total += d === 0 ? (c * (c - 1)) / 2 : c * (count.get(v + d) ?? 0);
return total;
}
const CASES = [[[], 2, 0], [[5], 0, 0], [[1, 3, 5], 2, 2], [[3, 1], 2, 1], [[4, 4, 4], 0, 3], [[1, 1, 2, 2], 1, 4], [[-2, 0, 2], 2, 2]];
let seed = 42;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647; // a small seeded generator (Park and Miller)
const randint = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));
const randoms = Array.from({ length: 300 }, () => Array.from({ length: randint(0, 12) }, () => randint(-5, 5)));
for (const [nums, d, expected] of CASES) {
if (pairsBrute(nums, d) !== expected) throw new Error(`pairsBrute(${JSON.stringify(nums)}, ${d})`);
}
console.log(`pairsBrute: right on ${CASES.length} worked examples`);
for (const solve of [pairsSorted, pairsCounted]) {
for (const [nums, d, expected] of CASES) {
if (solve(nums, d) !== expected) throw new Error(`${solve.name}(${JSON.stringify(nums)}, ${d})`);
}
for (const nums of randoms) {
for (const d of [0, 1, 3]) {
if (solve(nums, d) !== pairsBrute(nums, d)) throw new Error(`${solve.name}(${JSON.stringify(nums)}, ${d})`);
}
}
console.log(`${solve.name}: right on ${CASES.length} worked examples, agrees with pairsBrute on ${randoms.length * 3} random cases`);
}Output
pairsBrute: right on 7 worked examples pairsSorted: right on 7 worked examples, agrees with pairsBrute on 900 random cases pairsCounted: right on 7 worked examples, agrees with pairsBrute on 900 random cases
Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node pairs_difference.mjs
Runs on this device, in your browser. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs.
Your run, in this browser
pairs_sorted uses the bisect module to binary-search for the partners of each value, and pairs_counted uses a
Counter, a dictionary that counts how often each value occurs. The JavaScript version does the same with its own
binary search and a Map, and makes its random lists with a small seeded generator of its own, because JavaScript’s
Math.random() cannot be seeded.
Look at the special case for d equal to 0 in pairs_counted. It is there because of a worked example. Without it, the
counting formula pairs every value with itself:
from collections import Counter
def pairs_counted_naive(nums, d):
"""Multiply the counts of v and v + d, with no special case for d == 0."""
count = Counter(nums)
return sum(c * count[v + d] for v, c in count.items())
print(pairs_counted_naive([1, 3, 5], 2)) # the pairs (1, 3) and (3, 5): right
print(pairs_counted_naive([4, 4, 4], 0)) # three 4s make 3 pairs, but this counts 3 * 3Output
2 9
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 naive_counted.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
For d = 2 the formula is right. For d = 0 it multiplies the three 4s by themselves and gets 9, but three equal values
make only 3 pairs of positions. The worked example [4, 4, 4] with d = 0 catches this, and so do the random
comparisons with the brute force, whose two loops never pair a position with itself.
The method in one list
- Restate the problem: input, output, size, and the awkward cases worked by hand.
- Write the brute force, and make sure it is right.
- Name the step that repeats more than it needs to.
- Replace it with a better structure or algorithm, and write the sentence that says why the answer is the same.
- Test the new version against the brute force on many inputs, with a fixed seed so that a failure can be repeated.
Key takeaways
- Read the size of the input before choosing an approach: it tells you how many steps you can afford.
- Hand-worked edge cases (empty, one item, all equal, many repeats) settle what the output should be before any code exists.
- The brute force is the reference answer. Its bottleneck tells you what to improve: here, repeated searching, cured by sorting or by a set.
- Every faster version needs a reason it is still correct, and a test against the brute force on many seeded random inputs.
- Faster solutions often spend memory: a sorted copy, a set, a table of counts.
Exercise
Exercise · Easy · Python, JavaScript
Find the longest streak of rising step counts
A fitness app stores one step count per day. A rising streak is a run of consecutive days in which every day has more steps than the day before it; a single day on its own is a streak of length 1. Write two functions that return the length of the longest rising streak in a list of daily counts (0 for an empty list):
longest_rise_brute(steps)(JavaScript:longestRiseBrute(steps)): the brute force. For every start day, walk forward while each day beats the one before, and keep the longest walk.longest_rise(steps)(JavaScript:longestRise(steps)): one pass over the list. Keep the length of the streak that ends at the current day.
For [5000, 6200, 6200, 7100, 8000, 4000] both return 3: the days with 6200, 7100 and 8000 steps. Equal counts on two days in a row end a streak, because the second day is not higher.
The sample tests check both functions on the same small cases, then check that the fast version agrees with the brute force on 200 random lists, and finally give the fast version 200,000 rising days. The brute force would need about twenty billion steps for that input, so only a one-pass solution finishes in time.
Python · Starter code · streak.py
def longest_rise_brute(steps):
"""Length of the longest run of days, each with more steps than the day before (try every start day)."""
# Replace this line with your code.
return 0
def longest_rise(steps):
"""The same answer in one pass over the list."""
# Replace this line with your code.
return 0The sample tests · test_streak.py
import random
from streak import longest_rise, longest_rise_brute
CASES = [
([], 0),
([4200], 1),
([3000, 4000, 5000], 3),
([9000, 8000, 7000], 1),
([5000, 6200, 6200, 7100, 8000, 4000], 3),
([1, 3, 2, 4, 5, 6, 1], 4),
]
def test_brute_force_cases():
"""the brute force gives the right length for six small lists"""
assert [longest_rise_brute(steps) for steps, _ in CASES] == [answer for _, answer in CASES]
def test_one_pass_cases():
"""the one-pass version gives the right length for the same six lists"""
assert [longest_rise(steps) for steps, _ in CASES] == [answer for _, answer in CASES]
def test_agrees_with_brute_force():
"""the one-pass version agrees with the brute force on 200 random lists"""
rng = random.Random(7)
for _ in range(200):
steps = [rng.randint(0, 6) for _ in range(rng.randint(0, 15))]
assert longest_rise(steps) == longest_rise_brute(steps), steps
def test_long_rise():
"""the one-pass version handles 200,000 rising days in time"""
assert longest_rise(list(range(200_000))) == 200_000JavaScript · Starter code · streak.mjs
/** Length of the longest run of days, each with more steps than the day before (try every start day). */
export function longestRiseBrute(steps) {
// Replace this line with your code.
return 0;
}
/** The same answer in one pass over the list. */
export function longestRise(steps) {
// Replace this line with your code.
return 0;
}The sample tests · streak.test.mjs
import { test, assert } from 'toolverse:test';
import { longestRise, longestRiseBrute } from './streak.mjs';
const CASES = [
[[], 0],
[[4200], 1],
[[3000, 4000, 5000], 3],
[[9000, 8000, 7000], 1],
[[5000, 6200, 6200, 7100, 8000, 4000], 3],
[[1, 3, 2, 4, 5, 6, 1], 4],
];
test('the brute force gives the right length for six small lists', () => {
assert.deepEqual(CASES.map(([steps]) => longestRiseBrute(steps)), CASES.map(([, answer]) => answer));
});
test('the one-pass version gives the right length for the same six lists', () => {
assert.deepEqual(CASES.map(([steps]) => longestRise(steps)), CASES.map(([, answer]) => answer));
});
test('the one-pass version agrees with the brute force on 200 random lists', () => {
let seed = 7;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
for (let k = 0; k < 200; k++) {
const steps = Array.from({ length: Math.floor(random() * 16) }, () => Math.floor(random() * 7));
assert.equal(longestRise(steps), longestRiseBrute(steps), JSON.stringify(steps));
}
});
test('the one-pass version handles 200,000 rising days in time', () => {
assert.equal(longestRise(Array.from({ length: 200000 }, (_, i) => i)), 200000);
});A hint
For the one-pass version, keep two numbers: run, the length of the rising streak that ends at today, and best, the longest streak seen so far. If today beats yesterday, the streak goes on (run + 1); otherwise a new one starts today (run = 1). Update best after every day.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
References
- brute force (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- Computer Science Curricula 2023: Algorithmic Foundations (AL) (ACM, IEEE Computer Society and AAAI)
- Time complexity of operations on built-in types (Python Software Foundation)
- Sorting Techniques (Python Software Foundation)
- bisect, array bisection algorithm (Python Software Foundation)
- collections: Counter objects (Python Software Foundation)
- ECMAScript 2026 Language Specification, Math.random() (Ecma International)
- random: notes on reproducibility (Python Software Foundation)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress