Pair With Given Sum in Unsorted Array

by

In this question, we have to find the pair with given sum in unsorted array. We have been given an unsorted array along with a number say k. You’ll have to look if there is a pair in the given array whose sum is equal to k. 

Input: nums = [3, 2, 8, 15, -8]
          k = 17
Output: True // 2+15 = 17

Input: nums = [2, 1, 6, 3]
          k = 6
Output: False

Input: nums = [5, 8, -3, 6]
          k = 3
Output: True

Brute Force Approach to Find Pair With Given Sum in Unsorted Array

Approach: In this method, check for all possible pairs if their sum is equal to the number k. If a valid pair is found, return true otherwise return false. Below we have shown the implementation of the described approach to solve pair with given sum in unsorted array in C++.

#include <iostream>
#include <vector>

using namespace std;
//program to find pair with given sum in unsorted array
bool validSum(vector<int> &nums, int &k){
    int n = nums.size(), i, j;
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){//started iterating from i+1 to avoid testing previously tested pairs
            if(nums[i]+nums[j]==k)
                return true;//checking if the sum of current pair is equal to k
        }
    }
    return false;//returns false if no pair is found
}
//driver code to test the validSum function
int main()
{
    vector<int> nums;
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(8);
    nums.push_back(15);
    nums.push_back(-8);
    
    int k = 17;
    
    bool ans = validSum(nums, k);//calling the validSum function
    if(ans == true)
        cout<<"True";
    else    
        cout<<"False";

    return 0;
}

Complexity Analysis:
Time Complexity: O(N2)//as we have used nested loop
Space Complexity: O(1)//since no extra space is used

Two Pointer Approach to Find Pair With Given Sum in Unsorted Array

Approach: Firstly sort the array and then take two pointers, one at the beginning and another at the end of the sorted array. If the sum of the numbers is equal to k, return true. If the sum is greater than k, shift the right pointer to decrease the sum, else if the sum is lesser than k, shift the left pointer to increase the sum. Once pointers cross each other, which means no valid pair is present, then return false. Let’s understand this approach with an example.

Input: nums = [3, 2, 8, 15, -8]
          k = 17
After sorting the array we have nums = [-8, 2, 3, 8, 15]
Now let's initialize two pointers, i.e., i=0 and j=n-1 = 4(where n is the size of array).
nums[i]+nums[j] = -8+15 = 7<17. Therefore, we'll increment the value of i. Now i=1 and j=4
nums[i]+nums[j] = 2+15 = 17. Here we have found a pair which satisfies the criteria and hence we return true

Below we have shown the implementation of the described approach to solve pair with given sum in unsorted array in C++.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//program to find pair with given sum in unsorted array
bool validSum(vector<int> &nums, int &k){
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int i = 0, j = n-1;
    while(i<j){
        if(nums[i]+nums[j]==k)
            return true;//on finding a valid pair the function returns true
        else if (nums[i]+nums[j]>k)
            j--;//if sum of the element is greater than k we shift j to the left
        else 
            i++;//if sum of the element is lesser than k we shift i to the right
    }
    
    return false;//returns false if no pair is found
}
//driver code to test the validSum function
int main()
{
    vector<int> nums;
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(8);
    nums.push_back(15);
    nums.push_back(-8);
    
    int k = 17;
    
    bool ans = validSum(nums, k);//calling the validSum function
    if(ans == true)
        cout<<"True";
    else    
        cout<<"False";

    return 0;
}

Complexity Analysis

Time Complexity: O(nlogn) //as we use the sorting algorithm
Space Complexity: O(1)//as we don’t use extra space

Hashing Approach to Find Pair With Given Sum in Unsorted Array

One of the common mistakes that students commit using hashing is that they first insert everything in a hash table and then traverse through the array to find the (sum – arr[i]) element in the hash table. To visualize the problem let’s take an example.

Given nums = {8, 3, 2, 5} and k = 6. Now the problem is that you’ll find a valid pair once you reach nums[1] i. e., 3, and find 6-3 = 3 in the hash table. You’ll return true but you had to return a false value because if you look at the array, you’ll not find a valid pair with a given sum.

Correct Approach: Insert elements into the hash table one by one from the given array, but before that check, if it forms a pair with an existing element of the hash table.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;
//program to find pair with given sum in unsorted array
bool validSum(vector<int> &nums, int &k){
    int n = nums.size(), i;
    unordered_set <int> h;//we create an unordered set 
    for(i=0;i<n;i++){
        if(h.find(k - nums[i])!= h.end())
            return true;//if we find a valid pair we'll return true
        else
            h.insert(nums[i]);
    }
    return false;//otherwise we return false
}
//driver code to test the validSum function
int main()
{
    vector<int> nums;
    nums.push_back(8);
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(5);
    int k = 6;
    
    bool ans = validSum(nums, k);//calling the validSum function
    if(ans == true)
        cout<<"True";
    else    
        cout<<"False";

    return 0;
}

Complexity Analysis

Time Complexity: O(N) //as we traverse the array only once
Space Complexity: O(N)//since we create a set

Hope you liked the article and if it interests you, visit our website for articles on different topics like Insertion Sort – A Stable Sorting Algorithm, Rotating Elements of a Matrix by 90 Degrees, Median of Two Sorted Arrays | Leetcode Problem #4

Leave a Comment