LeetCode 1099 - Two Sum Less Than K

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

This problem asks us to find the maximum sum of any two distinct numbers in an integer array nums such that their sum is strictly less than a given integer k. In other words, we are looking for two indices i and j with i < j where nums[i] + nums[j] is less than k, and among all such valid pairs, the sum is the largest possible. If no pair exists that satisfies this condition, we should return -1.

The input array nums contains integers between 1 and 1000, and its length is between 1 and 100. The integer k is guaranteed to be between 1 and 2000. These constraints tell us that the input size is small, so algorithms with time complexity up to O(n^2) could work, but we can optimize further.

Important edge cases include arrays where all sums are greater than or equal to k, arrays with only one element, or arrays where multiple pairs sum to the same maximum valid value. The problem guarantees that numbers are positive integers, so we do not need to handle negative numbers or zero explicitly.

Approaches

The brute-force approach involves checking all possible pairs (i, j) in the array and computing their sums. For each pair, we check if the sum is less than k and track the maximum sum found. This approach is correct because it evaluates every pair, but it has time complexity O(n^2), which can be slow for larger arrays, though still feasible given the constraints.

The optimal approach uses sorting and the two-pointer technique. By first sorting the array, we can efficiently search for pairs using two pointers, one starting at the beginning (left) and one at the end (right). If the sum of nums[left] + nums[right] is less than k, we update the maximum sum and move left to the right to try a larger sum. If the sum is greater than or equal to k, we move right to the left to reduce the sum. This approach works because the array is sorted, so increasing left increases the sum and decreasing right decreases it, allowing us to explore all possible valid sums efficiently without checking every pair.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check all pairs, simple but quadratic
Optimal (Two Pointers)	O(n log n)	O(1)	Sort + two pointers to find maximum sum less than k

Algorithm Walkthrough

Sort the array nums in ascending order. This allows us to efficiently use two pointers to explore sums.
Initialize two pointers: left at 0 (start of the array) and right at len(nums) - 1 (end of the array). Also initialize max_sum to -1.
Enter a loop that runs while left < right.
Compute the sum current_sum = nums[left] + nums[right].
If current_sum < k, update max_sum to the maximum of max_sum and current_sum. Move left one step to the right to try a larger sum.
If current_sum >= k, move right one step to the left to reduce the sum.
Continue until left is no longer less than right.
Return max_sum, which will be -1 if no valid sum was found.

Why it works: The sorted array ensures that moving the left pointer increases the sum and moving the right pointer decreases it. This property guarantees that all potential sums less than k are explored efficiently, and the largest sum satisfying the condition is captured.

Python Solution

from typing import List

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        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

The implementation first sorts the array. The two-pointer loop efficiently explores sums from the smallest and largest numbers inward. If a sum is valid, max_sum is updated. If the sum exceeds k, the right pointer moves left to reduce the sum. The result is returned after all possible pairs are considered.

Go Solution

import "sort"

func twoSumLessThanK(nums []int, k int) int {
    sort.Ints(nums)
    left, right := 0, len(nums) - 1
    maxSum := -1
    
    for left < right {
        currentSum := nums[left] + nums[right]
        if currentSum < k {
            if currentSum > maxSum {
                maxSum = currentSum
            }
            left++
        } else {
            right--
        }
    }
    
    return maxSum
}

The Go implementation mirrors the Python solution. sort.Ints sorts the array, and the two-pointer approach is implemented with a for loop. Edge cases are naturally handled since maxSum starts at -1 and only valid sums update it.

Worked Examples

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

Sorted array: [1, 8, 23, 24, 33, 34, 54, 75]

Pointers: left = 0, right = 7

left	right	nums[left]	nums[right]	sum	max_sum
0	7	1	75	76	-1
0	6	1	54	55	55
1	6	8	54	62	55
1	5	8	34	42	55
2	5	23	34	57	57
3	5	24	34	58	58
4	5	33	34	67	58

Return 58.

Example 2: nums = [10,20,30], k = 15

Sorted array: [10,20,30]

Pointers: left = 0, right = 2

left	right	nums[left]	nums[right]	sum	max_sum
0	2	10	30	40	-1
0	1	10	20	30	-1

Return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), two-pointer traversal takes O(n), overall O(n log n)
Space	O(1)	Only a few variables used, no extra data structures needed beyond sorting

The complexity is efficient given the constraints. Sorting dominates the time complexity, and the two-pointer pass is linear, scanning each pair only once.

Test Cases

# Provided examples
assert Solution().twoSumLessThanK([34,23,1,24,75,33,54,8], 60) == 58  # normal case
assert Solution().twoSumLessThanK([10,20,30], 15) == -1  # no valid pair

# Boundary and stress cases
assert Solution().twoSumLessThanK([1], 2) == -1  # only one element
assert Solution().twoSumLessThanK([1,1], 3) == 2  # smallest possible sum < k
assert Solution().twoSumLessThanK([1000,1000], 2001) == 2000  # large numbers
assert Solution().twoSumLessThanK([5,5,5,5], 10) == 9  # multiple pairs same value
assert Solution().twoSumLessThanK(list(range(1, 101)), 50) == 49  # large array

Test	Why
[34,23,1,24,75,33,54,8], 60	Normal case, multiple pairs
[10,20,30], 15	No valid pair exists
[1], 2	Single-element array, cannot form a pair
[1,1], 3	Minimum valid sum scenario
[1000,1000], 2001	Large numbers at the upper limit
[5,5,5,5], 10	Multiple identical numbers forming pairs
range(1,101), 50	Large array to test efficiency

Edge Cases

Single-element array: With only one number, no pair exists. The implementation correctly returns -1 because the loop condition left < right never executes.

All sums greater than k: If every possible sum is greater than or equal

left	right	nums[left]	nums[right]	sum	max_sum
0	7	1	75	76	-1
0	6	1	54	55	55
1	6	8	54	62	55
1	5	8	34	42	55
2	5	23	34	57	57
3	5	24	34	58	58
4	5	33	34	67	58

left	right	nums[left]	nums[right]	sum	max_sum
0	7	1	75	76	-1
0	6	1	54	55	55
1	6	8	54	62	55
1	5	8	34	42	55
2	5	23	34	57	57
3	5	24	34	58	58
4	5	33	34	67	58

left	right	nums[left]	nums[right]	sum	max_sum
0	7	1	75	76	-1
0	6	1	54	55	55
1	6	8	54	62	55
1	5	8	34	42	55
2	5	23	34	57	57
3	5	24	34	58	58
4	5	33	34	67	58