Archived

two sum

An old note — I haven't updated it since I wrote it.

<iframe id="embed_player" frameborder="0" width="280" height="216" src="https://alsoisland.airtime.pro/embed/player?stream=auto&skin=1"></iframe>

Two Sum is problem #1 on leetcode.com, and can, as such, be considered a classic.

The gist

We're given a list: [2, 7, 11, 15] and want to find two numbers adding up to target 9.

The answer is 2 + 7 = 9.

Two pointer approach

The two pointer approach first involves sorting the array, as it will only work on sorted integers.

graph TD A[start] --> C C{s = Ai + Aj} C -->|s == k| D[return i, j] C -->|s < k| E[i += 1] C -->|s > k| F[j -= 1] E --> C F --> C

In other words, our pointer i starts at the left of the list, and our pointer j and the right. If A[i] + A[j] is equals to k we've found our solution. If it's less, then we need to increment i. If it's greater, then we need to decrement j.