Given an unsorted array of integers find a pair with given sum in it

Algorithm to find a pair of integers in unsorted array with a given sum k.

Example

Input:
var arr = [15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10];
k = 25;
  
Output:
true  (If found)
or
false (If Not found) 

1. Brute Force Method (Naive Approach) O(n^2)

In brute force method we will evaluate all the possible pairs and check if desired sum is found.

function findSum(arr, k){
  //Length of array
  var len = arr.length;

  //Initialize to false so that it can be checked
  var isFound = false;

   //Check each element
   for(var i = 0; i < len; i++){

    //Check with every next element
    for(var j = i+1; j < len; j++){

     //If matched
     if(arr[i] + arr[j] === k){

        //Mark true and break;
        isFound = true;
        break;

      }

    }

  }
  //Return
  return isFound;
}

console.log(findSum([15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10], 25));
console.log(findSum([15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10], 100));

Output:
true (15+10) (4 + 21) (11 + 14) (24 + 1)
false

Time complexity: O(n^2).
Space complexity: O(1).

Explanation

• Starting form the frist element in the array we sum it with it's every next elements.
• 15 -> (15 + 4) -> (15 + 9) -> (15 + 3) -> (15 + 2) -> (15 + 12) -> (15 + 11) -> (15 + 14) -> (15 + 21) -> (15 + 24) -> (15 + 1) -> (15 + 10)(found)
• If found we break the loop, Else continue the process with next element in the array until pair with given sum is found.

Time and Space Complexity

• We are looping each element with all its next elements like n(n-1) + n-1(n-2) + n-2(n-3) ... => n(n-1)/2 => O(n^2)
• We are just using one extra variable isFound so space complexity = O(1)

2. Using Sorting O(nlogn)

In this approach we sort the given array in ascending order and maintain two indices one at lowest(0) and another at highest(Array.length - 1) and check until lower index is less than higher index.

function findSum(arr, k){
  //Sort the array (Inbuilt function)
  arr.sort();

  //Maintain two index
  var low = 0;
  var high = arr.length - 1;

  //Initialize to false
  var isFound = false;
  
  //loop till low < high
  while(low < high){
     //if pair is found
     if(arr[low] + arr[high] === k){
       isFound = true;
       break;
     }

     //reduce the search array
     if(arr[low] + arr[high] < k){
        low++;
     }else{
        high--;
     }  
  }
  return isFound;
}

console.log(findSum([15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10], 25));
console.log(findSum([15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10], 100));

Output:
true
false

Time complexity: O(nlogn).
Space complexity: O(1).

Explanation

Example 1
After Sorting:
arr = [1, 2, 3, 4, 9, 10, 11, 12, 14, 15, 21, 24]
k = 25

• We will start by adding first(low) and last element(high) in the array
• arr[low] + arr[high] = 1 + 24 = 25
• It is equal to k so break the loop, pair with given sum found

Example 2
After Sorting:
arr = [1, 2, 3, 4, 9, 10, 11, 12, 14, 15, 21, 24]
k = 100

• We will start by adding first(low) and last element(high) in the array
• arr[low] + arr[high] = 1 + 24 = 25 != k
• If arr[low] + arr[high] < k then low++, so low = 1
• Repeat the process again
• arr[low] + arr[high] = 2 + 24 = 26 != k
• If arr[low] + arr[high] < k then low++, so low = 2
• Repeat until the pair with given sum k is found, If found break else repeat

Time and Space complexity

• We are sorting the array which takes O(nlogn) and then checking with looping on each element of array which is O(n) so O(nlogn + n) = O(nlogn)
• We are just using one extra variable isFound so space complexity = O(1)

3. Using Hashing O(n)

In this approach we store each element in HashMap and also check if difference(k - arr[i]) already exits or not, if found break the loop. Using this method we can solve this in linear time O(n).

function findSum(arr, k){
  //use set to store unique elements
  var hashMap = new Set();

  //Initialize to false
  var isFound = false;
  
  //Loop through each element
  for(var i = 0; i < arr.length; i++){
     //Check if difference pair already exists in hashMap
     if(hashMap.has(k - arr[i])){
       isFound = true;
       break;
     }
     
     hashMap.add(arr[i]);
  }
  return isFound;
}

console.log(findSum([15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10], 25));
console.log(findSum([15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10], 100));

Output:
true
false

Time complexity: O(n).
Space complexity: O(n).

Explanation

Example 1
arr = [15, 4, 9 ,3 ,2, 12, 11, 14, 21, 24, 1, 10]
k = 25

• We will start by creating new hashMap to store the unique values.
• s.has(k - arr[i]) = s.has(25 - 15 = 10), No then continue and store the arr[i] i.e 15 in s.
• Repeat until the pair with given sum k is found, If found return true else return false.

Time and Space complexity

• As worst case for searching in HashMap is O(N), Time Complexity = O(N).
• We are storing each value of array in HashMap, Space Complexity = O(N).