Lowest Sum of Pair Larger than Target

Description

You are given a list of integers nums and an integer target. Return the lowest sum of pair of numbers that is greater than target. You can assume that a solution exists.

Constraints:

• 2 ≤ n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [1, 3, 5, 9, 13]
target = 8

Output

10

Explanation

We pick 1 and 9

---

Implementation 1

import java.util.*;

class Solution {
    public int solve(int[] nums, int target) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < n - 1; i++) {
            int pair = binarySearchTargetRight(nums, i + 1, target - nums[i]);
            int sum = nums[i] + nums[pair];
            if (sum > target) {
                ans = Math.min(ans, sum);
            }
        }
        return ans;
    }

    private int binarySearchTargetRight(int[] nums, int l, int target) {
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

Time Complexity

• Time:
• Space:

---

Implementation 2

import java.util.*;

class Solution {
    public int solve(int[] nums, int target) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        int ans = Integer.MAX_VALUE;
        while (l < r) {
            int sum = nums[l] + nums[r];
            if (sum > target) {
                ans = Math.min(ans, sum);
                r--;
            } else {
                l++;
            }
        }
        return ans;
    }
}

Time Complexity

• Time:
• Space: