Two Sum (Part 3) Amazon Python Interview Question

Given an array of integers nums and an integer k, return the largest possible maxSum < k such that maxSum = nums[i] + nums[j] and i ≠ j. If no maxSum < k 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 nums 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 sum < k.

The associated time complexity is $O(n^{2})$. This means that as the length of nums 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 nums 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 sum == k, we can still use similar logic to keep track of the greatest sum < k seen so far (let's call this max_sum), and avoid looking at pairs that we know cannot improve max_sum.

Code

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

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

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

This approach looks at each value at most once, so finding max_sum when nums 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.

def max_two_sum(nums, k):
  
  # Sort so that we can use two-pointer approach
  nums.sort()
  
  # initialize pointers
  left = 0
  right = len(nums)-1
  
  # initialize, in case we find that no pair sums up to less than k
  max_sum = -1
  
  while left < right:
    cur_sum = nums[left] + nums[right]
    
    if cur_sum >= k:
      '''
      lowest possible sum including right is
      greater than k, so no need to keep considering right
      '''
      right = right-1
    else:
      '''
      cur_sum is greatest possible sum including left so any other 
      pair including left cannot possibly improve max_sum
      '''
      max_sum = max(cur_sum, max_sum)
      left = left+1
    
  return max_sum