Solution Explanation for LeetCode 1099: Two Sum Less Than K

This problem asks to find the maximum sum of two numbers in an array nums such that the sum is less than a given integer k.

Approach 1: Sorting + Binary Search

This approach leverages sorting for efficient searching.

1. Sort the array: Sorting nums allows us to use binary search efficiently in the next step. The time complexity of sorting is O(n log n), where n is the length of nums.

2. Iterate and Binary Search: We iterate through each number nums[i] in the sorted array. For each number, we want to find the largest number nums[j] (where j > i) such that nums[i] + nums[j] < k. We can efficiently find this nums[j] using binary search on the remaining portion of the sorted array (nums[i+1:]). The binary search takes O(log n) time.

3. Update Maximum Sum: If a suitable nums[j] is found (meaning nums[i] + nums[j] < k), update the maximum sum found so far.

4. Return Result: After iterating through all numbers, the maximum sum (or -1 if no such pair exists) is returned.

Time Complexity: O(n log n) due to sorting. The binary search within the loop contributes O(n log n) overall. Space Complexity: O(log n) or O(1) depending on the sorting algorithm used (some in-place sorting algorithms have O(1) space complexity, while merge sort or quicksort usually require O(log n) space for recursion).

Approach 2: Sorting + Two Pointers

This approach uses two pointers to iterate through the sorted array efficiently.

1. Sort the array: Same as in Approach 1, we start by sorting nums in O(n log n) time.

2. Two Pointers: Initialize two pointers, i pointing to the beginning (index 0) and j pointing to the end (index n-1) of the sorted array.

3. Iterate and Check Sum: Calculate the sum s = nums[i] + nums[j].

   • If s < k, we've found a pair whose sum is less than k. Update the maximum sum if necessary and increment i to consider larger numbers at the left.
   • If s >= k, the sum is too large. Decrement j to consider smaller numbers at the right.

4. Return Result: The loop continues until the pointers cross (i >= j), at which point the maximum sum (or -1) is returned.

Time Complexity: O(n log n) dominated by the sorting step. The two-pointer iteration is O(n). Space Complexity: O(log n) or O(1) depending on the sorting algorithm (similar to Approach 1).

Code Examples (Python - Approach 2 is shown for brevity and efficiency):

def twoSumLessThanK(nums, k):
    nums.sort()
    i, j = 0, len(nums) - 1
    max_sum = -1
    while i < j:
        current_sum = nums[i] + nums[j]
        if current_sum < k:
            max_sum = max(max_sum, current_sum)
            i += 1  # Move left pointer to increase the sum
        else:
            j -= 1  # Move right pointer to decrease the sum
    return max_sum
 

The other languages (Java, C++, Go, TypeScript) would have similar implementations, primarily differing in syntax and specific library functions used for sorting and max operations. The core logic of the two-pointer approach remains consistent.