ALL YOU NEED TO KNOW ABOUT 3 SUM & THE 2 POINTER TECHNIQUE

The two-pointers approach is one of the important parts of a programmer’s toolkit. You may be wondering why?

It is because this problem is often asked in every technical interview!

Well, the name completely justifies the method. This method employs two pointers which ultimately saves space and time. Here, you can understand pointers as the indexes of the given array. 

Like binary search, this algorithm is also used for optimization purposes. Binary search is an optimization technique to reduce the number of trials required to get the desired result. 

In the same way, the two-pointer approach checks two different parts of an array simultaneously to get the desired results faster.

The two-pointer approach is used to resolve different advanced problems like the 3sum problem, reverse an array, and more. 

Here, in this post, we are going to discuss 3 sum problem and the 2-pointer technique in detail. 

In a 3-sum problem, you will be given an array and a target. In the array, you will have to look for such Three elements whose sum is equal to the given target.

Let’s consider the following example to understand this problem better:

Input:

Array= {1, 2, 3,5 ,6 11, 15, 16, 17, 18}

Sum= 20

Output:

True

[1, 3, 16]

Explanation:

In the given array, three elements i.e, 1, 3, and 16 can be added to achieve the given target of 20.

HOW TO FIX A 3-SUM PROBLEM?

There are three methods that you can use to fix the 3-sum problem. Here’s a glimpse of all three methods:

• Brute Force Method.
• Recursive Method.
• Hashing Method.

Check out below how these methods work -

• Brute Force Method: In this method, 3 nested loops are used to consider every triplet. These loops will find the desired sum of the triplets.
• Recursive Method: In this method, in each recursion, we consider the current element or ignore it. Recur the same thing for all the remaining items. Now, check if the target sum is found it will return True otherwise it will return false.
• Hashing Method: This is the most efficient approach to finding the 3-sum. In this approach, we will store each element of the array in the map with its respective index. We will then consider each pair and then check if the map has the sum of the remaining elements or not. In case the index of the remaining is not overlapping, you need to return true otherwise return false.

In the same way, the two-pointer technique is used. But you can not use it to resolve the 3 sum problem. 

Are you wondering why? Let’s discuss the two-pointers approach first. 

WHAT IS A TWO-POINTER TECHNIQUE

The two-pointer approach is the easiest and most effective technique that is used to search for pairs in a sorted array.

In this approach, you will be given a sorted array that has N integers. You need to find if there is any such pair exists such that the sum of the elements is equal to X. 

In this approach, we will consider two pointers; one of the pointers will represent the first element and the other one will represent the last element of the given array. Both these pointers are then assigned values. 

In case the sum of these pointers is smaller than X, we will have to shift the pointer present on the left side to the right side. However, if the sum is greater than X, we will have to shift the pointer present on the right side to the left side.

Now, in the same way, keep moving until you get the sum equal to X. 

Read More