Two Pointer Algorithm to Find Maximum Two Sum Less Than K

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 <= A.length <= 100
• 1 <= A[i] <= 1000
• 1 <= K <= 2000

Intutive Bruteforce Algorithm to Find Maximum Tow Sum Pair Less than K

The bruteforce is the most intutive algorithm that we can use. We can bruteforce the two-pair in O(N^2) time complexity. Then, if the sum is less than K, we record the maxium.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        int r = -1;
        for (int i = 0; i < A.size(); ++ i) {
            for (int j = i + 1; j < A.size(); ++ j) {
                if (A[i] + A[j] < K) {
                    r = max(r, A[i] + A[j]);
                }
            }
        }
        return r;
    }
};

class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        int r = -1;
        for (int i = 0; i < A.size(); ++ i) {
            for (int j = i + 1; j < A.size(); ++ j) {
                if (A[i] + A[j] < K) {
                    r = max(r, A[i] + A[j]);
                }
            }
        }
        return r;
    }
};

The above C++ bruteforce two-pair algorithm takes O(1) constant space.

Sort and Two Pointer Algorithm to Find Maximum Tow Sum Pair Less than K

If we sort the array which takes O(nlogN) time, we can apply the two-pointer algorithm by initialising the two points at two ends. If the current sum is less than K, we record and update the maximum. At each iteration, depending on the comparison between K and the current sum, we move the corresponding pointer.

The two pointer algorithm takes O(N), and overall the complexity is O(nlogN).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

Same algorithm but implemented in Python3 is given as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def twoSumLessThanK(self, A: List[int], K: int) -> int:
        A = sorted(A)
        ans = -1
        j = 0
        k = len(A) - 1
        while j < k:
            if A[j] + A[k] < K:
                ans = max(ans, A[j] + A[k])
                j += 1
            else:
                k -= 1
        return ans

class Solution:
    def twoSumLessThanK(self, A: List[int], K: int) -> int:
        A = sorted(A)
        ans = -1
        j = 0
        k = len(A) - 1
        while j < k:
            if A[j] + A[k] < K:
                ans = max(ans, A[j] + A[k])
                j += 1
            else:
                k -= 1
        return ans

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —