Two Sum Less Than K

Easy
751.

Two Sum Less Than K

Two Sum Less Than K is an easy coding problem on arrays, sorting and two pointers, asked in Amazon, Infosys and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var twoSumLessThanK = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Two Sum Less Than K — Solution in Python, Java & C++

Two Sum Less Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and sorting.

Two Sum Less Than K is an easy coding problem on arrays, sorting and two pointers, asked in Amazon, Infosys and Zoho interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Two Pointers
  • Asked at: Amazon, Infosys, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Two Sum Less Than K

  1. Hint 1

    Sort, then walk two pointers inward from the ends.

  2. Hint 2

    If the current sum is already below k, it is the best for this left element — record it and move the left pointer up.

  3. Hint 3

    Otherwise the sum is too big, so move the right pointer down.

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

Java

public static int twoSumLessThanK(int[] nums, int k) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int lo = 0, hi = s.length - 1, best = -1;
    while (lo < hi) {
        int sum = s[lo] + s[hi];
        if (sum < k) {
            best = Math.max(best, sum);
            lo++;
        } else hi--;
    }
    return best;
}

C++

int twoSumLessThanK(vector<int>& nums, int k) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int lo = 0, hi = (int) s.size() - 1, best = -1;
    while (lo < hi) {
        int sum = s[lo] + s[hi];
        if (sum < k) {
            best = max(best, sum);
            lo++;
        } else hi--;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms