Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

“The most effective techniques are those that are simple and well-executed,” in Data Structures and Algorithms, the two pointer technique is one of them.

Two Pointers is a pattern in which two pointers iterate across the Data Structure until one or both of them satisfy the necessary condition.

Don’t worry; the "two pointer technique" has a limited set of concepts. Furthermore, it is a simple and effective technique that, when used correctly, works wonders.

As a result, a lot of interviews tend to be a little biased to questions using this technique. In this article, we'll go over the fundamental concepts and provide various examples, so you know when and how to apply the two-pointer strategy.

Two pointer approach is exactly what it sounds like. We use two pointers to get a certain task done.

A pointer is a reference to an object. That object stores a memory address of another value located in computer memory, or in some cases, that of memory-mapped computer hardware. Speaking in simpler terms - a variable storing the address to an array is also a pointer. For Example, we have calculated thesize of the pointersin the C program.

Questioning how pointer and two-pointer techniques are comparable?

Pointers store addresses of objects, and we will use this fact to point to various objects using variables in the two-pointer technique. Thus, in this case, they are also referred to as pointers.

Two pointer technique is nothing more than a clever optimization of specific brute-force techniques. It reduces the time complexity by using some type of order rather than necessarily sorting the data.

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

How to use the two pointer technique?

Before we begin, keep in mind that pointers in this technique represent either an index or an iteration attribute, such as the node's next.

Let’s get started with a few of the most famous examples, which can be solved optimally using the two pointer technique:

Example 1:Given a sorted array A ( sorted in ascending order ) and an integer target,find if there exists 2 integers A[i] and A[j] such that A[i] + A[j] = target, where i!=j.

For a given array A, suppose the target value=6

Brute-Force:

The brute-force solution would be implementing a nested loop that searches for all possible pairs of elements and adds them. Return True if any pair of elements adds up to the target.

# Naive solution to find if there is a
# pair in A[0..N-1] with given sum.
def isPairSum(A, N, target):
for i in range(N):
for j in range(N):
# as equal i and j means same element
if(i == j):
continue
# pair exists
if (A[i] + A[j] == target):
return True
# No pair found with given sum
return 0
# Driver code
arr = [1,2,3,4,6]
target = 6
print(isPairSum(arr, len(arr), target))

Time Complexity: O(n^2) where n is the length of an array.

Let’s brainstorm and reduce its time complexity using an efficient approach.

If we observe we haven’t used the fact- ”array is sorted ”.

We can use that to our advantage and use the property of the sorted array: “If we have to find a smaller element move to the left and likewise for greater elements we should move to the right.”

Let's initialise two variables, pointer1 and pointer2, and consider them as our two pointers.

Set pointer1 to 0 index and pointer2 to len(A)-1

These correspond to the smallest and greatest integers, respectively, because the array is sorted.

Compute the sum of the two numbers pointed to at each step.

If the sum is greater than the target, we need to reduce the estimate by moving the right pointer, i.e. pointer2, to the left.

On the other hand, if the sum is less than the target, we need to increase the estimate by moving the left pointer, i.e. pointer1, to the right.

And how will it benefit? The array is sorted, so as the index increases, the value on that index will also increase. Thus, this brings the estimate closer to the target value.

We can break and return the answer if a solution is found. If there is no answer, the left and right pointers will finally point to the same number, indicating that all possibilities have been exhausted.

The fact that the list was sorted is why we are confident that we've explored all of the possibilities in linear runtime O(N).

Below is the pythoncode to show how it looks when the above approach is put together:

# Two pointer technique based solution to find
# if there is a pair in A[0..N-1] with a given sum.
def isPairSum(A, N, target):
# represents the first pointer
pointer1 = 0
# represents second pointer
pointer2 = N - 1
while(pointer1 < pointer2):
# If we find a pair
if (A[pointer1] + A[pointer2] == target):
return True
# If sum of elements at current
# pointers is less, we move towards
# higher values by doing pointer += 1
elif(A[pointer1] + A[pointer2] < target):
pointer1 += 1
# If sum of elements at current
# pointer is more, we move towards
# lower values by doing pointer2 -= 1
else:
pointer2 -= 1
return False
# Driver Code
arr = [1,2,3,4,6]
# value to search
target = 6
print(isPairSum(arr, len(arr), target))

Output:

True

It's a well-known TwoSum problem; let's check it out on Coding Ninjas Studio, and let’s get our solution accepted.

In addition to the previous example, the two pointer technique can also involve the idea of using fast and slow pointers.

Let’s see how in Example 2.

Example 2:

Given the head of a linked list, the task is to determine if the linked list has a cycle in it. There is a cycle in a linked list if some node in the list can be reached again by continuously following the next pointer.

Visualise two runners running on a circular track. Both have different speeds.

You can see how a fast pointer or, say, a fast runner catches the slow runner after a certain time. Thus It is undeniable that both runners would meet at a certain point.

Using the same fact, we are going to solve this problem. Let’s get started.

Step 1. Initialise two pointers - slow and fast pointers to the head of the linked list.

slow=head
fast=head

Step 2. The idea is to move the fast pointer twice as quickly as the slow pointer, so the distance between them increases by one at each step.

Step 3. If both points meet at some point in the linked list, we have discovered a cycle. Otherwise, we'll have hit the end of the list, and there won't be a cycle.

Below is the pythoncode (detectCycleInLinkedList(head)) to show how it looks when the above approach is put together:

def detectCycleInLinkedList(head):
#Initialise slow and fast
slow = head
fast = head
while(fast and fast.next):
slow = slow.next
fast = fast.next.next
if slow == fast:
return True #cycle found
return False #No cycle found

Time Complexity: O(N), where N is the number of nodes in the Linked List.

The fast and slow pointer (also known as the tortoise and hare approach) is quite a famous two-pointer technique used to determine properties about directed data structures: an array, a single-linked list, or a graph all be used.

To employ the two-pointer technique, the following aspects must be recognised or verified:

Is it necessary to sort the array before initialising the pointers?

For example: In the above TwoSum problem, if the array was unsorted, we would be unable to determine which direction pointers should be moved.

Is it necessary for pointers to move at various speeds?

Using the fast and slow pointer techniques in the Detecting cycle in Linked List, we demonstrated how moving pointers at different speeds help us depending on the problem.

Is it possible to reduce a three-pointer problem to multiple two-pointer problems if managing three or more pointers is impossible or extremely difficult?

Yes, we can do that. Consider the problem Triplets with a Given Sum. Learn how to reduce the three-pointers problem to multiple two-pointer problems in this problem.

If the problem requires it, how should relationships between three or more pointers be managed?

This would vary from problem to problem. Using the two pointer approach, we can update the pointer in any necessary way.

Should pointers be updated one by one or all at once?;

Depends on the requirements of the problem.

Brainstorm these questions before approaching a two-pointer problem.

Eventually, you will ascertain that using and constructing two-pointer solutions to an array, string, and LinkedList search is straightforward and can be incredibly fast.

Additional Problems to master the two pointer technique

Very frequently, problems related to the two pointer technique are asked during interviews.

If this is your first time discovering this technique or preparing for an interview, we recommend that you practice the additional problems listed below on your own to master two pointer techniques. Practice like a Champion.

This is not the end of the list; you can find more questions in the Two-Pointer tag on Coding Ninjas Studio. Before reaching the end of our blog, let’s see some frequently asked questions related to two pointer techniques.

Frequently Asked Questions

What is the two pointer technique?

The Two Pointer technique is a pattern in which two pointers iterate across the data structure until one or both of them satisfy the necessary condition.

Where can I practice two pointer problems?

On Coding Ninjas Studio, you can practise and master everything from basic to all interview-related questions.

What is 2 pointer approach in linked list?

We use two pointers in this method to navigate the linked list. One pointer receives a one-digit increment, while the other receives a two-digit increment. After some time, the Slow pointer will be in the middle of the linked list when the fast pointer reaches the end.

What are the two types of pointers?

The two types of pointers in two pointer approach are slow and fast pointers. Another variation to this problem is when the first pointer begins at the beginning while the second pointer begins at the end. They move until they meet.

When can we use two pointer technique?

The two-pointer technique is frequently applied to effectively solve array problems. It is a search method that compares elements referenced by two pointers and updates them as necessary to solve problems involving collections such as arrays and lists.

Conclusion

This blog covered the fundamental concepts along with various examples related to two pointer techniques. It also highlights the aspects that describe how and when to employ the two pointer technique.

Whoops! We missed the fact that the "two pointer technique" is widely used in Competitive Programming as well.

Do you know about Competitive Programming and its perks? If not, don’t worry!

Competitive programming is a fun sport that involves problem-solving for the rush of finding excellent and elegant solutions to problems. It is also a valuable skill if you look forward to working at big tech giants like Google, Microsoft, Amazon, etc.

So, what are you waiting for? Jump right in and ace your dream companies and master competitive coding right now with thisComplete Competitive Coding Roadmap

Or explore the Preparation Guide to Competitive Programming for Free. If you're already a competitive programmer, you should read Ankush Singla's Roadmap To Become A 5 Star Coder|CodeChef.