We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Two Sum Less Than K

Number: 1083

Difficulty: Easy

Paid? Yes

Companies: Amazon

Problem Description

Given an array of integers nums and an integer k, return the maximum sum of any two distinct numbers in nums such that their sum is less than k. If no valid pair exists, return -1.

Key Insights

  • Sorting the array simplifies pair selection by ordering the values.
  • A two-pointer approach can efficiently explore potential pairs.
  • Adjust the two pointers based on whether the current pair sum is less than k.
  • Ensure that the best candidate is continuously updated with valid sums.

Space and Time Complexity

Time Complexity: O(n log n) due to the sort operation, and O(n) for the two-pointer scan, resulting in an overall O(n log n). Space Complexity: O(1) if sorting in-place; otherwise, O(n) if a separate sorted copy is used.

Solution

The solution sorts the array and then employs a two-pointer technique. Start with one pointer at the beginning and one at the end of the array. At each step:

  • Calculate the sum of the values at the two pointers.
  • If the sum is less than k, update the maximum sum and move the left pointer rightwards to try for a larger sum.
  • If the sum is greater than or equal to k, move the right pointer leftwards to reduce the sum. Continue until the pointers meet, and finally return the best valid sum found, or -1 if no valid pair exists.

Code Solutions

# Python solution
def two_sum_less_than_k(nums, k):
    # Sort the array to facilitate two-pointer scanning
    nums.sort()  # O(n log n)
    left = 0
    right = len(nums) - 1
    max_sum = -1  # Initialize with -1 to indicate no valid pair has been found
    
    # Use two pointers to explore pairs
    while left < right:
        current_sum = nums[left] + nums[right]
        # Check if the current sum meets the condition
        if current_sum < k:
            max_sum = max(max_sum, current_sum)  # Update maximum sum if current is valid
            left += 1  # Move left pointer to get a possibly larger sum
        else:
            right -= 1  # Move right pointer to get a smaller sum
    return max_sum

# Example usage:
# print(two_sum_less_than_k([34,23,1,24,75,33,54,8], 60))  # Output: 58
← Back to All Questions