Jobs

Interviews

Discussions

Two Sum Less Than K

Easy

Amazon

3 views

Topics:

ArraysTwo PointersBinary Search

You are given an array of integers nums and an integer k. Your task is to find the maximum sum of two distinct numbers in the nums array that is strictly less than k. If no such pair exists, return -1.

For example:

nums = [1, 3, 5, 7], k = 8. The maximum sum less than 8 is 1 + 5 = 6. Therefore, the output should be 6.
nums = [5, 20, 110, 10, 15], k = 40. The possible sums less than 40 are 5+20, 5+10, 5+15, 20+10, 20+15, and 10+15. The largest of these is 20 + 15 = 35. Therefore, the output should be 35.
nums = [1, 2, 3], k = 1. Since no two numbers in the array sum to a value less than 1, the function should return -1.

Describe an algorithm to solve this problem efficiently. What is the time and space complexity of your solution? Consider edge cases such as an empty input array or when no pairs sum to less than k.

Two Sum Less Than K

Easy

Amazon

3 views

Topics:

ArraysTwo PointersBinary Search

For example:

nums = [1, 3, 5, 7], k = 8. The maximum sum less than 8 is 1 + 5 = 6. Therefore, the output should be 6.
nums = [5, 20, 110, 10, 15], k = 40. The possible sums less than 40 are 5+20, 5+10, 5+15, 20+10, 20+15, and 10+15. The largest of these is 20 + 15 = 35. Therefore, the output should be 35.
nums = [1, 2, 3], k = 1. Since no two numbers in the array sum to a value less than 1, the function should return -1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integers in the input array, and for the value of K?
Can the input array contain duplicate numbers, and if so, should I consider pairs with the same number at different indices?
If there are multiple pairs whose sum is less than K, should I return the pair with the largest sum, or is any such pair sufficient?
If no such pair exists whose sum is less than K, what should I return?
Is the input array guaranteed to have at least two elements?

Brute Force Solution

Approach

The brute force approach to this problem is like trying every possible pair of numbers. We will look at each combination to see if it meets our condition. We aim to find the largest sum of two numbers that is still smaller than the specified limit.

Here's how the algorithm would work step-by-step:

Take the first number in the set.
Pair it with every other number in the set and add them together.
If the sum is smaller than the specified limit, remember this sum.
Repeat this process for the second number, pairing it with every other number (avoiding repeats).
Continue this process until you've paired every number with every other number.
After checking all possible pairs, find the largest sum that you remembered. This is the answer.

Code Implementation

def two_sum_less_than_k_brute_force(numbers, limit):
    largest_sum_smaller_than_limit = -1

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # For each number, iterate through the rest of the numbers
        for second_number_index in range(first_number_index + 1, len(numbers)):

            current_sum = numbers[first_number_index] + numbers[second_number_index]

            # Check if the current sum is less than the limit
            if current_sum < limit:

                # Keep track of the largest sum that satisfies this condition
                largest_sum_smaller_than_limit = max(largest_sum_smaller_than_limit, current_sum)

    return largest_sum_smaller_than_limit

Big(O) Analysis

Time Complexity

O(n²) – The proposed solution iterates through the array to select the first number in a pair. For each of these n numbers, it then iterates through the remaining elements in the array to find a second number to pair with the first. This nested iteration performs a sum calculation for approximately n * (n-1) / 2 pairs. Therefore, the total number of operations is proportional to n squared. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The described brute force approach only requires a single variable to store the largest sum found so far. No auxiliary data structures, like arrays or hash maps, are used to store intermediate results or track visited elements. The memory required for this single variable remains constant irrespective of the input size N (number of elements in the set). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The best way to solve this problem is to first organize the numbers in ascending order. Then, use two pointers, one starting at the beginning and the other at the end, to efficiently find the pair that adds up to the largest sum less than the target value.

Here's how the algorithm would work step-by-step:

First, sort all the numbers from smallest to largest.
Set up two markers: one at the very beginning and one at the very end of the sorted list.
Add the numbers at both marker positions together.
If the sum is less than the target value, remember that sum as the best one so far and move the marker on the left one position to the right to try to get a larger sum.
If the sum is greater than or equal to the target value, move the marker on the right one position to the left to try to get a smaller sum.
Keep doing steps 3-5 until the two markers cross each other.
The best sum you remembered along the way is the answer.

Code Implementation

def two_sum_less_than_k(numbers, target):
    numbers.sort()

    left_pointer = 0
    right_pointer = len(numbers) - 1
    max_sum_less_than_target = -1

    while left_pointer < right_pointer:
        current_sum = numbers[left_pointer] + numbers[right_pointer]

        # Update the result if current sum is less than target.
        if current_sum < target:

            max_sum_less_than_target = max(max_sum_less_than_target, current_sum)

            # Try to find a larger sum.
            left_pointer += 1

        # We need a smaller sum.
        else:

            right_pointer -= 1

    return max_sum_less_than_target

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this approach is sorting the input array, which takes O(n log n) time. After sorting, the two-pointer approach iterates through the array once, performing constant-time operations (addition, comparison, and pointer movement) at each step. This linear iteration takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The described algorithm primarily uses a two-pointer approach on a sorted array. Sorting in-place modifies the input array directly and doesn't allocate significant auxiliary space, assuming an in-place sort is used. The algorithm uses a constant number of variables to store the two pointers, best sum so far, and intermediate sums, irrespective of the input array's size, denoted as N. Therefore, the auxiliary space complexity is O(1), indicating constant extra space usage.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no sum less than K is possible.
Input array with fewer than 2 elements	Return 0, as no pair can be formed.
All numbers in the array are greater than or equal to K	Return 0, as no sum less than K is possible.
Array contains only one unique number repeated multiple times	Ensure that the algorithm does not add the number to itself, unless K is greater than twice the number.
Large input array (scalability considerations)	Sorting the array upfront allows for a two-pointer approach with O(n log n) time complexity, avoiding quadratic complexity of naive solutions.
Negative numbers in the input array	The algorithm should correctly handle negative numbers and consider their contribution to the sum.
K is a very small negative number	The solution should correctly identify the largest possible sum less than a negative K, potentially being a large negative number itself.
Duplicate pairs exist	The two-pointer approach implicitly handles duplicate pairs by moving pointers and ensuring the calculated sum is the largest possible sum less than K.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integers in the input array, and for the value of K?
Can the input array contain duplicate numbers, and if so, should I consider pairs with the same number at different indices?
If there are multiple pairs whose sum is less than K, should I return the pair with the largest sum, or is any such pair sufficient?
If no such pair exists whose sum is less than K, what should I return?
Is the input array guaranteed to have at least two elements?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the set.
Pair it with every other number in the set and add them together.
If the sum is smaller than the specified limit, remember this sum.
Repeat this process for the second number, pairing it with every other number (avoiding repeats).
Continue this process until you've paired every number with every other number.
After checking all possible pairs, find the largest sum that you remembered. This is the answer.

Code Implementation

def two_sum_less_than_k_brute_force(numbers, limit):
    largest_sum_smaller_than_limit = -1

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # For each number, iterate through the rest of the numbers
        for second_number_index in range(first_number_index + 1, len(numbers)):

            current_sum = numbers[first_number_index] + numbers[second_number_index]

            # Check if the current sum is less than the limit
            if current_sum < limit:

                # Keep track of the largest sum that satisfies this condition
                largest_sum_smaller_than_limit = max(largest_sum_smaller_than_limit, current_sum)

    return largest_sum_smaller_than_limit

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort all the numbers from smallest to largest.
Set up two markers: one at the very beginning and one at the very end of the sorted list.
Add the numbers at both marker positions together.
If the sum is less than the target value, remember that sum as the best one so far and move the marker on the left one position to the right to try to get a larger sum.
If the sum is greater than or equal to the target value, move the marker on the right one position to the left to try to get a smaller sum.
Keep doing steps 3-5 until the two markers cross each other.
The best sum you remembered along the way is the answer.

Code Implementation

def two_sum_less_than_k(numbers, target):
    numbers.sort()

    left_pointer = 0
    right_pointer = len(numbers) - 1
    max_sum_less_than_target = -1

    while left_pointer < right_pointer:
        current_sum = numbers[left_pointer] + numbers[right_pointer]

        # Update the result if current sum is less than target.
        if current_sum < target:

            max_sum_less_than_target = max(max_sum_less_than_target, current_sum)

            # Try to find a larger sum.
            left_pointer += 1

        # We need a smaller sum.
        else:

            right_pointer -= 1

    return max_sum_less_than_target

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no sum less than K is possible.
Input array with fewer than 2 elements	Return 0, as no pair can be formed.
All numbers in the array are greater than or equal to K	Return 0, as no sum less than K is possible.
Array contains only one unique number repeated multiple times	Ensure that the algorithm does not add the number to itself, unless K is greater than twice the number.
Large input array (scalability considerations)	Sorting the array upfront allows for a two-pointer approach with O(n log n) time complexity, avoiding quadratic complexity of naive solutions.
Negative numbers in the input array	The algorithm should correctly handle negative numbers and consider their contribution to the sum.
K is a very small negative number	The solution should correctly identify the largest possible sum less than a negative K, potentially being a large negative number itself.
Duplicate pairs exist	The two-pointer approach implicitly handles duplicate pairs by moving pointers and ensuring the calculated sum is the largest possible sum less than K.