1099. Two Sum Less Than K

EasyArrayTwo PointersBinary SearchSorting
Leetcode Link

Problem Description

Given an array nums of integers and an integer k, the challenge is to find the maximum possible sum of any two distinct elements (i.e., nums[i] and nums[j] where i < j) that is less than k. To clarify:

  • The sum should be less than k.
  • You need to find two different elements in the array (no element should be used twice).
  • The maximum sum needs to be returned.
  • If it is not possible to find such a pair, the function should return -1.

Intuition

The intuition behind the solution involves sorting the array first. When the array is sorted, we can use a two-pointer approach to efficiently find two numbers with the desired property. The first pointer i starts at the beginning of the list, and the second pointer j starts at the end. The sorting allows us to make decisions based on the sum of the elements at the two pointers:

  • If the sum of the two pointed-to numbers is less than k, then we have a valid pair, and we can try to find a bigger sum by moving pointer i one step to the right (increasing the sum).
  • If the sum is greater or equal to k, then we must reduce the sum by moving pointer j one step to the left.

Throughout the process, we maintain the highest sum obtained that is less than k, and this becomes our answer. The approach works because sorting the array allows us to know that, as i moves to the right, the sum will increase, and as j moves to the left, the sum will decrease. This helps us avoid considering every possible pair, which reduces the time complexity significantly compared to a brute-force approach.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following uses divide and conquer strategy?

Solution Approach

The solution makes effective use of a two-pointer technique with a sorted array to optimize the process of finding the maximum sum of a pair of integers that is less than k. Here's a step-by-step breakdown of the implementation:

  1. Sort the Array: The first step is to sort the nums array which will arrange the integers in non-decreasing order. Sorting is crucial because it allows us to explore potential sums from the smallest and largest values and move our pointers based on the comparison with k.

  2. Initialize Two Pointers: We set up two pointers, i and j, where i starts from the beginning of the array (0 index) and j starts from the end (len(nums) - 1). These pointers will traverse the array from opposite ends towards each other.

  3. Initialize the Answer Variable: An ans variable is initialized with a value of -1. This variable will hold the maximum sum encountered that is still less than k.

  4. Iterate with Two Pointers: We then enter a while loop that will continue as long as i is less than j. Inside the loop, we do the following:

    • Calculate the sum (s) of the elements pointed to by i and j.
    • If this sum is less than k, compare it with the current ans variable and update ans to be the maximum of the two. Since we want to maximize our sum, we then move i one step to the right (i.e., i += 1) to potentially increase our sum.
    • If the sum is greater than or equal to k, we must reduce it. To do this, we move j one step to the left (i.e., j -= 1), as this will use a smaller number for the sum.

  5. Return the Answer: After the loop terminates, the variable ans will contain the maximum sum less than k that we have found, or -1 if no such sum exists. We return ans.

By following these steps, the solution ensures that every move of either i or j is purposeful and brings us closer to the maximum sum we can achieve under the constraint that it must be less than k. Through this optimization, the solution effectively manages the potential combinations of pairs, resulting in a more efficient algorithm.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example Walkthrough

Suppose we have an array nums = [34, 23, 1, 24, 75, 33, 54, 8] and an integer k = 60.

According to our solution approach:

  1. Sort the Array: First, we sort the array: nums = [1, 8, 23, 24, 33, 34, 54, 75].

  2. Initialize Two Pointers: We set two pointers, i = 0 (pointing to 1) and j = 7 (pointing to 75).

  3. Initialize the Answer Variable: We initialize an answer variable with ans = -1.

  4. Iterate with Two Pointers: We enter the while loop with the condition i < j.

    • During the first iteration, the sum s = nums[i] + nums[j] = 1 + 75 = 76 which is greater than k. Hence, we decrease j to point to the second last element (j = 6 pointing to 54).
    • In the next iteration, the sum s = 1 + 54 = 55. This sum is less than k, so we update ans = 55. We want to see if we can get closer to k, so we increase i to point to the next element (i = 1 pointing to 8).
    • Now, the sum s = 8 + 54 = 62, which is greater than k. So we decrease j to point to j = 5 (pointing to 34).
    • The sum s = 8 + 34 = 42. This is less than k and greater than the current ans, so we update ans = 42. We try increasing i again (i = 2 pointing to 23).
    • The sum s = 23 + 34 = 57. It is less than k and greater than ans, so we update ans = 57. Since we are still trying to maximize the sum, we increment i again (i = 3, pointing to 24).
    • Continuing the iteration, we keep moving i and j to find larger sums until i is no longer less than j.

  5. Return the Answer: Once i >= j, the loop terminates. Our ans is the largest sum found which is less than k, which in this case is 57. Hence, we would return 57.

Solution Implementation

1class Solution:
2    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
3        # Sort the list to apply the two-pointer technique
4        nums.sort()
5      
6        # Initialize two pointers, one at the start and one at the end of the list
7        left_pointer, right_pointer = 0, len(nums) - 1
8      
9        # Initialize the answer variable with -1 which will be returned if no suitable pair is found
10        max_sum = -1
11      
12        # Iterate until the two pointers meet
13        while left_pointer < right_pointer:
14            # Calculate the current sum of the values pointed by the two pointers
15            current_sum = nums[left_pointer] + nums[right_pointer]
16          
17            # If the sum is less than k, it's a potential candidate for our answer
18            if current_sum < k:
19                # Update the answer with the maximum sum encountered which is less than k
20                max_sum = max(max_sum, current_sum)
21                # Move the left pointer to the right to potentially increase the sum
22                left_pointer += 1
23            else:
24                # If the sum is greater than or equal to k, move the right pointer to the left
25                # This is to try and find a smaller sum that is less than k
26                right_pointer -= 1
27      
28        # Return the maximum sum that we have found which is less than k, or -1 if there is no such sum
29        return max_sum
30
1class Solution {
2
3    /**
4     * Finds the maximum sum of any pair of numbers in the array that is less than K
5     *
6     * @param numbers Array of integers
7     * @param targetSum Target sum K we are trying not to exceed
8     * @return Maximum sum of a pair of numbers less than K, or -1 if such a pair does not exist
9     */
10    public int twoSumLessThanK(int[] numbers, int targetSum) {
11        // Sort the array in ascending order
12        Arrays.sort(numbers);
13      
14        // Initialize the answer as -1 assuming there might be no valid pairs
15        int maximumSum = -1;
16      
17        // Initialize two pointers, one at the beginning (left) and one at the end (right) of the array
18        int left = 0, right = numbers.length - 1;
19
20        // Iterate over the array using the two-pointer approach
21        while (left < right) {
22            // Calculate the sum of values at the left and right pointers
23            int sum = numbers[left] + numbers[right];
24          
25            // If the sum is less than the targetSum, update maximumSum and move the left pointer forward
26            if (sum < targetSum) {
27                maximumSum = Math.max(maximumSum, sum);
28                left++;
29            } else {
30                // If the sum is greater than or equal to targetSum, move the right pointer backward
31                right--;
32            }
33        }
34      
35        // Return the maximum sum found, or -1 if no suitable pair was found
36        return maximumSum;
37    }
38}
39
1class Solution {
2public:
3    int twoSumLessThanK(vector<int>& nums, int k) {
4        // Sort the array to use the two-pointer technique
5        sort(nums.begin(), nums.end());
6      
7        // Initialize answer to -1 since we need a sum less than k
8        int maxSum = -1;
9      
10        // Initialize two pointers, one at the beginning and one at the end of the sorted array
11        int left = 0;
12        int right = nums.size() - 1;
13      
14        // Use the two-pointer technique to find the two numbers with a sum less than k
15        while (left < right) {
16            // Calculate the sum of the two pointed elements
17            int sum = nums[left] + nums[right];
18          
19            // If the current sum is less than k, it's a potential answer
20            if (sum < k) {
21                // Update maxSum to the maximum of itself and the current sum
22                maxSum = max(maxSum, sum);
23              
24                // Move the left pointer to the right to increase the sum
25                ++left;
26            } else {
27                // If the sum is greater than or equal to k, decrease the sum by moving the right pointer to the left
28                --right;
29            }
30        }
31      
32        // Return the maximum sum found that is less than k, or -1 if no such sum exists
33        return maxSum;
34    }
35};
36
1function twoSumLessThanK(nums: number[], k: number): number {
2    // Sort the array in ascending order 
3    nums.sort((a, b) => a - b);
4
5    // Initialize the variable to store the maximum sum found that is less than k
6    let maxSum = -1;
7
8    // Initialize two pointers, one starting from the beginning of the array (left) and
9    // the other from the end of the array (right)
10    let left = 0;
11    let right = nums.length - 1;
12
13    // Iterate through the array while the left pointer is less than the right pointer
14    while (left < right) {
15        // Calculate the sum of the elements pointed by the left and right pointers
16        const sum = nums[left] + nums[right];
17
18        // If the sum is less than k, check if it is greater than the current maxSum
19        // and update maxSum if necessary. Then move the left pointer one step to the right.
20        if (sum < k) {
21            maxSum = Math.max(maxSum, sum);
22            left++;
23        } else {
24            // If the sum is greater than or equal to k, move the right pointer one step to the left
25            right--;
26        }
27    }
28
29    // Return the maximum sum found or -1 if no such sum exists
30    return maxSum;
31}
32
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the provided function is O(N log N) because of the sort operation. The subsequent while loop has at most N iterations (where N is the length of nums), since each iteration either increments i or decrements j, ensuring that each element is considered at most once. However, the sort operation dominates the time complexity.

Therefore, the overall time complexity is associated with the sorting step, which for most sorting algorithms like Timsort (used in Python's .sort() method), is O(N log N).

Space Complexity

The space complexity of the function is O(1) or constant space complexity, assuming that the sort operation is done in-place. Aside from sorting, only a fixed number of integer variables are introduced (i, j, s, and ans), which do not depend on the size of the input array nums.

If the sorting algorithm used is not in-place, the space complexity would be O(N) due to the space required to create a separate sorted array. However, since Python's default .sort() method sorts the array in place, we consider the space complexity to be O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ