“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.
What is a Pointer?
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 the size of the pointers in 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.
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
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 add 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.”
Efficient Approach: Using two pointers:
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 python code 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))
It’s a well-known TwoSum problem; let’s check it out on CodeStudio, 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.
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.
Visualize 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.
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.
Image Source: Github
Step 3. If both points meet at some point in the linked list, we have discovered a cycle. Otherwise, we’ll have to hit the end of the list, and there won’t be a cycle.
Below is the python code (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.
Let’s head onto CodeStudio and try to code for this problem.
When to use the two-pointer technique?
A two-pointer isn’t the answer to every problem. To employ the two-pointer technique, the following aspects must be recognized 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.
- Sum of Two Elements Equals the Third
- Move Zeros To Left
- Sort 0,1,2 array
- Last Substring In Lexicographical Order
- Remove Consecutive Duplicates From String
- The Celebrity Problem
- Count with K different characters
- Find All Triplets With Zero Sum
- Minimum subarray with the required sum
- Find Pair Sum in Rotated and Sorted array
This is not the end of the list; you can find more questions in the Two-Pointer tag on CodeStudio. Before reaching the end of our blog, let’s see some frequently asked questions related to two-pointer techniques.
Frequently Asked Questions
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.
The tortoise and hare approach (also known as the fast and slow pointer technique) uses two pointers to determine properties about directed data structures. An array, a single-linked list, or a graph can all be used.
The linked list can be reversed using two pointer techniques. Let’s solve the question Reverse Linked List and submit it to CodeStudio to see if it works.
No, not at all. The “two pointer technique” has a limited set of concepts. Furthermore, it is simple and easy to use.
On CodeStudio, you can practise and master everything from basic to all interview-related questions.
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 this Complete 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.
By Aanchal Tiwari