Problem: K-Sum

Given a sorted array A and an integer key. We need to determine whether there exist two elements in A whose sum is equal to key. The two elements can be the same entry in the array (i.e., we may use the same number twice). We should return True if such a pair exists; otherwise, return False.

K-Sum

Example
Input: A = [1, 2, 3, 4, 5] and key=6
Output: True
We can take 2 + 4 = 6 or 1 + 5 = 6.

Here,
Input: A = [1, 2, 3, 4, 5] and key=11
Output: False
No two elements (even the same element twice) sum up to 11.

Exhaustive Logic (Brute Force):

We want to check if two numbers add up to the key or not. So, for that we can simply check every possible pair(including an element with itself)

check_two_sum_brute_force(A, key)
    // A is the Array
    // Key is the sum we need to check
    // starting index is 0
    n = A.length - 1 
    for (i = 0; i <= n; i++)
        for (j = i; j <= n; j++)
            if ((A[i] + A[j]) == key)
                return True
     return False

The equivalent Python code is,

def check_two_sum_brute_force(A, key):
    n = len(A)
    # Iterate over all pairs (i, j)
    for i in range(n):
        for j in range(n):
            if A[i] + A[j] == key:
                return True
    return False

The time complexity for this approach is O(n²)

If we extend the problem to check for a sum of 3 numbers instead of 2, we would need to add a loop over the array, increasing the time complexity to O(n³).

Recursive Approach

For the sake of practice, let's try to solve this recursively.
For the base case, think as if we only have one element in the array. If that is the case, then the starting index and ending index are the same, and we have to compute their sum and check that with the key.

check_two_sum_recursively(A, l, r, key)
    // l is left index, r is right index
    if l > r
        return False

    if (A[l] + A[r] == key)
        return True

    else if (A[l] + A[r] > key)
        return check_two_sum_recursively(A, l, r - 1, key)
    else
        return check_two_sum_recursively(A, l + 1, r, key)

The Python solution for this approach will be,

def check_two_sum_recursively(A, l, r, key):
    # Base case: no valid pair
    if l > r:
        return False
    
    # Check current pair
    if A[l] + A[r] == key:
        return True
    elif A[l] + A[r] > key:
        return check_two_sum_recursively(A, l, r - 1, key)
    else:
        return check_two_sum_recursively(A, l + 1, r, key)

At each recursive call, we either increment l or decrement r. That means in the worst case, we make at most n recursive calls (where n is the length of the array.
So, the time complexity for this approach is O(n) . Because it’s recursive, each call is pushed onto the call stack. Worst case depth = O(n) recursive calls → O(n) space.

Here is another way to code this problem,

check_two_sum_recursively(A, l, r, key)
    if (l == r)
        if (A[l] + A[r] == key)
              return True;
        else
              return False;
     else
         if (A[l] + A[r] == key)
              return True
         else if (A[l] + A[r] > key)
              return check_two_sum_recursively(A, l, r - 1, key)
         else
              return check_two_sum_recursively(A, l + 1, r, key)

Here the,
Time Complexity: O(n)
Space Complexity: O(n) (because of recursion stack)

Optimal Solution (Binary Search approach)

We are given that the array is sorted, so we can use this to our advantage. We start with two pointers: one at the beginning (left) and one at the end (right). We compute the sum of these two elements and compare it with the key:
- If the sum is greater than the key, we know we need a smaller number, so we move the right pointer left (right--). Since the array is sorted, this gives us a smaller number.
- If the sum is smaller than the key, we need a larger number, so we move the left pointer right (left++).
- If the sum matches the key, we return True.

Get Prajun Trital’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Because we are allowed to use the same number twice, we use left <= right in the while loop.

check_two_sum_optimal(A, key)
    // indexing is 0 based
    left = 0;
    right = A.length - 1
    while (left <= right) // <= because we can use the same number twice
        if (A[left] + A[right] == key)
            return True;
        else if (A[left] + A[right] > key)
            right--;
        else
            left++;
    return False

The equivalent Python code for this will be

def check_two_sum_optimal(A, key):
    left = 0
    right = len(A) - 1

    # <= because we can use the same number twice
    while left <= right:
        current_sum = A[left] + A[right]

        if current_sum == key:
            return True
        elif current_sum > key:
            right -= 1
        else:
            left += 1

    return False

The time complexity is O(n)
The space complexity is O(1)

Let's try to extend this problem to check the sum of three numbers.

check_three_sum_optimal(A, key)
    // indexing is 0 based

    n = A.length - 1
    
    for (i = 0; i >= n; i++)
        // Fix A[i], now look for two numbers in the rest that sum to (key - A[i])
        left = i;    // left can start at i (allows using A[i] twice)
        right = n

        while (left <= right) // <= because we can use the same number twice
            current_sum = A[i] + A[left] + A[right]
            if (current_sum == key)
                return True;
            else if (current_sum > key)
                right--;
            else
                left++;
     return False

Time: O(n²), Space: O(1)

In this approach, we allow a single number to be used twice. So we can form combinations like (A[i], A[i], A[right]) or (A[i], A[left], A[left]). However, we will not get the same element three times. In that case, we need a separate check at the beginning:

    for i in range(n):
        if 3 * A[i] == key:
            return True

Here is the recursive solution:

// A: The sorted array
// i: The index of the *first* element we are fixing
// n: The last index of the array
// key: The target sum
check_three_sum_recursively(A, i, n, key):

    // Base Case: If 'i' is too close to the end, 
    // there aren't two elements left to form a triplet.
    if (i >= n - 1):  // e.g., if i = n-2, l=n-1, r=n. This is the last possible triplet.
        return False
    
    // 1. Fix the first element
    first_element = A[i]
    
    // 2. Define the new target for the 2-sum problem
    two_sum_key = key - first_element
    
    // 3. Define the search space for the 2-sum problem
    l = i + 1
    r = n
    
    // 4. Solve the 2-sum problem for the rest of the array
    found_pair = check_two_sum_recursively(A, l, r, two_sum_key)
    
    if (found_pair):
        // We found a triplet: (A[i], and the pair from the helper)
        return True
    else:
        // No triplet found *starting with A[i]*.
        // Move on and try again, fixing A[i+1] as the first element.
        return check_three_sum_recursively(A, i + 1, n, key)



// Helper Function for two sum
check_two_sum_recursively(A, l, r, key):
    
    // Base Case: Pointers met or crossed, so no pair was found.
    if (l >= r):
        return False
    
    // --- RECURSION & WORK ---
    
    current_sum = A[l] + A[r]
    
    if (current_sum == key):
        return True
    else if (current_sum > key):
        // Sum is too big, move the right pointer in
        return check_two_sum_recursively(A, l, r - 1, key)
    else: // current_sum < key
        // Sum is too small, move the left pointer in
        return check_two_sum_recursively(A, l + 1, r, key)

Some Leetcode problems to practice (Most asked in interviews):

• 15. 3Sum — classic three-pointer two-sum extension. LeetCode
• 167. Two Sum II – Input Array Is Sorted — two-pointer variant of the basic two-sum. LeetCode

Common but Less Frequent:

• 88. Merge Sorted Array — merging two arrays with pointers. LeetCode
• 881. Boats to Save People — greedy two-pointer pairing. LeetCode

Additional ones

• 1498. Number of Subsequences That Satisfy the Given Sum Condition — two-pointer counting variant. LeetCode
• 78. Sort Colors — Dutch national flag problem (three-way pointer). LeetCode

🔙 Back to all notes
𝕏 Let’s Connect

Backlinks:
Design and Analysis of Algorithms