1099. Two Sum Less Than K

EasyArrayTwo PointersBinary SearchSorting

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 Implementation

1from typing import List
2
3
4class Solution:
5    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
6        # Sort the array to enable binary search
7        nums.sort()
8
9        # Initialize the maximum sum to -1 (default return value if no valid pair exists)
10        max_sum = -1
11        n = len(nums)
12
13        # Iterate through each number as the first element of the pair
14        for i, first_num in enumerate(nums):
15            # Find the largest possible second number such that first_num + second_num < k
16            # We need nums[j] < k - first_num
17            target = k - first_num
18
19            # Binary search to find first index where nums[mid] >= target
20            # Feasible condition: nums[mid] >= target
21            # Pattern: [false, false, ..., true, true, true]
22            left, right = i + 1, n - 1
23            first_true_index = -1
24
25            while left <= right:
26                mid = (left + right) // 2
27                if nums[mid] >= target:
28                    first_true_index = mid
29                    right = mid - 1
30                else:
31                    left = mid + 1
32
33            # The largest valid index is one before first_true_index (or n-1 if not found)
34            if first_true_index == -1:
35                j = n - 1  # All elements < target, use last element
36            else:
37                j = first_true_index - 1  # Use element just before the boundary
38
39            # Check if we found a valid second element
40            if i < j:
41                # Update the maximum sum if current pair has a larger sum
42                current_sum = first_num + nums[j]
43                max_sum = max(max_sum, current_sum)
44
45        return max_sum
46

1class Solution {
2    /**
3     * Find the maximum sum of two elements in the array that is less than k.
4     * @param nums the input array
5     * @param k the upper bound (exclusive)
6     * @return the maximum sum less than k, or -1 if no such sum exists
7     */
8    public int twoSumLessThanK(int[] nums, int k) {
9        // Sort the array to enable binary search
10        Arrays.sort(nums);
11
12        int maxSum = -1;
13        int n = nums.length;
14
15        // Iterate through each element as the first number
16        for (int i = 0; i < n; ++i) {
17            // Find the largest number that when added to nums[i] is less than k
18            // We need nums[j] < k - nums[i]
19            int target = k - nums[i];
20
21            // Binary search to find first index where nums[mid] >= target
22            // Feasible condition: nums[mid] >= target
23            int left = i + 1;
24            int right = n - 1;
25            int firstTrueIndex = -1;
26
27            while (left <= right) {
28                int mid = left + (right - left) / 2;
29                if (nums[mid] >= target) {
30                    firstTrueIndex = mid;
31                    right = mid - 1;
32                } else {
33                    left = mid + 1;
34                }
35            }
36
37            // The largest valid index is one before firstTrueIndex (or n-1 if not found)
38            int j;
39            if (firstTrueIndex == -1) {
40                j = n - 1;  // All elements < target, use last element
41            } else {
42                j = firstTrueIndex - 1;  // Use element just before the boundary
43            }
44
45            // Check if we found a valid pair
46            if (i < j) {
47                int currentSum = nums[i] + nums[j];
48                maxSum = Math.max(maxSum, currentSum);
49            }
50        }
51
52        return maxSum;
53    }
54}
55

1class Solution {
2public:
3    int twoSumLessThanK(vector<int>& nums, int k) {
4        // Sort the array to enable binary search
5        sort(nums.begin(), nums.end());
6
7        // Initialize result as -1 (no valid pair found) and get array size
8        int maxSum = -1;
9        int n = nums.size();
10
11        // Iterate through each element as the first number in the pair
12        for (int i = 0; i < n; ++i) {
13            // Find the largest index j where nums[j] < k - nums[i]
14            // We need nums[j] < k - nums[i]
15            int target = k - nums[i];
16
17            // Binary search to find first index where nums[mid] >= target
18            // Feasible condition: nums[mid] >= target
19            int left = i + 1;
20            int right = n - 1;
21            int firstTrueIndex = -1;
22
23            while (left <= right) {
24                int mid = left + (right - left) / 2;
25                if (nums[mid] >= target) {
26                    firstTrueIndex = mid;
27                    right = mid - 1;
28                } else {
29                    left = mid + 1;
30                }
31            }
32
33            // The largest valid index is one before firstTrueIndex (or n-1 if not found)
34            int j;
35            if (firstTrueIndex == -1) {
36                j = n - 1;  // All elements < target, use last element
37            } else {
38                j = firstTrueIndex - 1;  // Use element just before the boundary
39            }
40
41            // Check if we found a valid pair (j must be greater than i)
42            if (i < j) {
43                // Update the maximum sum if current pair sum is larger
44                int currentSum = nums[i] + nums[j];
45                maxSum = max(maxSum, currentSum);
46            }
47        }
48
49        return maxSum;
50    }
51};
52

1/**
2 * Finds the maximum sum of two different elements in the array that is less than k.
3 * Uses binary search to find the best partner for each element.
4 *
5 * @param nums - Array of integers to search through
6 * @param k - Upper bound (exclusive) for the sum
7 * @returns Maximum sum less than k, or -1 if no valid pair exists
8 */
9function twoSumLessThanK(nums: number[], k: number): number {
10    // Sort the array in ascending order to enable binary search
11    nums.sort((a, b) => a - b);
12
13    // Initialize result as -1 (default when no valid pair is found)
14    let maxSum = -1;
15    const n = nums.length;
16
17    // Iterate through each element as the first number
18    for (let i = 0; i < n; i++) {
19        const firstNum = nums[i];
20        // We need nums[j] < k - firstNum
21        const target = k - firstNum;
22
23        // Binary search to find first index where nums[mid] >= target
24        // Feasible condition: nums[mid] >= target
25        let left = i + 1;
26        let right = n - 1;
27        let firstTrueIndex = -1;
28
29        while (left <= right) {
30            const mid = Math.floor((left + right) / 2);
31            if (nums[mid] >= target) {
32                firstTrueIndex = mid;
33                right = mid - 1;
34            } else {
35                left = mid + 1;
36            }
37        }
38
39        // The largest valid index is one before firstTrueIndex (or n-1 if not found)
40        let j: number;
41        if (firstTrueIndex === -1) {
42            j = n - 1;  // All elements < target, use last element
43        } else {
44            j = firstTrueIndex - 1;  // Use element just before the boundary
45        }
46
47        // Check if we found a valid pair
48        if (i < j) {
49            const currentSum = firstNum + nums[j];
50            maxSum = Math.max(maxSum, currentSum);
51        }
52    }
53
54    return maxSum;
55}
56

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

max_sum = -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, first_num in enumerate(nums):

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

Step 4: Binary Search Using Template

For each element first_num, we need to find the largest element that, when added to it, gives a sum less than k. We need nums[j] < k - first_num.

Feasible condition: nums[mid] >= target where target = k - first_num

Pattern: [false, false, ..., true, true, true]

left, right = i + 1, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

Step 5: Calculate the best partner index

If first_true_index == -1: All elements after i are < target, so use the last element
Otherwise: The largest valid element is at first_true_index - 1 (just before the boundary)

Step 6: Update the maximum sum

if i < j:
    max_sum = max(max_sum, first_num + nums[j])

We verify that we found a valid index j (ensuring i < j), then update our answer.

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.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

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).

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity consists of two main operations:

Sorting the array: nums.sort() takes O(n × log n) time
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:

The sorting algorithm: Python's Timsort (used in sort()) requires O(log n) space for its recursion stack
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)
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. Using the Wrong Binary Search Template

A common mistake is using while left < right with right = mid instead of the standard template:

# Alternative template (not recommended)
while left < right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        right = mid
    else:
        left = mid + 1
j = left - 1

Solution: Use the standard template with while left <= right and first_true_index:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
# j is first_true_index - 1, or n - 1 if first_true_index == -1

2. Not Handling the "All Elements Valid" Case

When all elements in the search range are < target, first_true_index remains -1:

# WRONG
j = first_true_index - 1  # When first_true_index is -1, j becomes -2!

Solution: Handle this case explicitly:

if first_true_index == -1:
    j = n - 1  # All elements < target, use last element
else:
    j = first_true_index - 1

3. Using the Same Element Twice

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

# WRONG: starting binary search from index i instead of i + 1
left = i  # Could find j = i

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

left = i + 1  # Ensures j > i

4. Off-by-One When Computing Partner Index

The binary search finds the first index where nums[mid] >= target, but we need the largest index where nums[j] < target:

# WRONG: Using first_true_index directly
j = first_true_index  # This gives nums[j] >= target, not < target

Solution: Use first_true_index - 1 to get the element just before the boundary.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know