Problem Description

You are given an array of integers nums and an integer k. Your task is to find the maximum possible sum of two different elements from the array such that their sum is less than k.

The requirements are:

• You need to pick two elements at different indices i and j where i < j
• The sum nums[i] + nums[j] must be less than k
• Among all valid pairs, you want the maximum possible sum

If no such pair exists that satisfies these conditions, return -1.

For example:

• If nums = [34, 23, 1, 24, 75, 33, 54, 8] and k = 60, the maximum sum less than 60 would be 58 (formed by 24 + 34)
• If no two elements can sum to less than k, the answer would be -1

The solution uses sorting combined with binary search. After sorting the array, for each element nums[i], it uses binary search to find the largest possible nums[j] such that nums[i] + nums[j] < k. The binary search specifically looks for the position where k - nums[i] would be inserted, then takes the element just before that position to ensure the sum stays below k.

Intuition

The key insight is that once we sort the array, we can efficiently find the best pairing for each element. Think about it this way: for any element nums[i], we want to find the largest possible nums[j] that we can pair it with while keeping their sum below k.

Why sorting helps? In a sorted array, if we're looking for a partner for nums[i], we know that the maximum allowed value for its partner would be something less than k - nums[i]. Since the array is sorted, we can use binary search to quickly locate the largest element that is still less than k - nums[i].

The beauty of this approach is that bisect_left(nums, k - x, lo=i + 1) finds the insertion point for k - x in the sorted array starting from index i + 1. By subtracting 1 from this position, we get the index of the largest element that is smaller than k - x. This element, when added to x, gives us the largest sum that is still less than k.

For each element, we're essentially asking: "What's the biggest number I can add to this element without exceeding k?" The sorted order allows us to answer this question in O(log n) time using binary search, rather than checking every possible pair which would take O(n) time.

By iterating through each element and finding its best partner using this method, we ensure we don't miss the maximum possible sum. We keep track of the maximum sum found so far, and if no valid pair exists, we return -1.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution follows a sorting + binary search strategy to efficiently find the maximum sum less than k.

Step 1: Sort the array

nums.sort()

We first sort the array in ascending order. This enables us to use binary search and ensures that for any element, all potential partners greater than it are to its right.

Step 2: Initialize the answer

ans = -1

We start with -1 as our answer, which will be returned if no valid pair exists.

Step 3: Iterate through each element

for i, x in enumerate(nums):

We enumerate through each element x at index i in the sorted array. This element will be the first element of our potential pair.

Step 4: Binary search for the best partner

j = bisect_left(nums, k - x, lo=i + 1) - 1

For each element x, we need to find the largest element that, when added to x, gives a sum less than k.

• We search for k - x starting from index i + 1 (to ensure i < j)
• bisect_left returns the leftmost insertion position for k - x
• By subtracting 1, we get the index of the largest element less than k - x
• This element at index j is the best partner for x

Step 5: Update the maximum sum

if i < j:
    ans = max(ans, x + nums[j])

We verify that we found a valid index j (ensuring i < j), then update our answer with the maximum between the current answer and the new sum x + nums[j].

Step 6: Return the result

return ans

After checking all possible first elements, we return the maximum sum found, or -1 if no valid pair exists.

Time Complexity: O(n log n) where n is the length of the array - O(n log n) for sorting plus O(n log n) for n binary searches.

Space Complexity: O(1) if we don't count the space used by sorting (in-place sorting), otherwise O(n) for the sorting algorithm.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: nums = [10, 20, 30], k = 31

Step 1: Sort the array The array is already sorted: [10, 20, 30]

Step 2: Initialize answer ans = -1

Step 3-5: Iterate and search for best partners

Iteration 1: i = 0, x = 10

• We need to find the largest number that when added to 10 gives sum < 31
• Search for k - x = 31 - 10 = 21 starting from index i + 1 = 1
• bisect_left([20, 30], 21, lo=0) returns index 1 (where 21 would be inserted)
• j = 1 - 1 = 0 (relative to the search range), which maps to actual index 1 in the full array
• Check: i = 0 < j = 1 ✓
• Sum: 10 + nums[1] = 10 + 20 = 30 (which is < 31) ✓
• Update: ans = max(-1, 30) = 30

Iteration 2: i = 1, x = 20

• Search for k - x = 31 - 20 = 11 starting from index i + 1 = 2
• bisect_left([30], 11, lo=0) returns index 0 (11 would go before 30)
• j = 0 - 1 = -1 (relative), which maps to actual index 1 in the full array
• Check: i = 1 < j = 1 ✗ (not valid)
• No update to answer

Iteration 3: i = 2, x = 30

• Search for k - x = 31 - 30 = 1 starting from index i + 1 = 3
• Since we're searching beyond the array bounds, no valid partner exists
• No update to answer

Step 6: Return result Return ans = 30

The maximum sum less than 31 is 30 (formed by 10 + 20).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity consists of two main operations:

1. Sorting the array: nums.sort() takes O(n × log n) time
2. Iterating through the array with binary search: The for loop runs n times, and each iteration performs a bisect_left operation which takes O(log n) time, resulting in O(n × log n) time

Since both operations are O(n × log n), the overall time complexity is O(n × log n), where n is the length of the array nums.

Space Complexity: O(log n)

The space complexity comes from:

1. The sorting algorithm: Python's Timsort (used in sort()) requires O(log n) space for its recursion stack
2. The binary search (bisect_left): Uses O(log n) space for its recursion stack (or O(1) if implemented iteratively, but Python's implementation uses recursion)
3. A few constant space variables (ans, i, x, j): O(1) space

The dominant factor is the O(log n) space from sorting, making the overall space complexity O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Binary Search

One of the most common mistakes is misunderstanding what bisect_left returns and incorrectly calculating the partner index.

The Pitfall:

# Incorrect: forgetting to subtract 1
j = bisect_left(nums, k - x, lo=i + 1)  # Wrong!
if i < j:
    ans = max(ans, x + nums[j])  # This might access an invalid element

bisect_left returns the insertion position where k - x would go to maintain sorted order. If k - x doesn't exist in the array, this position points to the first element greater than or equal to k - x. We need the element just before this position.

The Solution:

# Correct: subtract 1 to get the largest element less than k - x
j = bisect_left(nums, k - x, lo=i + 1) - 1
if i < j:
    ans = max(ans, x + nums[j])

2. Array Index Out of Bounds

When bisect_left returns i + 1 (meaning no element >= k - x exists after index i), subtracting 1 gives us j = i, which violates our i < j requirement.

The Pitfall:

# Potentially problematic if not checking i < j
j = bisect_left(nums, k - x, lo=i + 1) - 1
ans = max(ans, x + nums[j])  # Could access nums[i] when j = i

The Solution: Always verify i < j before using the indices:

j = bisect_left(nums, k - x, lo=i + 1) - 1
if i < j:  # This check prevents using the same element twice
    ans = max(ans, x + nums[j])

3. Using the Same Element Twice

Without proper bounds in binary search, we might accidentally pair an element with itself.

The Pitfall:

# Wrong: starting binary search from index i instead of i + 1
j = bisect_left(nums, k - x, lo=i) - 1  # Could return j = i

The Solution: Always start the binary search from i + 1:

# Correct: ensures j > i
j = bisect_left(nums, k - x, lo=i + 1) - 1

4. Forgetting to Handle Edge Cases

Not considering when no valid pair exists or when the array has fewer than 2 elements.

The Pitfall:

def twoSumLessThanK(self, nums: List[int], k: int) -> int:
    nums.sort()
    # Missing check for array length
    for i, x in enumerate(nums):
        # ... rest of the code

The Solution: Either add an explicit check or rely on the loop naturally handling it:

def twoSumLessThanK(self, nums: List[int], k: int) -> int:
    if len(nums) < 2:
        return -1
    nums.sort()
    ans = -1
    # ... rest of the code

Or let the algorithm handle it naturally (the current solution does this - if there's only one element, the loop runs once but i < j will never be true).