In this blog post, I will be going through another pattern called Two Pointers or Iterators which is very important to understand for technical interviews.
This pattern is very useful to solve problems with sorted arrays (Linked Lists) which involve a set of pair elements, or a triplet or even a subarray. It is the use of two different pointers to solve a problem involving said indices with the benefit of saving time and space. Most of the problems involving these patterns can be solved in O(N) time complexity and O(1) or O(N) space complexity.
Why is Two Pointer technique effective?
In this pattern, we are able to process two elements per loop instead of just one.There are two pointers, one starting from the beginning and the other one starting at the end.
How to identify when to use Two Pointer pattern:
The different ways to identify if Two Pointer method is the right solution to the problem :
- The problem involve sorted arrays(Linked Lists), a set of pair elements, or a triplet or even a subarray.
- There is a target value to match or duplicates to be removed.
Some of the problems that feature the Two Pointer pattern:
- Squaring a sorted array ,
- Triplets that sum to zero ,
- Comparing strings that contain backspaces