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
numsthat is less thank, or-1if no such pair exists.
Implicit Constraints/Edge Cases:
- The array can be empty, in which case the output should be
-1. - All elements in
numsare positive integers. - The value of
kis 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
- Sort the Array: Begin by sorting the array
numsin ascending order. - Initialize Pointers and Variables:
- Set
leftpointer at the start of the array (0). - Set
rightpointer at the end of the array (len(nums) - 1). - Initialize a variable
max_sumto-1to keep track of the maximum sum found that is less thank.
- Set
- Two-Pointer Technique:
- While
left < right:- Calculate the sum of the elements at the
leftandrightpointers. - If the sum is less than
k, updatemax_sumif this sum is greater than the currentmax_sum. - Move the
leftpointer to the right (left += 1) to try and find a larger sum. - If the sum is greater than or equal to
k, move therightpointer to the left (right -= 1) to reduce the sum.
- Calculate the sum of the elements at the
- While
- 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
-1as 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.