Easy

Two Sum Less Than K

LAB

Return the largest sum of two distinct numbers less than k, or -1 if no pair qualifies.

EXAMPLES

Example 1

Input
{
  "nums": [
    34,
    23,
    1,
    24,
    75,
    33,
    54,
    8
  ],
  "k": 60
}

Output
58

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

We want the largest pair sum that is still less than k (closest to k, from below).

If nums[i] + nums[j] >= k we are clearly too large, so decrement j. If nums[i] + nums[j] < k, we satisfy the condition, but we want to increment i to increase the sum and see if we can get even closer to k without exceeding. There is no point in decrementing j, because our current answer is at least as good.

Reveal reference solution +

pythonREFERENCE

def twoSumLessThanK(self, nums: List[int], k: int) -> int:
    nums.sort()
    n = len(nums)
    res = -1
    i, j = 0, n - 1

    while i < j:
        if nums[i] + nums[j] >= k:
            j -= 1
        else:
            res = max(res, nums[i] + nums[j])
            i += 1

    return res

TimeO(n log n)

SpaceO(1)

Open on LeetCode ↗