Two Sum With Two Pointers – Interview Question Solution

Two sum with two pointers problem solving technique is a technique where two elements of a sorted array (a pair) must add up to a given target value.

Problem Statement

Given a sorted array of n integers and a target value, your task is to check if any pair of elements exists such that their sum is equal to the given target.

return 1, if any pair exists with the given target.
return 0, otherwise.

Example input 1

arr[] = {2,7,11,22,75}

target = 86

output: 1. This is because arr[2] + arr[4] equals 86, meaning there is a pair whose summation equals the target value 86

Example input 2

arr[] = {11,15,20,30,70}

target = 40

output: 0. This is because there is no pair whose summation equals the target value 40

Problem Statement Explained

So given a sorted array arr[] = {2,7,11,22,75} for example and a target value of 86, your task is to check if any pair exist such that the sum of the pair equals the target value. If the sum of any pair of elements of the array arr equals to the target value, return 1 otherwise return 0.

The brute-force Approach

So the brute-force approach or the baby programmer approach is implemented below in c

#include <stdio.h>

int main(){
    int arr[5] = {2,7,11,22,75};
    int sum;
    int i;
    int j;
    
    for(i=0; i<i+1; i++){
        for(j=i; j<4; j++){
            sum = arr[i] + arr[j + 1];
            if(sum == 86){
                return 1;
            }
        }
    }
    return 0;
}

• Create a double for loop, and outer loop and an inner loop
• The outer for loop picks the next i element of the array in each pass starting from the 1st element (i.e i = 0) and assigns it for use in the inner loop until the n – 1 element has been picked
• The inner loop takes the i element which is assigned to j (i.e j=i; in the for loop) and use it to retrieve the next element of the array (i.e the arr[j + 1] part of the code in the line sum = arr[i] + arr[j + 1]). This retrieved element is what is used in the summation of the i element (i.e arr[i]) and the sum is assigned to the variable sum.
• The next line of code does the comparison to check if sum is equal to the target value 86; if equal the program returns 1.
• Execution does not leave the inner loop in each pass until addition has been between the i element arr[i] and the next element to the i element arr[j + 1]
• Then control returns to the outer loop and the next element is picked and handed over to the inner loop for repetition of the same process.

The Problem With This Code

Time Complexity

What is time complexity? Simply put, it is the time that your function takes to complete execution as the size of input for your function grows.

Large input can be a problem for baby programmers to handle efficiently in their codes and informed employers know this; so if you say you want employment in their organization, one of the things they like to interview you for is how your code handles large input – basically how much time (time complexity) and how much memory (space complexity) it will take your code to finish execution of whatever it is asked to do.

Every time you implement a loop in your code that has to loop the given input (array, list etc) n times to achieve its purpose, just know that as the input size increases your code will take a longer time to finish executing and may even crash – this is the reason senior developers talk about data structure and algorithms.

In our code example, the outer for loop has to loop the input n times, the inner for loop also has to loop the input n times – n is the number of elements in the array. In summary our code has to loop the given input n * n times which gives n² times (or what bigO calls quadratic time).

So the problem with our code above is that it is bigO of n² which is unacceptable given large input size.

You know for our particular situation, we might not have a noticeable problem; but think about it, what if our array size increases to say 100,000 elements; how long will it take our double for loop to finish looping 100000² elements? Will the application user be happy waiting endlessly for a particular action to finish so that he/she can continue using our application? If it takes 45mins (depending on other factors like computer speed) to finish that particular looping, can you say that our application is efficient? Now you are beginning to understand the issue i believe.

If all this thing about bigO notation and time complexity is completely strange to you, you may want to go look at cs dojo YouTube video on Introduction to Big O Notation and Time Complexity after now.

And if you are a beginner to Data Structure and Algorithm, i recommend learning from these guys: log2base2. I prefer you choose their course called Problem Solving With DSA; this should allow you have practice time from the interview question under problem solving. All their lectures are animated videos and their problem solving practices includes hints in case you get stuck. Please note that the link is my affiliate link with them and i will be paid a commission if you buy a course from them using that link at no extra cost to you. It is my reward for introducing them to you.

Two Pointer Technique – A More Efficient Approach

Hint

• They array has to be sorted
• We are to find a pair whose sum equals the given target.
• So we will first of all initialize two pointers, one for the starting index and the other for the last index.

• Find the sum of the values of the start and end pointer indices, if sum equals to target value, return 1; otherwise check whether sum is less than or greater than the given target. If less than the given target, move the start pointer by 1 place otherwise if greater than, move the end pointer by 1 place.
• Start the process all over again until either you find the given target or return 0 if target value not in given input.

One thing you should spot from the diagram above by now is that since the array is sorted, if after finding the sum of the value of the start pointer index and the end pointer index and the sum is less than the target value, the only way to get closer to our target value then is by moving the start pointer by 1 place. Same goes for if the sum of start pointer index value and end pointer index value is greater than target value; the only way to get closet to the target value is to move the end pointer by 1 place.

Given our first input for example:

• We begin with start pointer index value == 2 and end pointer index value == 75, sum == 77. 77 is less than 86, so we increment our start pointer index by 1 place to index position 1 having value == 7
• So now start pointer index value == 7 and end pointer index value == 75, sum == 82. 82 is less than 86, so we increment our start pointer index by 1 place to index position 2 having value == 11
• Now start pointer index value == 11 and end pointer index value == 75, sum == 86. 86 is equal to our target value, so we return 1 and end program execution

Solution

The solution is implemented in c but the algorithm can be implemented in any language of your choice.

int Two_Sum_With_Two_Pointers(int arr[], int n, int target)
{
    int start_pointer = 0;
    int end_pointer = n - 1;
    
    while(start_pointer < end_pointer){
        int sum = arr[start_pointer] + arr[end_pointer];
        if(sum == target)
            return 1;
        if(sum < target)
            start_pointer++;
        else
            end_pointer--;
    }
    return 0;
}

Conclusion

Our solution runs in O(n) or linear time and is far more time efficient than the brute-force approach that runs in O(n²) or quadratic time. See big-o cheat sheet to see difference between O(n) and O(n²).