Two Sum Less Than K
Problem
Given an integer array nums and integer k, return the maximum sum s = nums[i] + nums[j] such that 0 ≤ i < j < n and s < k. If no such pair exists, return -1.
nums = [34, 23, 1, 24, 75, 33, 54, 8], k = 6058def two_sum_less_than_k(nums, k):
nums = sorted(nums)
l, r = 0, len(nums) - 1
best = -1
while l < r:
s = nums[l] + nums[r]
if s < k:
best = max(best, s)
l += 1
else:
r -= 1
return bestfunction twoSumLessThanK(nums, k) {
nums = nums.slice().sort((a, b) => a - b);
let l = 0, r = nums.length - 1, best = -1;
while (l < r) {
const s = nums[l] + nums[r];
if (s < k) { best = Math.max(best, s); l++; }
else r--;
}
return best;
}class Solution {
public int twoSumLessThanK(int[] nums, int k) {
Arrays.sort(nums);
int l = 0, r = nums.length - 1, best = -1;
while (l < r) {
int s = nums[l] + nums[r];
if (s < k) { best = Math.max(best, s); l++; }
else r--;
}
return best;
}
}int twoSumLessThanK(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int l = 0, r = (int)nums.size() - 1, best = -1;
while (l < r) {
int s = nums[l] + nums[r];
if (s < k) { best = max(best, s); l++; }
else r--;
}
return best;
}Explanation
We want the largest pair sum that stays strictly below k. Checking every pair would be slow, so we first sort the array and then sweep with two pointers, keeping a running best.
After sorting, place l at the smallest value and r at the largest. Look at s = nums[l] + nums[r]. If s < k, it is a valid candidate, so we update best = max(best, s). Since nums[l] is the smallest available left value, no other right element can pair with it to do better, so we move on with l++ to try a bigger left number.
If instead s >= k, the sum is too large. The only way to shrink it is to use a smaller right value, so we do r--. We start best at -1 so that if no pair ever qualifies, that's what we return.
Example: nums = [34, 23, 1, 24, 75, 33, 54, 8], k = 60. Sorted it is [1, 8, 23, 24, 33, 34, 54, 75]. Pairs like 1+75=76 ≥ 60 push r down; eventually 24 + 34 = 58 < 60 becomes the best valid sum, so the answer is 58.
Sorting costs O(n log n) and the sweep is linear, so the sort dominates the running time.