Code Implementation

class Solution:
    def twoSumLessThanK(self, nums, k):
        nums.sort()
        left, right = 0, len(nums) - 1
        max_sum = -1
        while left < right:
            curr_sum = nums[left] + nums[right]
            if curr_sum < k:
                max_sum = max(max_sum, curr_sum)
                left += 1
            else:
                right -= 1
        return max_sum
      

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        int max_sum = -1;
        while (left < right) {
            int curr_sum = nums[left] + nums[right];
            if (curr_sum < k) {
                max_sum = max(max_sum, curr_sum);
                left++;
            } else {
                right--;
            }
        }
        return max_sum;
    }
};
      

import java.util.Arrays;

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        int maxSum = -1;
        while (left < right) {
            int currSum = nums[left] + nums[right];
            if (currSum < k) {
                maxSum = Math.max(maxSum, currSum);
                left++;
            } else {
                right--;
            }
        }
        return maxSum;
    }
}
      

var twoSumLessThanK = function(nums, k) {
    nums.sort((a, b) => a - b);
    let left = 0, right = nums.length - 1;
    let maxSum = -1;
    while (left < right) {
        let currSum = nums[left] + nums[right];
        if (currSum < k) {
            maxSum = Math.max(maxSum, currSum);
            left++;
        } else {
            right--;
        }
    }
    return maxSum;
};
      

Problem Description

Given an array of integers nums and an integer k, your task is to find the maximum sum of any two distinct elements in nums such that the sum is less than k. If no such pair exists, return -1.

• Each number in nums can be used at most once in the sum (no element can pair with itself).
• The input does not guarantee that a valid pair exists.
• Return the largest possible sum that is strictly less than k, or -1 if none exists.

Thought Process

When first approaching this problem, a simple way to think about it is to try every possible pair of numbers and check if their sum is less than k. For each valid pair, we keep track of the largest sum found so far. This brute-force approach works, but it becomes slow as the array grows larger.

To optimize, we notice that sorting the array allows us to use a two-pointer technique. By sorting, we can efficiently find pairs with sums close to but less than k without checking every possible pair. This reduces unnecessary checks and speeds up the solution.

The key insight is: after sorting, if the sum of the smallest and largest is too big, we can decrease the largest; if it's small enough, we can try increasing the smallest to get closer to k.

Solution Approach

• Step 1: Sort the Array
  • Sorting helps us easily find pairs with sums less than k using two pointers.
• Step 2: Initialize Two Pointers
  • Set left at the start (smallest number) and right at the end (largest number).
• Step 3: Traverse with Two Pointers
  • While left < right:
    • Calculate curr_sum = nums[left] + nums[right].
    • If curr_sum < k: update max_sum if this sum is larger, and move left right to try a bigger sum.
    • If curr_sum ≥ k: move right left to try a smaller sum.
• Step 4: Return Result
  • If a valid pair was found, return the largest sum found; otherwise, return -1.

This approach is efficient because sorting is O(n log n) and the two-pointer scan is O(n).

Example Walkthrough

Let's use nums = [34, 23, 1, 24, 75, 33, 54] and k = 60.

1. Sort nums: [1, 23, 24, 33, 34, 54, 75]
2. Start with left = 0 (1), right = 6 (75).
3. 1 + 75 = 76 (too big), move right to 5.
4. 1 + 54 = 55 (< 60), update max_sum = 55, move left to 1.
5. 23 + 54 = 77 (too big), move right to 4.
6. 23 + 34 = 57 (< 60), update max_sum = 57, move left to 2.
7. 24 + 34 = 58 (< 60), update max_sum = 58, move left to 3.
8. 33 + 34 = 67 (too big), move right to 3.
9. Loop ends (left is not less than right).

The largest sum less than 60 is 58.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n^2) (check every pair)
  • Space Complexity: O(1) (no extra space needed)
• Optimized two-pointer approach:
  • Time Complexity: O(n log n) (due to sorting; two-pointer scan is O(n))
  • Space Complexity: O(1) (if sorting in place)

The optimized approach is much faster for larger arrays because it avoids checking every possible pair.

Summary

The Two Sum Less Than K problem is a great example of how sorting and the two-pointer technique can turn a slow brute-force solution into an efficient one. By sorting the array, we can quickly zoom in on the best possible pair using two pointers, only checking pairs that might yield a better result. This approach is both simple and elegant, making the solution efficient even for large inputs.