This is the classic, literally Leetcode question 1. It’s an OK question. It admits a “naive” solution of try-every-pair, and also enables some deeper thought. I don’t have a good read on whether that deeper thought should be considered expected in an interview setting.

Naive Solution

The naive solution is try-every-pair. This is an accessible example of a concept I like, where we have the explicit object (in our case, an array), but we’re really exploring an implicit object (in our case, a sequence of pairs of elements, those elements drawn from an array). We can be careful about precisely which pairs we’re exploring.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i]+nums[j] == target:
                    return [i, j]

Not-Better Solution

The interesting thing is how to derive the better solution. Let’s formulate it in terms of the condition we “care” about, nums[i]+nums[j] == target. With arithmetic, we can say that’s the same condition as: nums[i] == target – nums[j], (we subtracted nums[j] from each side).

So we can derive a new sequence, diffNums, where we assign diffNums[j] = target – nums[j]. Now what would our loop look like?

class Solution(object):
    def twoSum(self, nums, target):
        diffNums = [target-nums[i] for i in range(len(nums))]
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i] == diffNums[j]:
                    return [i, j]

This is not faster by any measure: asymptotically it’s still O(n^2), and now we have an extra intermediate array diffNums to instantiate. Sure enough, it’s too slow for Leetcode, haha.

However, a careful look at our condition now is enticing: we’re “just” seeing if the collection nums has any element in common with the collection diffNums. That’s set-membership! So let’s recast things:

Faster Solution

We ultimately need to return the indices. So let’s have diffNums be a mapping from target-nums[i] : i.

class Solution(object):
    def twoSum(self, nums, target):
        diffNums = {target-nums[i] : i for i in range(len(nums))}
        for i in range(len(nums)):
            v = nums[i]
            if v in diffNums and i != diffNums[v]:
                return [i, diffNums[v]]

A lot has changed! Crucially, we have the if v in diffNums condition: that captures the whole inner for-loop! Even better, because diffNums is a map, we can expect that lookup to be roughly constant time, instead of linear. This brings our algorithm down to roughly-linear time. (Note that diffNums[v] is basically j in this loop.)

Conclusion

This problem grew on me, in terms of introducing some intermediate programming thoughts. I think if we have to use this an interview question, assuming the candidate is stuck on getting the faster solution, I’d prompt them to that not-better solution and see where they take it. More introductory questions here.