Domain 1EasyCORE

Two Sum Less Than K

The problem requires finding two numbers in an array such that their sum is less than a given integer `k` and is as large as possible. The inputs are an array of integers `nums` and an integer `k`. The output should be the maximum sum of any two distinct elements in `nums` that is less than `k`. If no such pair exists, return `-1`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Two Pointers#Sort

1099. Two Sum Less Than K

Model: qwen2.5-coder:14b
Topics: Array,Two Pointers,Sort
FAANG asked: 1
Acceptance rate: 60.8%


Problem Breakdown

The problem requires finding two numbers in an array such that their sum is less than a given integer k and is as large as possible. The inputs are an array of integers nums and an integer k. The output should be the maximum sum of any two distinct elements in nums that is less than k. If no such pair exists, return -1.

Inputs:

  • An array of integers nums.
  • An integer k.

Outputs:

  • An integer representing the maximum sum of two numbers in nums that is less than k, or -1 if no such pair exists.

Implicit Constraints/Edge Cases:

  • The array can be empty, in which case the output should be -1.
  • All elements in nums are positive integers.
  • The value of k is also a positive integer.
  • There might be duplicate numbers in the array.

Intuition

A brute-force approach would involve checking all possible pairs (i, j) where i < j and calculating their sums. If the sum is less than k, we compare it with the current maximum sum found and update if necessary. This approach has a time complexity of (O(n^2)), which is inefficient for larger arrays.

To improve this, we can sort the array first. After sorting, we can use two pointers: one starting at the beginning (left) and the other at the end (right). We then move these pointers towards each other based on whether the sum of the elements at these pointers is less than or greater than k. This approach leverages the sorted order to reduce unnecessary checks, leading to a more efficient solution.

Approach

  1. Sort the Array: Begin by sorting the array nums in ascending order.
  2. Initialize Pointers and Variables:
    • Set left pointer at the start of the array (0).
    • Set right pointer at the end of the array (len(nums) - 1).
    • Initialize a variable max_sum to -1 to keep track of the maximum sum found that is less than k.
  3. Two-Pointer Technique:
    • While left < right:
      • Calculate the sum of the elements at the left and right pointers.
      • If the sum is less than k, update max_sum if this sum is greater than the current max_sum.
      • Move the left pointer to the right (left += 1) to try and find a larger sum.
      • If the sum is greater than or equal to k, move the right pointer to the left (right -= 1) to reduce the sum.
  4. Return Result: After the loop, return max_sum.

Complexity Analysis

  • Time Complexity: (O(n \log n)) due to the sorting step. The two-pointer traversal is (O(n)).
  • Space Complexity: (O(1)) as we are using a constant amount of extra space.

Solution

def twoSumLessThanK(nums, k):
    nums.sort()
    left, right = 0, len(nums) - 1
    max_sum = -1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum < k:
            max_sum = max(max_sum, current_sum)
            left += 1
        else:
            right -= 1
    
    return max_sum

Edge Cases Handled

  • Empty Array: The function returns -1 as there are no elements to form a pair.
  • All Elements Greater Than or Equal to k: The function will eventually reduce the window size until no valid pairs remain, returning -1.
  • Single Element Array: Similar to the empty array case, it returns -1.
  • Duplicates: The algorithm correctly handles duplicates by checking all possible pairs within the sorted array.