Two Sum (Part 3) Amazon Python Interview Question

Given an array of integers and an integer , return the largest possible such that and . If no is possible, return -1.

Example #1

Input: nums = [34, 23, 1, 24, 75, 33, 54, 8], k = 60

Output: 58

Explanation: The greatest possible sum less than 60 is 58, made by adding 34 + 24

Brute Force Approach

Because is not sorted, if we were to dive in right away, the best we could do is simply inspect each pair, keep track of the greatest .

The associated time complexity is $O(n^{2})$. This means that as the length of grows, the max number of operations required will scale by $n^{2}$. This is due to checking $n*(n-1)$ distinct pairs.

Sorted Approach

We can do better by sorting up front! This can be done in $O(n\log n)$ time.

To get a sense of why this is the case, read up here about merge sort and it's time complexity.

If we can solve the problem for the sorted array in less than $O(n^{2})$ time then it's worth doing the sort! And we've seen a sorted Two Sum problem before!

Though we are not looking for the values where , we can still use similar logic to keep track of the greatest seen so far (let's call this ), and avoid looking at pairs that we know cannot improve .

Code

The approach is very similar to the sorted Two Sum problem.

We use two pointers, one on each end ( and ), and eliminate options from the outside in according to how the sum of the current two values () compares to .

1. If then we need not continue to consider . Any other pair with in it will also be greater than or equal to .
2. If then we need not continue to consider . Any other pair with will be less than the current , so we can update and move on.

This approach looks at each value at most once, so finding when is sorted has a linear time complexity: $O(n)$. The complexity of the full solution is limited to $O(n \log n)$ by the sorting step, and therefore better than the $O(n^{2})$ brute force approach.