LeetCode 1099: Two Sum Less Than K

Problem Restatement

We are given an integer array nums and an integer k.

We need to find the maximum sum nums[i] + nums[j] where i < j and nums[i] + nums[j] < k.

Return -1 if no such pair exists.

The official constraints state that 1 <= nums.length <= 100 and 1 <= nums[i] <= 1000.

Input and Output

Function shape:

def twoSumLessThanK(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

nums = [34, 23, 1, 24, 75, 33, 54, 8]
k = 60

Best pair: (33, 24) with sum 57 < 60.

Answer:

57

Key Insight

Sort the array. Use two pointers at both ends.

If the sum is less than k, update the answer and move the left pointer right (to try a larger sum).

If the sum is ≥ k, move the right pointer left (to decrease the sum).

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

class Solution:
    def twoSumLessThanK(self, nums: list[int], k: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        result = -1

        while left < right:
            s = nums[left] + nums[right]
            if s < k:
                result = max(result, s)
                left += 1
            else:
                right -= 1

        return result

Testing

def run_tests():
    s = Solution()

    assert s.twoSumLessThanK([34,23,1,24,75,33,54,8], 60) == 57
    assert s.twoSumLessThanK([10,20,30], 15) == -1
    assert s.twoSumLessThanK([254,914,110,900,147,441,209,122,571,942,136,350,160,127,178,839], 200) == 176

    print("all tests passed")

run_tests()