Two Sum Less Than K

Problem Statement

In this problem, we are tasked with finding the maximum possible sum of two distinct elements from a given array of integers, such that this sum is less than a provided threshold k. Specifically, we need to identify two indices i and j (with i < j) where the sum of nums[i] and nums[j] is the highest possible under the constraint that it must be less than k. If no such pair exists that conforms to these rules, the function should return -1.

Examples

Example 1

Input:

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

Output:

58

Explanation:

We can use 34 and 24 to sum 58 which is less than 60.

Example 2

Input:

nums = [10,20,30], k = 15

Output:

-1

Explanation:

In this case it is not possible to get a pair sum less that 15.

Constraints

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 1000
• 1 <= k <= 2000

Approach and Intuition

To solve this problem, our goal is to maximize the sum of two numbers from the array while ensuring that their sum is less than the given limit k. Here's a systematic way to approach this:

1. Start by sorting the array nums. Sorting helps in efficiently finding pairs that satisfy the given condition by using a two-pointer technique.
2. Initialize two pointers, one (left) at the beginning of the array and the other (right) at the last element.
3. Use a variable max_sum to keep track of the maximum sum encountered that is also less than k.
4. Iterate over the array using the two pointers:
   • Calculate the sum of elements at the left and right pointers.
   • If this sum is less than k, compare it with max_sum and update max_sum if this sum is greater.
   • If the sum is less than k, increase the left pointer to try and get a larger sum.
   • If the sum is equal to or greater than k, decrease the right pointer to reduce the sum.
5. Continue this process until the left pointer is not less than the right pointer.
6. After completing the loop, check the value of max_sum. If it has changed from its initial value (suggesting a valid sum was found), return it. Otherwise, return -1, indicating no valid pair was found.

By following this method, we efficiently search for the highest pair sum under the given constraints without needing to check all possible pairs, thus optimizing the process.

Solutions

class Solution {
public:
    int pairSumLessThanK(vector<int>& arr, int limit) {
        int bestSum = -1;
        int frequency[1001] = {};
        for (int v : arr) {
            frequency[v]++;
        }
        int left = 1;
        int right = 1000;
        while (left <= right) {
            if (left + right >= limit || frequency[right] == 0) {
                right--;
            } else {
                if (frequency[left] > (left < right ? 0 : 1)) {
                    bestSum = max(bestSum, left + right);
                }
                left++;
            }
        }
        return bestSum;
    }
};