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.