Watch 10 video solutions for Two Sum Less Than K, a easy level problem involving Array, Two Pointers, Binary Search. This walkthrough by Fisher Coder has 3,634 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |