Two Sum Less Than K - Leetcode Solution

Problem:

Given an array of integers nums and an integer target, return the sum of the two integers in nums such that they add up to target and their sum is less than or equal to target. If there is no answer, return -1.

Solution:

We can solve this problem using two-pointer approach.

1. Sort the array nums in non-decreasing order.
2. Initialize two pointers, left pointing to the beginning of the array and right pointing to the end of the array.
3. Initialize a variable max_sum with -1.
4. Iterate until left is less than right. a. Calculate the sum of nums[left] and nums[right]. b. If the sum is less than or equal to target, update max_sum as the maximum of max_sum and the sum. c. If the sum is greater than target, decrement right. d. If the sum is less than target, increment left.
5. Return max_sum which is the maximum possible sum less than or equal to target. If max_sum is still -1, it means there is no possible sum less than target.

Code:

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());     // Step 1
        int left = 0, right = n - 1, max_sum = -1;    // Step 2 and 3
        while (left < right) {   // Step 4
            int sum = nums[left] + nums[right];
            if (sum <= k) {
                max_sum = max(max_sum, sum);
                left++;
            } else {
                right--;
            }
        }
        return max_sum;     // Step 5
    }
};

Time Complexity: O(n log n) (because of sorting)
Space Complexity: O(1)

1