Two Sum Less Than K - Solution & Explanation
Problem Statement
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 <= 2000
Approach Overview
Problem 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 1: Sorting + Binary Search
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.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Sorting + Two Pointers
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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting + Binary Search | — |
| Sorting + Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 1099: Two Sum Less Than K - Interview Prep Ep 6 • Fisher Coder • 3,670 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Two Sum Less Than K easy or hard?
Two Sum Less Than K Python/Java solution
How to solve Two Sum Less Than K in O(n)?
What is the best approach for Two Sum Less Than K?
Is Two Sum Less Than K asked at Google/Amazon/Meta?
What data structure is used in Two Sum Less Than K?
What is the time complexity of Two Sum Less Than K?
Ready to solve this problem?
Practice Two Sum Less Than K with our built-in code editor and test cases.
Practice on FleetCode