Two Sum Less Than K — Easy Problem & Solution

Problem statement

Find two distinct indices i < j maximising nums[i] + nums[j] subject to the sum being strictly less than k.

Return that maximum sum, or -1 if no pair qualifies.

Example 1

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: 24 + 34 = 58 is the largest sum below 60.

Example 2

Input: nums = [10,20,30], k = 15
Output: -1
Explanation: Every pair sums to at least 30.

Example 3

Input: nums = [1,2], k = 4
Output: 3

Constraints

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 1000
• 1 <= k <= 2000

How to solve Two Sum Less Than K

After sorting, the two-pointer sweep considers every left element paired with the largest partner that could work, which is exactly what maximising under an upper bound needs.

Approach

1. Sort a copy of nums.
2. Start lo at the front and hi at the back.
3. If s[lo] + s[hi] < k, record it as a candidate and advance lo — no larger partner exists for this lo.
4. Otherwise retreat hi.

Why it works

For a fixed lo, the sums decrease as hi decreases, so the first hi that brings the sum under k gives the best pair for that lo. Advancing lo afterwards is safe because every larger hi has already been ruled out for the remaining lefts.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Strictly less than k, so a sum equal to k does not count.
• Returning 0 when nothing qualifies — the sentinel is -1.
• A single-element array has no pair at all.

Reference solution

Python

from typing import List

def twoSumLessThanK(nums: List[int], k: int) -> int:
    s = sorted(nums)
    lo, hi = 0, len(s) - 1
    best = -1
    while lo < hi:
        total = s[lo] + s[hi]
        if total < k:
            best = max(best, total)
            lo += 1
        else:
            hi -= 1
    return best

JavaScript

var twoSumLessThanK = function(nums, k) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var lo = 0, hi = s.length - 1, best = -1;
    while (lo < hi) {
        var sum = s[lo] + s[hi];
        if (sum < k) {
            if (sum > best) best = sum;
            lo++;
        } else hi--;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy