1099. Two Sum Less Than K 🔒

Description

Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.

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

Solutions

Solution 1: Sorting + Binary Search

Thinking

The largest pair sum strictly below \(k\) is quadratic if every pair is tested. After sorting, each \(x\) needs the largest right value below \(k-x\), which is a binary search.

For index \(i\), bisect_left on \((i,n)\) finds \(k-x\); the previous index, if still greater than \(i\), updates the answer.

The answer stays \(-1\) when no pair qualifies.

We can first sort the array \(nums\), and initialize the answer as \(-1\).

Next, we enumerate each element \(nums[i]\) in the array, and find the maximum \(nums[j]\) in the array that satisfies \(nums[j] + nums[i] < k\). Here, we can use binary search to speed up the search process. If we find such a \(nums[j]\), then we can update the answer, i.e., \(ans = \max(ans, nums[i] + nums[j])\).

After the enumeration ends, return the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++GoTypeScript

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = -1
        for i, x in enumerate(nums):
            j = bisect_left(nums, k - x, lo=i + 1) - 1
            if i < j:
                ans = max(ans, x + nums[j])
        return ans

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = -1;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int j = search(nums, k - nums[i], i + 1, n) - 1;
            if (i < j) {
                ans = Math.max(ans, nums[i] + nums[j]);
            }
        }
        return ans;
    }

    private int search(int[] nums, int x, int l, int r) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = -1, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int j = lower_bound(nums.begin() + i + 1, nums.end(), k - nums[i]) - nums.begin() - 1;
            if (i < j) {
                ans = max(ans, nums[i] + nums[j]);
            }
        }
        return ans;
    }
};

func twoSumLessThanK(nums []int, k int) int {
    sort.Ints(nums)
    ans := -1
    for i, x := range nums {
        j := sort.SearchInts(nums[i+1:], k-x) + i
        if v := nums[i] + nums[j]; i < j && ans < v {
            ans = v
        }
    }
    return ans
}

function twoSumLessThanK(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = -1;
    for (let i = 0, j = nums.length - 1; i < j;) {
        const s = nums[i] + nums[j];
        if (s < k) {
            ans = Math.max(ans, s);
            ++i;
        } else {
            --j;
        }
    }
    return ans;
}

Solution 2: Sorting + Two Pointers

Thinking

One binary search per \(x\) is \(O(n\log n)\). Two pointers use the same monotonicity: a small sum moves the left end right; a sum of at least \(k\) moves the right end left.

A single pass covers the Pareto front of distinct-index pairs with a smaller constant.

Similar to Solution 1, we can first sort the array \(nums\), and initialize the answer as \(-1\).

Next, we use two pointers \(i\) and \(j\) to point to the left and right ends of the array, respectively. Each time we judge whether \(s = nums[i] + nums[j]\) is less than \(k\). If it is less than \(k\), then we can update the answer, i.e., \(ans = \max(ans, s)\), and move \(i\) one step to the right, otherwise move \(j\) one step to the left.

After the enumeration ends, return the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++Go

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        i, j = 0, len(nums) - 1
        ans = -1
        while i < j:
            if (s := nums[i] + nums[j]) < k:
                ans = max(ans, s)
                i += 1
            else:
                j -= 1
        return ans

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = -1;
        for (int i = 0, j = nums.length - 1; i < j;) {
            int s = nums[i] + nums[j];
            if (s < k) {
                ans = Math.max(ans, s);
                ++i;
            } else {
                --j;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = -1;
        for (int i = 0, j = nums.size() - 1; i < j;) {
            int s = nums[i] + nums[j];
            if (s < k) {
                ans = max(ans, s);
                ++i;
            } else {
                --j;
            }
        }
        return ans;
    }
};

func twoSumLessThanK(nums []int, k int) int {
    sort.Ints(nums)
    ans := -1
    for i, j := 0, len(nums)-1; i < j; {
        if s := nums[i] + nums[j]; s < k {
            ans = max(ans, s)
            i++
        } else {
            j--
        }
    }
    return ans
}

1099. Two Sum Less Than K 🔒

Description

Solutions

Solution 1: Sorting + Binary Search

Solution 2: Sorting + Two Pointers

Comments