Beginner Problem Solving Patterns Part 3
In the previous article, I wrote a blog regarding a little bit of an advanced problem-solving pattern, “divide and conquer.” This time I am going to introduce multiple pointers (known as two-pointers) problem-solving patterns.
Two Pointers
The idea of two pointers is usually creating pointers or values that correspond to an index or position and move towards the beginning, end, or middle based on a specific condition. It is an important technique to know due to optimal and efficient solutions for solving minimal space complexity problems. Let’s jump into an example for two pointers problem-solving patterns so that we can visualize it.
Example:
Before we dive deeper into the problem, we know that the array is sorted; if it’s not sorted, the way we solve it is probably inefficient. However, the situation indicates a sorted array, and because it is a sorted array, we know that the small number would be on the left side, and the large number would be on the right side index of the array. From this investigation, we could use two pointers techniques to solve the problem efficiently.
The naive approach
The brute force naive approach of this problem is having two for loops and checking every possible index that sum is equal to zero. The problem with this, the time complexity is O(N²); if there are a million numbers in the array, the code will run forever.
The better approach
The better way to approach this problem is to use two pointers, where one starts at the beginning of the index array, and the other starts at the end of the index array. Sum them both and check if the sum is equal to zero then we find our answer, else if the sum is greater than zero, we decrement the end of the index by one, else if the sum is less than a zero, we increment the start index by one and go on until the start index is greater than the end of the index.
The time complexity with two pointers is linear O(N) is much more efficient than brute force solution O(N²).
There are many ways to solve this problem, but two pointers are traditional ways to solve it. So there you go! That is ‘two pointers’ problem-solving patterns — one last one for the beginner problem-solving pattern journey. Stay tuned!