DSA series #01 · interactive

One problem, three ways

DSA is not about writing code. It is about spotting the pattern and knowing more than one way to solve it. Here is the classic example: find two numbers that add up to 24.

Try each number with every number after it.

[0]

↑i

[1]

↑j

[2]

[3]

[4]

[5]

[6]

[7]

4 + 11 = 15 ≠ 24

checks

Trade-off: No extra memory, easy to get right. Falls over once n grows. time O(n²) · extra memory O(1)

Checks to find the answer in these 8 numbers

Check every pair
23
Sort + two pointers
29
One pass + hash map
6

With 8 numbers, checking every pair is not slow, and sorting first actually costs more. Big-O ignores constants and small inputs. That is why you measure before you optimise.

Now make the input bigger

log scale · 1 check = 1 ns

Numbers in the array (n)1,000,000

Check every pair O(n²)500B checks · 8.3 min
Sort + two pointers O(n log n)20.9M checks · 20.9 ms
One pass + hash map O(n)1M checks · 1.0 ms

Same problem, same answer. At a million numbers the pair check takes minutes, the hash map about a millisecond. Knowing the pattern is what lets you pick.