Two Sum Less Than K Problem in Javascript

Given an array of integers A and an integer K, your task is to find the maximum sum of two distinct numbers in the array that is less than K.

If no such pair exists, return -1.

Examples

// Example 1:
Input: A = [34, 23, 24, 33, 12], K = 60
Output: 58 // Because the pair (34, 24) is the largest pair whose sum is less than 60

// Example 2:
Input: A = [10, 20, 30], K = 15
Output: -1 // No pairs found that meet the criteria

Solution

There can be two approaches to solve this problem:

1. Brute Force Approach
2. Two Pointers Approach

Approach 1: Brute Force

This brute force method checks every possible pair of numbers in the array to see if their sum is less than K and maintains the maximum of those sums. The time complexity is O(n²), and the space complexity is O(1).

const twoSumLessThanK_BruteForce = function(A, K) {
    let max = -1;
    for (let i = 0; i < A.length; i++) {
        for (let j = i + 1; j < A.length; j++) {
            const sum = A[i] + A[j];
            if (sum < K) {
                max = Math.max(max, sum);
            }
        }
    }
    return max;
};

Approach 2: Two Pointers

This approach sorts the array first, then uses two pointers to find pairs that sum up to a value less than K. It maintains the maximum of those sums. The time complexity is O(n log n) due to sorting, and the space complexity is O(1).

const twoSumLessThanK = function(A, K) {
    A.sort((a, b) => a - b);
    
    let max = -1,
        i = 0,
        j = A.length - 1;
    
    while (i < j) {
        const sum = A[i] + A[j];
        
        if (sum < K) {
            max = Math.max(max, sum); // found another answer pair
            i++;
        } else {
            j--; // pick smaller number
        }
    }
    
    return max;
};