Home » Data Structure » Hashing Coding Problems

Given an array A[] and number X, check for pair in A[] with sum X | using two pointer algorithm, O(1) space complexity | Set 2

In this article, we are going to check how we can use two pointer algorithms to solve the two-sum problem without any additional space?
Submitted by Radib Kar, on July 18, 2020

Prerequisite:

• Hashing data structure
• Given an array A[] and number X, check for pair in A[] with sum X | using hashing O(n) time complexity | Set 1

Problem statement:

Given an array and a sum X, fins any pair which sums to X without using additional space.

Example:

Input array:
[4, -1, 6, 5, -2, 2]
Sum, X=2

Output:
Pair {4,-2}

Explanation:
4+(-2)=2 and thus the pair is {4,-2}

Solution:

In the set 1, we saw how to solve this problem using brute force and using hashing. We also found that due to additional hash table creation the algorithm has additional space complexity O(n). In this section, we will discuss how to solve this in constant space that is without using any additional space complexity.

The idea is to use the standard two-pointer algorithm where we keep two pointers at two ends of the array and based on the logic used, we traverse the pointers.

To solve this problem using two pointer algorithm, we require the input array to be sorted. Since the input array can be unsorted as well, we require to sort the input array as a pre-requisite step and then can perform the below to pointer algorithm:

1)  Initially set left pointer to the left end, i.e., left=0
2)  Initially set right pointer to the right end, i.e., 
    right=n-1, where n be the size of the array
3)  While left<right
        If arr[left] + arr[right]==X
            We have find the pair { arr[left], arr[right]}
		Else if arr[left] + arr[right]<X
			Increment left as current sum is less than X
            (that's why we need sorted array)
		Else // if arr[left] + arr[right]>X
			Decrement right as current sum is more than X
            (that's why we need sorted array)
	End While
4)  If not returned in the loop then there is no pair found

We can perform the above algorithm, using our example:

[4, -1, 6, 5, -2, 2]
X=2
After sorting:
[-2,-1, 2, 4, 5, 6]
Initially:
Left=0
Right=5

Iteration 1:
Left<right
arr[left]+arr[right]=4
So current sum>X
So decrement right
Iteration 2:
Left=0
Right=4
Left<right
arr[left]+arr[right]=3
So current sum>X
So decrement right

Iteration 3:
Left=0
Right=3
Left<right
arr[left]+arr[right]=2
So current sum==X
Thus return { arr[left], arr[right]}

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

pair<int, int> find_pair_sum(vector<int> arr, int n, int X)
{
    //sort the array takes O(logn)
    sort(arr.begin(), arr.end());

    int left = 0, right = arr.size() - 1;

    while (left < right) {

        if (arr[left] + arr[right] == X)
            return make_pair(arr[left], arr[right]);
        else if (arr[left] + arr[right] > X)
            right--;
        else
            left++;
    }

    return make_pair(INT_MAX, INT_MAX);
}

int main()
{
    cout << "Enter number of input elements,n\n";
    int n;
    cin >> n;
 
    cout << "Enter the input elements\n";
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << "Enter sum, X\n";
    int X;
    cin >> X;

    pair<int, int> p = find_pair_sum(arr, n, X);
    if (p.first == INT_MAX && p.second == INT_MAX)
        cout << "No pairs found\n";
    else
        cout << "The pairs are : " << p.first << ", " << p.second << endl;

    return 0;
}

Output:

Enter number of input elements, n
6
Enter the input elements
4 -1 6 5 -2 2
Enter sum, X
2
The pairs are : -2, 4