Learn

Technical Interview Problems in Python: Lists

Pair Sum: Optimized

We’ll explore a common trade-off: time vs. space.

Our previous solution used nested `for`

loops to iterate through each element in the list and then iterate **again** for each element in the list to find their sum for a `O(N^2)`

time complexity.

On the bright side, that solution used `O(1)`

space because we’re not using any additional data structures.

If we sort the list **before** looking for pairs, we can reach `O(N * logN)`

time complexity, but we’re going to go for a `O(N)`

solution by trading away a little space.

Engineering is about trade-offs! This is another opportunity to communicate benefits and drawbacks to the interviewer.

As with other naive solutions, we’re doing more work than is necessary. Given the target integer, what information we can gather in a single iteration?

```
# <> marks the current element
nums = [4, 2, 8, 9, 6]
target = 8
[<4>, 2, 8, 9, 6]
# target - 4 = 4
# we need another 4...
[4, <2>, 8, 9, 6]
# target - 2 = 6
# we need a 6...
[4, 2, <8>, 9, 6]
# target - 8 = 0
# we need a 0...
[4, 2, 8, <9>, 6]
# target - 9 = -1
# we need a -1...
[4, 2, 8, 9, <6>]
# target - 6 = 2
# we need a 2...
```

At each step of the iteration, we know the “complement” number needed to sum to the target.

Use a dictionary to store that complement at each iteration and solve this problem with `O(N)`

time complexity and `O(N)`

space complexity.

Write a function `pair_sum()`

, which has two parameters: `nums`

and `target`

.

`pair_sum()`

should return a list containing a single pair of indices whose values sum to `target`

. This can be any pair that meets the requirements.

If no such values exist, return `None`

.

**Your solution should run in O(N) time and O(N) space!**