Two Pointers Algorithm — Most Efficient Technique to Optimize Runtime
Hey all 👋,
In this article, we will discuss the most used algorithm which is the Two Pointers Algorithm.
Two Pointers algorithm is one of the most commonly asked questions in any Coding/Technical Interview. This approach helps in optimizing runtime to a great extent. It is generally applied on arrays and linked lists. This algorithm works in constant space.
Let’s discuss the working of two pointers algorithm –
In this technique, pointers represent either indexes or Node’s next attribute.
Steps in Two Pointer Algorithm –
1. Pointer Initialization — Pointers can be at any place depending upon what we are trying to achieve. In the left part of the pic, both pointers are starting at the same position. And in the right of the pic, we have pointers at extreme ends i.e. start index and end index of an array.
2. Pointer Movement — Depending upon what we are trying to do, pointers can move in the same direction (left part of pic) or they can move in the opposite direction (right part of pic). Also, in the left part of the pic, we have fast and slow pointers having different increments.
3. Termination Condition — This step decides when to stop. In the left part, the termination condition is to continue till we reach a node whose next attribute is NULL. In the right part, we continue till (start < end).
Note : Sliding Window is another variation of Two Pointers Algorithm.
We will discuss about Sliding Window in my next article. So, stay tuned for that 🙈.
Let's see how we can use the above logic to solve some problems 😃.
Problem 1 — Two Sum Problem
You are given an array people where people[i] is the weight of the ith person and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at the most limit.
Problem Link — https://leetcode.com/problems/boats-to-save-people/
The task is to return the minimum number of boats to carry every given person.
For example, if people = [1,2], limit = 3 then output would be 1.
Brute Force Approach –
The brute force solution would be to run through every possible pair of elements, a solution that runs in O(n²) time. We can run two nested loops and check for every possible pair. And of course, this is not an efficient and optimized approach.
Suppose you are giving an interview and after explaining the brute force solution, now the interviewer may ask you to optimize the solution 🤔. And we can do this using two pointers 🙌.
Optimized Approach –
First, we sort the array. Not all two-pointer problems require sorting. Next, we start the sum of extreme values (at the front and at the end) and conditionally move both left and right pointers. Because the array is sorted, this corresponds to the smallest and largest numbers, respectively.
For each step, we calculate the sum of the two numbers being pointed to. If the sum is less than the target, we increase the estimate by moving the left pointer one to the right. If our sum is larger than the target, we decrease the estimate by moving the right pointer one to the left.
If a solution is found, we can break and return the answer. On the other hand, if there is no solution, the left and right pointers will eventually point to the same number (in the middle). And here we met our termination condition.
Implementation in Java –
Time Complexity — O(n log n), where N is the size of an array
Log n is the runtime of the fastest sorting algorithms.
Space Complexity — O(1)
Problem 2 — Find Middle Node in Linked List.
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Problem Link — https://leetcode.com/problems/middle-of-the-linked-list/
Brute Force Approach –
First, we find the size of a linked list by traversing the list from start to end. Again, we traverse the list up to (size/2) starting from the 0th position. Then return the node which is our middle node.
Approach using Two Pointers –
We maintain two pointers starting from the head of the list. The first pointer will be a slow pointer which will move by one node and the second is a fast pointer which will move by 2 nodes. When the fast pointer reaches the end, the slow pointer will reach the middle of the linked list.
Implementation in Java –
Time Complexity — O(n), n is the number of nodes in the list
Space Complexity — O(1)
Some more problems based on Two Pointer Algorithm –
1. Identify palindromes within strings. For example, ‘abcdedc’ has the palindrome ‘cdedc’.
2. Find three numbers in an array that sum to zero. For instance, the solution for [-3, 2, 1, 7, 9] would be -3, 2, and 1.
3. Merge two sorted lists. Convert [1, 3, 4, 6] and [2, 4, 7, 7] into [1, 2, 3, 4, 6, 7, 7].
I’ll be back with some more exciting topics.
Till then Happy Coding!!! 😉
