Find a Pair with Sum K in an Unsorted Array Using Hashtable

Finding a pair of numbers with a given sum (K) in an unsorted array can be performed efficiently using a hashtable. The idea is to iterate through the array, and for each element, calculate the value needed to achieve the sum K. Store this needed value in a hashtable. As you proceed, check if the current element is one of the needed values stored in the hashtable. If it is, a pair that sums to K has been found. This approach has 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
import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    int[] array = {5, 2, 1, 6, 9, 3};
    int K = 10;
    HashSet<Integer> set = new HashSet<>();

    for (int num : array) {
      if (set.contains(num)) {
        System.out.println("Pair found: " + num + ", " + (K - num));
        return;
      }
      set.add(K - num);
    }
    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
#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int array[] = {5, 2, 1, 6, 9, 3};
  int K = 10;
  unordered_set<int> set;

  for (int num : array) {
    if (set.find(num) != set.end()) {
      cout << "Pair found: " << num << ", " << K - num << endl;
      return 0;
    }
    set.insert(K - num);
  }
  cout << "No pair found." << endl;
  return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
array = [5, 2, 1, 6, 9, 3]
K = 10
set_ = set()

for num in array:
    if num in set_:
        print(f"Pair found: {num}, {K - num}")
        break
    set_.add(K - num)
else:
    print("No pair found.")

Key Takeaways

A single iteration through the array is needed, making the algorithm efficient with a time complexity of O(n).
A hashtable is used to store the values needed to complete the sum K.
During each iteration, the current element is checked against the hashtable to see if it completes a pair that sums to K.