Find a Pair with Sum K by Traversing Sorted Array Forwards and Backwards

In a sorted array, finding a pair of numbers that sum up to a given value (K) can be achieved by using two index variables. One starts at the beginning of the array and the other at the end. Then, traverse the array by incrementing or decrementing the indexes based on the sum of the elements at those positions. The goal is to meet in the middle with a pair of numbers that sum up to K. This method is efficient, with a time complexity of O(n).

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Main {
  public static void main(String[] args) {
    int[] array = {1, 3, 4, 5, 7, 8, 9};
    int K = 12;
    int left = 0;
    int right = array.length - 1;
    
    while (left < right) {
      int sum = array[left] + array[right];
      if (sum == K) {
        System.out.println("Pair found: " + array[left] + ", " + array[right]);
        return;
      } else if (sum < K) {
        left++;
      } else {
        right--;
      }
    }
    
    System.out.println("No pair found.");
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int main() {
  int array[] = {1, 3, 4, 5, 7, 8, 9};
  int K = 12;
  int left = 0;
  int right = sizeof(array) / sizeof(array[0]) - 1;
  
  while (left < right) {
    int sum = array[left] + array[right];
    if (sum == K) {
      cout << "Pair found: " << array[left] << ", " << array[right] << endl;
      return 0;
    } else if (sum < K) {
      left++;
    } else {
      right--;
    }
  }
  
  cout << "No pair found." << endl;
  return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
array = [1, 3, 4, 5, 7, 8, 9]
K = 12
left = 0
right = len(array) - 1

while left < right:
    sum = array[left] + array[right]
    if sum == K:
        print(f"Pair found: {array[left]}, {array[right]}")
        break
    elif sum < K:
        left += 1
    else:
        right -= 1
else:
    print("No pair found.")

Key Takeaways

Two index variables, one starting at the beginning and the other at the end, are used to traverse the array.
The sum of the elements at the two index positions determines the next move: increment left if the sum is smaller than K, and decrement right if the sum is larger.
The algorithm stops when a pair is found or the indices cross each other.
The time complexity is O(n), making this an efficient approach for finding such pairs.