Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.
Example 1:
Input: nums = [34,23,1,24,75,33,54,8], k = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60.
Example 2:
Input: nums = [10,20,30], k = 15 Output: -1 Explanation: In this case it is not possible to get a pair sum less that 15.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 10001 <= k <= 2000Problem Overview: Given an integer array nums and an integer k, return the maximum sum of any two different elements such that the sum is strictly less than k. If no such pair exists, return -1. The task is essentially a constrained pair search where you want the largest possible sum without crossing the threshold.
Approach 1: Sorting + Binary Search (Time: O(n log n), Space: O(1) to O(log n))
Start by sorting the array using a standard sorting algorithm. For each index i, treat nums[i] as the first number in the pair. The second number must be less than k - nums[i]. Use binary search on the remaining portion of the array to find the largest value strictly smaller than this limit. This works because the array is sorted, allowing efficient lookup of the best candidate. Track the maximum valid pair sum while iterating through the array. Sorting costs O(n log n) and each binary search takes O(log n), giving an overall complexity of O(n log n) with constant or logarithmic extra space depending on the sorting implementation.
Approach 2: Sorting + Two Pointers (Time: O(n log n), Space: O(1))
Sort the array first, then apply the classic two pointers pattern. Place one pointer at the start (left) and the other at the end (right). Compute the current sum nums[left] + nums[right]. If the sum is greater than or equal to k, decrease right to reduce the sum. If the sum is less than k, update the best answer and move left forward to try a larger value. Because the array is sorted, decreasing the right pointer always reduces the sum and increasing the left pointer increases it. Each element is visited at most once after sorting, making the scan O(n). Combined with sorting, the total complexity is O(n log n) with constant extra space.
Recommended for interviews: The two‑pointer approach is typically expected. It demonstrates understanding of sorted array properties and efficient pair scanning. The binary search method is still valid and shows strong algorithmic thinking, but two pointers are simpler and more commonly used in array pair optimization problems. Mentioning both approaches in an interview shows you recognize multiple ways to leverage sorting.
We can first sort the array nums, and initialize the answer as -1.
Next, we enumerate each element nums[i] in the array, and find the maximum nums[j] in the array that satisfies nums[j] + nums[i] < k. Here, we can use binary search to speed up the search process. If we find such a nums[j], then we can update the answer, i.e., ans = max(ans, nums[i] + nums[j]).
After the enumeration ends, return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
Similar to Solution 1, we can first sort the array nums, and initialize the answer as -1.
Next, we use two pointers i and j to point to the left and right ends of the array, respectively. Each time we judge whether s = nums[i] + nums[j] is less than k. If it is less than k, then we can update the answer, i.e., ans = max(ans, s), and move i one step to the right, otherwise move j one step to the left.
After the enumeration ends, return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Sorting + Binary Search | — |
| Sorting + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Binary Search | O(n log n) | O(1) to O(log n) | When you want to evaluate each element independently and find the best partner using binary search |
| Sorting + Two Pointers | O(n log n) | O(1) | Best practical solution after sorting; efficient linear scan for optimal pair sum |
LeetCode 1099: Two Sum Less Than K - Interview Prep Ep 6 • Fisher Coder • 3,634 views views
Watch 9 more video solutions →Practice Two Sum Less Than K with our built-in code editor and test cases.
Practice on FleetCode