Arrays and Hashing
8 / 170Arrays and HashingLesson 3 of 10About 39 min
Instead of searching for a partner, store what would complete each element and let the partner find you.
A whole family of problems asks you to find two elements that stand in some fixed relationship to each other. Pairs that differ by k. Pairs that sum to a target. Pairs where one is double the other.
The brute force is always the same: check every pair, O(n squared). The improvement is always the same too, and it is worth learning as one idea rather than as several tricks.
Here it is for the difference version. Note the order: look up first, record afterwards.
def has_pair_with_difference(nums, k): seen = set() for value in nums: if value - k in seen: return True seen.add(value) return False print(has_pair_with_difference([1, 5, 9, 3], 4)) # 5 and 9 differ by 4print(has_pair_with_difference([1, 5, 9, 3], 7))A set answers whether. If the problem wants the positions of the two elements, swap the set for a dict from value to the index where it appeared. The loop does not otherwise change.
def index_of_partner(nums, k): seen = {} # value -> index where it appeared for i, value in enumerate(nums): if value - k in seen: return [seen[value - k], i] seen[value] = i return [] print(index_of_partner([1, 5, 9, 3], 4))Run index_of_partner on nums = [4, 1, 6, 9] with k = 5, so each element looks for a partner equal to value - 5. Fill in the partner being looked for, whether it was found in seen, and what seen holds after the step. Write the dict as {} when empty, otherwise like {4: 0}. Write found as yes or no.
| i | value | partner wanted | found | seen after |
|---|---|---|---|---|
| 0 | 4 | |||
| 1 | 1 | |||
| 2 | 6 |
Give the time and space complexity of the one-pass version above, in terms of n, the length of nums.
def index_of_partner(nums, k): seen = {} for i, value in enumerate(nums): if value - k in seen: return [seen[value - k], i] seen[value] = i return []Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.