Open In App

Two Sum - Pair with given Sum

Last Updated : 26 Jul, 2025
Suggest changes
Share
Like Article
Like
Report

Given an array arr[] of n integers and a target value, check if there exists a pair whose sum equals the target. This is a variation of the 2-Sum problem.

Examples: 

Input: arr[] = [0, -1, 2, -3, 1], target = -2
Output: true
Explanation: There is a pair (1, -3) with the sum equal to given target, 1 + (-3) = -2.

Input: arr[] = [1, -2, 1, 0, 5], target = 0
Output: false
Explanation: There is no pair with sum equals to given target.

[Naive Approach] Generating all Possible Pairs - O(n2) time and O(1) space

The basic approach is to generate all the possible pairs and check if any of them add up to the target value. To generate all pairs, we simply run two nested loops.

C++
#include <iostream> #include <vector> using namespace std; bool twoSum(vector<int> &arr, int target) {  int n = arr.size();  for (int i = 0; i < n; i++) {    // For each element arr[i], check every  // other element arr[j] that comes after it  for (int j = i + 1; j < n; j++) {    // Check if the sum of the current pair  // equals the target  if (arr[i] + arr[j] == target) {  return true;  }  }  }    // If no pair is found after checking  // all possibilities  return false; } int main() {    vector<int> arr = {0, -1, 2, -3, 1};  int target = -2;  if(twoSum(arr, target))  cout << "true";  else  cout << "false";  return 0; } 
C
#include <stdbool.h> #include <stdio.h> bool twoSum(int arr[], int n, int target){  for (int i = 0; i < n; i++){  // For each element arr[i], check every  // other element arr[j] that comes after it  for (int j = i + 1; j < n; j++){  // Check if the sum of the current pair  // equals the target  if (arr[i] + arr[j] == target)  return true;  }  }    // If no pair is found after checking  // all possibilities  return false; } int main(){  int arr[] = {0, -1, 2, -3, 1};  int target = -2;  int n = sizeof(arr) / sizeof(arr[0]);  // Call the twoSum function and print the result  if (twoSum(arr, n, target))  printf("true\n");  else  printf("false\n");    return 0; } 
Java
class GfG {  static boolean twoSum(int[] arr, int target){  int n = arr.length;  for (int i = 0; i < n; i++) {    // For each element arr[i], check every  // other element arr[j] that comes after it  for (int j = i + 1; j < n; j++) {    // Check if the sum of the current pair  // equals the target  if (arr[i] + arr[j] == target) {  return true;  }  }  }    // If no pair is found after checking  // all possibilities  return false;  }  public static void main(String[] args){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;    if (twoSum(arr, target))  System.out.println("true");  else  System.out.println("false");  } } 
Python
def twoSum(arr, target): n = len(arr) for i in range(n): # For each element arr[i], check every # other element arr[j] that comes after it for j in range(i + 1, n): # Check if the sum of the current pair # equals the target if arr[i] + arr[j] == target: return True # If no pair is found after checking # all possibilities return False if __name__ == "__main__": arr = [0, -1, 2, -3, 1] target = -2 if twoSum(arr, target): print("true") else: print("false") 
C#
using System; class GfG {  static bool twoSum(int[] arr, int target) {  int n = arr.Length;  for (int i = 0; i < n; i++) {    // For each element arr[i], check every  // other element arr[j] that comes after it  for (int j = i + 1; j < n; j++) {    // Check if the sum of the current pair  // equals the target  if (arr[i] + arr[j] == target) {  return true;  }  }  }    // If no pair is found after checking  // all possibilities  return false;  }  static void Main() {    int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target))  Console.WriteLine("true");  else   Console.WriteLine("false");  } } 
JavaScript
function twoSum(arr, target) {  let n = arr.length;  for (let i = 0; i < n; i++) {    // For each element arr[i], check every  // other element arr[j] that comes after it  for (let j = i + 1; j < n; j++) {    // Check if the sum of the current pair  // equals the target  if (arr[i] + arr[j] === target) {  return true;  }  }  }  // If no pair is found after checking  // all possibilities  return false; } // Driver Code let arr = [0, -1, 2, -3, 1]; let target = -2; if (twoSum(arr, target))  console.log("true"); else   console.log("false"); 

Output
true

[Better Approach 1] Sorting and Binary Search - O(n × log(n)) time and O(1) space

To check if a pair with a given sum exists in the array, we first sort the array. Then for each element, we compute the required complement (i.e., target - arr[i]) and perform binary search on the remaining subarray (from index i+1 to end) to find that complement.

Step By Step Implementation:

  • Sort the array in non-decreasing order. 
  • Loop through each element arr[i] from index 0 to n-2. 
  • For each arr[i], calculate complement = target - arr[i]. 
  • Perform binary search for complement in the subarray from index i+1 to n-1. 
  • If the complement is found, return true. 
  • If the loop completes without finding any valid pair, return false.
C++
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to perform binary search bool binarySearch(vector<int> &arr, int left,  int right, int target){  while (left <= right){  int mid = left + (right - left) / 2;  if (arr[mid] == target)  return true;  if (arr[mid] < target)  left = mid + 1;  else  right = mid - 1;  }  return false; } bool twoSum(vector<int> &arr, int target){    sort(arr.begin(), arr.end());    for (int i = 0; i < arr.size(); i++){  int complement = target - arr[i];  // Use binary search to   // find the complement  if (binarySearch(arr, i + 1,   arr.size() - 1, complement))  return true;  }    // If no pair is found  return false; } int main(){  vector<int> arr = {0, -1, 2, -3, 1};  int target = -2;  if (twoSum(arr, target))  cout << "true";  else  cout << "false";  return 0; } 
C
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> // Comparison function for qsort int compare(const void *a, const void *b){  return (*(int *)a - *(int *)b); } // Function to perform binary search bool binarySearch(int arr[], int left,  int right, int target){  while (left <= right){  int mid = left + (right - left) / 2;  if (arr[mid] == target)  return true;  if (arr[mid] < target)  left = mid + 1;  else  right = mid - 1;  }  return false; } bool twoSum(int arr[], int n, int target){    qsort(arr, n, sizeof(int), compare);  for (int i = 0; i < n; i++){  int complement = target - arr[i];  // Use binary search to  // find the complement  if (binarySearch(arr, i + 1,  n - 1, complement))  return true;  }  // If no pair is found  return false; } int main(){  int arr[] = {0, -1, 2, -3, 1};  int target = -2;  int n = sizeof(arr) / sizeof(arr[0]);  if (twoSum(arr, n, target))  printf("true\n");  else  printf("false\n");  return 0; } 
Java
import java.util.Arrays; class GfG {  // Function to perform binary search  static boolean binarySearch(int[] arr, int left,  int right, int target){  while (left <= right) {  int mid = left + (right - left) / 2;  if (arr[mid] == target)  return true;  if (arr[mid] < target)  left = mid + 1;  else  right = mid - 1;  }  return false;  }  static boolean twoSum(int[] arr, int target){    Arrays.sort(arr);  for (int i = 0; i < arr.length; i++) {  int complement = target - arr[i];  // Use binary search to find the complement  if (binarySearch(arr, i + 1, arr.length - 1,  complement))  return true;  }  // If no pair is found  return false;  }  public static void main(String[] args){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target)) {  System.out.println("true");  }  else {  System.out.println("false");  }  } } 
Python
# Function to perform binary search def binarySearch(arr, left, right, target): while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return True elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return False def twoSum(arr, target): arr.sort() for i in range(len(arr)): complement = target - arr[i] # Use binary search to find the complement if binarySearch(arr, i + 1, len(arr) - 1, complement): return True # If no pair is found return False if __name__ == "__main__": arr = [0, -1, 2, -3, 1] target = -2 if twoSum(arr, target): print("true") else: print("false") 
C#
using System; class GfG {  // Function to perform binary search  static bool binarySearch(int[] arr, int left,  int right, int target){  while (left <= right) {  int mid = left + (right - left) / 2;  if (arr[mid] == target)  return true;  if (arr[mid] < target)  left = mid + 1;  else  right = mid - 1;  }  return false;  }  static bool twoSum(int[] arr, int target){    Array.Sort(arr);  for (int i = 0; i < arr.Length; i++) {  int complement = target - arr[i];  // Use binary search to find the complement  if (binarySearch(arr, i + 1, arr.Length - 1,  complement))  return true;  }  // If no pair is found  return false;  }  static void Main(){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target)) {  Console.WriteLine("true");  }  else {  Console.WriteLine("false");  }  } } 
JavaScript
// Function to perform binary search function binarySearch(arr, left, right, target) {  while (left <= right) {  let mid = Math.floor(left + (right - left) / 2);  if (arr[mid] === target)  return true;  if (arr[mid] < target)  left = mid + 1;  else  right = mid - 1;  }  return false; } function twoSum(arr, target) {  arr.sort((a, b) => a - b);  for (let i = 0; i < arr.length; i++) {  let complement = target - arr[i];  // Use binary search to find the complement  if (binarySearch(arr, i + 1,   arr.length - 1, complement))  return true;  }  // If no pair is found  return false; } // Driver Code let arr = [0, -1, 2, -3, 1]; let target = -2; if (twoSum(arr, target)) {  console.log("true"); } else {  console.log("false"); } 

Output
true

[Better Approach 2] Sorting and Two-Pointer Technique - O(n × log(n)) time and O(1) space

The idea is to use the two-pointer technique but for using the two-pointer technique, the array must be sorted. Once the array is sorted then we can use this approach by keeping one pointer at the beginning (left) and another at the end (right) of the array.

Check the sum of the elements at these two pointers:

  • If the sum equals the target, we’ve found the pair.
  • If the sum is less than the target, move the left pointer to the right to increase the sum.
  • If the sum is greater than the target, move the right pointer to the left to decrease the sum.

Note: This approach is the best approach for a sorted array. But if array is not sorted, then we use the below approach.

C++
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool twoSum(vector<int> &arr, int target){    sort(arr.begin(), arr.end());  int left = 0, right = arr.size() - 1;  // Iterate while left pointer   // is less than right  while (left < right){  int sum = arr[left] + arr[right];  // Check if the sum matches the target  if (sum == target)  return true;  else if (sum < target)    // Move left pointer to the right  left++;   else    // Move right pointer to the left  right--;   }  // If no pair is found  return false; } int main(){  vector<int> arr = {0, -1, 2, -3, 1};  int target = -2;  if (twoSum(arr, target))  cout << "true";  else  cout << "false";  return 0; } 
C
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> // Comparison function for qsort int compare(const void *a, const void *b){  return (*(int *)a - *(int *)b); } bool twoSum(int arr[], int n, int target){    qsort(arr, n, sizeof(int), compare);  int left = 0, right = n - 1;  // Iterate while left pointer is less than right  while (left < right){  int sum = arr[left] + arr[right];  // Check if the sum matches the target  if (sum == target)  return true;  else if (sum < target)    // Move left pointer to the right  left++;   else    // Move right pointer to the left  right--;   }  // If no pair is found  return false; } int main(){  int arr[] = {0, -1, 2, -3, 1};  int target = -2;  int n = sizeof(arr) / sizeof(arr[0]);  if (twoSum(arr, n, target))  printf("true\n");   else  printf("false\n");  return 0; } 
Java
import java.util.Arrays; class GfG {  static boolean twoSum(int[] arr, int target){    Arrays.sort(arr);  int left = 0, right = arr.length - 1;  // Iterate while left pointer is less than right  while (left < right) {  int sum = arr[left] + arr[right];  // Check if the sum matches the target  if (sum == target)  return true;  else if (sum < target)    // Move left pointer to the right  left++;   else    // Move right pointer to the left  right--;  }  // If no pair is found  return false;  }  public static void main(String[] args){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target)) {  System.out.println("true");  }  else {  System.out.println("false");  }  } } 
Python
def twoSum(arr, target): arr.sort() left, right = 0, len(arr) - 1 # Iterate while left pointer is less than right while left < right: sum = arr[left] + arr[right] # Check if the sum matches the target if sum == target: return True elif sum < target: # Move left pointer to the right left += 1 else: # Move right pointer to the left right -= 1 # If no pair is found return False if __name__ == "__main__": arr = [0, -1, 2, -3, 1] target = -2 if twoSum(arr, target): print("true") else: print("false") 
C#
using System; using System.Linq; class GfG {  static bool twoSum(int[] arr, int target){    Array.Sort(arr);  int left = 0, right = arr.Length - 1;  // Iterate while left pointer is less than right  while (left < right) {  int sum = arr[left] + arr[right];  // Check if the sum matches the target  if (sum == target)  return true;  else if (sum < target)    // Move left pointer to the right  left++;   else    // Move right pointer to the left  right--;   }  // If no pair is found  return false;  }  static void Main(){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target))  Console.WriteLine("true");  else   Console.WriteLine("false");  } } 
JavaScript
function twoSum(arr, target) {  arr.sort((a, b) => a - b);  let left = 0, right = arr.length - 1;  // Iterate while left pointer is less than right  while (left < right) {  let sum = arr[left] + arr[right];  // Check if the sum matches the target  if (sum === target)  return true;  else if (sum < target)    // Move left pointer to the right  left++;   else    // Move right pointer to the left  right--;   }  // If no pair is found  return false; } // Driver Code let arr = [ 0, -1, 2, -3, 1 ]; let target = -2; if (twoSum(arr, target)) {  console.log("true"); } else {  console.log("false"); } 

Output
true

[Expected Approach] Using Hash Set - O(n) time and O(n) space

Hashing provides a more efficient solution to the 2-Sum problem. Rather than checking every possible pair, we store each number in an unordered set during iterating over the array's elements. For each number, we calculate its complement (i.e., target - current number) and check if this complement exists in the set. If it does, we have successfully found the pair that sums to the target.

Step By Step Implementations:

  • Create an empty Hash Set or Unordered Set
  • Iterate through the array and for each number in the array:
    => Calculate the complement (target - current number).
    => Check if the complement exists in the set:
    - If it is, then pair found.
    - If it isn’t, add the current number to the set.
  • If the loop completes without finding a pair, return that no pair exists.
C++
#include <iostream> #include <vector> #include <unordered_set> using namespace std; bool twoSum(vector<int> &arr, int target){    // Create an unordered_set to store the elements  unordered_set<int> s;  for (int i = 0; i < arr.size(); i++){  // Calculate the complement that added to  // arr[i], equals the target  int complement = target - arr[i];  // Check if the complement exists in the set  if (s.find(complement) != s.end())  return true;  // Add the current element to the set  s.insert(arr[i]);  }    // If no pair is found  return false; } int main(){  vector<int> arr = {0, -1, 2, -3, 1};  int target = -2;  if (twoSum(arr, target))  cout << "true";  else  cout << "false";  return 0; } 
Java
import java.util.HashSet; class GfG {  static boolean twoSum(int[] arr, int target){  // Create a HashSet to store the elements  HashSet<Integer> set = new HashSet<>();  for (int i = 0; i < arr.length; i++) {  // Calculate the complement that added to  // arr[i], equals the target  int complement = target - arr[i];  // Check if the complement exists in the set  if (set.contains(complement)) {  return true;  }  // Add the current element to the set  set.add(arr[i]);  }  // If no pair is found  return false;  }  public static void main(String[] args){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target))  System.out.println("true");  else  System.out.println("false");  } } 
Python
def twoSum(arr, target): # Create a set to store the elements s = set() for num in arr: # Calculate the complement that added to # num, equals the target complement = target - num # Check if the complement exists in the set if complement in s: return True # Add the current element to the set s.add(num) # If no pair is found return False if __name__ == "__main__": arr = [0, -1, 2, -3, 1] target = -2 if twoSum(arr, target): print("true") else: print("false") 
C#
using System; using System.Collections.Generic; class GfG {  static bool twoSum(int[] arr, int target){  // Create a HashSet to store the elements  HashSet<int> set = new HashSet<int>();  for (int i = 0; i < arr.Length; i++) {  // Calculate the complement that added to  // arr[i], equals the target  int complement = target - arr[i];  // Check if the complement exists in the set  if (set.Contains(complement))  return true;  // Add the current element to the set  set.Add(arr[i]);  }  // If no pair is found  return false;  }  static void Main(){  int[] arr = { 0, -1, 2, -3, 1 };  int target = -2;  if (twoSum(arr, target))  Console.WriteLine("true");  else   Console.WriteLine("false");   } } 
JavaScript
function twoSum(arr, target) {  // Create a Set to store the elements  let set = new Set();  for (let num of arr) {    // Calculate the complement that added to  // num, equals the target  let complement = target - num;  // Check if the complement exists in the set  if (set.has(complement)) {  return true;  }  // Add the current element to the set  set.add(num);  }  // If no pair is found  return false; } // Driver Code let arr = [0, -1, 2, -3, 1]; let target = -2; if (twoSum(arr, target))  console.log("true"); else   console.log("false"); 

Output
true

Related Problems:  


Explore