1083. Two Sum Less Than K

• Difficulty: Easy

• Topics: Array

• Similar Questions:

  • Two Sum

  • Two Sum II - Input array is sorted

  • 3Sum Smaller

  • Subarray Product Less Than K

Problem:

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

Example 1:

Input: A = [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: A = [10,20,30], K = 15
Output: -1
Explanation: 
In this case it's not possible to get a pair sum less that 15.

Note:

1. 1 <= A.length <= 100
2. 1 <= A[i] <= 1000
3. 1 <= K <= 2000

Solutions:

class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        if (A.size() < 2)   return -1;
        int ret = INT_MIN;
        int left = 0;
        int right = A.size() - 1;
        sort(A.begin(), A.end());
        while (left < right) {
            if (A[left] + A[right] >= K) {
                --right;
            } else {
                ret = max(ret, A[left] + A[right]);
                ++left;
            }
        }

        return ret == INT_MIN ? -1 : ret;
    }
};

It is possible to use count sort to reduce the space complexity from O(nlogn) to O(n).

bucket sort strict O(n) solution-solution)

class Solution {

    class Node {
        int v;
        int f;
        public Node(int v, int f) {
            this.v =v;
            this.f = f;
        }

        public String toString(){return v +"-" + f;}
    }
    public int twoSumLessThanK(int[] A, int k) {
        if(A == null || A.length < 1) return -1;


        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int a : A) {
            min = Math.min(min, a);
            max = Math.max(max, a);
        }

        Node[] buckets = new Node[max+1];
        for(int a : A) {
            if(buckets[a] == null) buckets[a] = new Node(a, 0);
            buckets[a].f ++;
        }

        Node cur = null;
        for(int i = 0; i<= max; i++) {
            if( buckets[i] != null && buckets[i].v == i) {
                cur = buckets[i];
            }

            buckets[i] = cur;
        }
        int sum = -1;

        for(int a : A) {
            int target = k - a - 1;
            if(target < min) continue;
            if(target > max) target = max;
            if(a == buckets[target].v && buckets[target].f == 1) continue;
            sum = Math.max(sum, buckets[target].v + a);
        }
        return sum;
    }
}