Breaking Down Two Sum

If you ever prepared for coding interview, you probably know this one. Two Sum — sitting at #1 out of thousands of LeetCode problems.

Source: LeetCode

LeetCode 1. Two Sum →

If you open Companies tab, you can see so many companies still asking this problem. Honestly it's not that difficult. You can solve it with brute force double loop, or more efficiently with HashMap in O(n). So... is that it?

Brute Force vs HashMap

Let me go through two basic approaches first.

Brute Force — O(n²), Space O(1)

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

HashMap — O(n), Space O(n)

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

HashMap is clearly better. But I think stopping here is not enough.

Is That Really It?

While I was preparing for interviews, I started thinking about follow-up questions. And this is where it gets more interesting.

Let's say you solved it with HashMap, and interviewer asks:

"Is there a way to do this with better space complexity?"

If you can say "yes, assuming the array is sorted, we can use Two Pointers and get O(1) space" — you're not just solving the problem. You're showing that you understand the tradeoffs. I think that's what makes a difference in interviews.

What is Two Pointer?

Basic idea is — put one pointer at the start, one at the end. If sum is too small, move left pointer right. If too big, move right pointer left.

One important thing: array needs to be sorted first.

That's actually why I think this approach is good for follow-ups. You're not just giving another solution — you're also showing that you know sorting is required for this to work.

Two Pointer — O(n), Space O(1)

def twoSum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1

Structure is pretty simple. Two pointers at both ends, moving inward based on the sum. Once you understand what to use as your anchor point, Three Sum and Four Sum follow the exact same pattern.

Know Two Pointer? Three Sum and Four Sum Come With It

This is honestly the main reason I think you should learn Two Pointer for Two Sum. The pattern extends naturally.

Three Sum — O(n²), Space O(1)

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return res

Same structure as Two Sum. The difference is we fix one value i as anchor, then run Two Pointers on the remaining elements. Think of it as — pick one starting point, then do Two Sum from there.

Four Sum — O(n³), Space O(1)

def fourSum(nums, target):
    nums.sort()
    res = []
    for i in range(len(nums) - 3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j] == nums[j-1]:
                continue
            left, right = j + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    res.append([nums[i], nums[j], nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return res

One step further from Three Sum. Now we fix two anchors — i and j — then run Two Pointers on the rest. The core pattern is always same. Only thing that changes is how many anchors you fix.

Follow-up Questions Worth Knowing

These might not come up as actual coding problems, but being able to talk through them is good to have.

• What if input is really large? → External sort first, then Two Pointer. Or distribute the work.
• What if there are multiple valid pairs? → Modify logic to collect all pairs, and be careful with duplicates.
• What if it's streaming input? → HashMap works better here. Sliding window might also apply.
• What about distributed environment? → Partition the data, process each part, then merge results.

You can just solve Two Sum with HashMap and move on. But I think knowing Two Pointer as well prepares you way better for follow-up questions.

Still figuring things out myself, but going one layer deeper on problems like this — I think that's what makes a difference.