Stop Using Extra Arrays: Mastering the Two-Pointer Approach

In a two pointer approach we use two pointers which are pointing at two different or sometimes same locations in an array. For problems like move targeted element where we move target element at the front or end of the array or problem like remove duplicates where in sorted or unsorted array we remove the duplicate elements or move those elements at the end of the array can be approached or solved by the two pointer approach where the time complexity can be 0(n).

Let’s learn a two pointer approach by one example:- Remove duplicates from an array.

Problem statement:
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. [this is the problem from leetcode #26]

Consider the number of unique elements in nums to be k​​​​​​​​​​​​​​. After removing duplicates, return the number of unique elements k.

example:-
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]

The standard approach would be to loop through an array and add unique elements to a new array. But in that case time complexity remains O(n) but space complexity would grow to the size of an array O(n) too. In small arrays like 100 or even 1000 entries it won’t be much difference but what if the array size is in billion? Takes too much extra space right? Here is where the two pointer approach comes in.

Lets see How would we solve this problem with a two pointer approach?

I solved this problem using the 'Paper-First' method—a part of my daily routine to ensure my logic is peaceful and precise before I ever touch the keyboard.

Solution:

var removeDuplicates = function(nums) {
if (nums.length === 0) return 0;

// We start at 1 because the first element is always unique
let insertIndex = 1;


for (let i = 1; i < nums.length; i++) {
    // If current element is different from the previous unique one
    if (nums[i] !== nums[insertIndex - 1]) {
        nums[insertIndex] = nums[i];
        insertIndex++;
    }
}


return insertIndex;

};

Here,

Step-1: if (nums.length === 0) return 0; Handling the Edge Case.
The first edge case handles the empty array. If an array has no element then we return zero cause there is nothing to perform on.

Step-2: let insertIndex = 1;
Variable declaration: In our case this acts as a pointer (1st pointer) that we use to point to the desired index to perform swap operation.

Step-3: for (let i = 1; i < nums.length; i++) { … }; loop
In step - 3 we loop through an array and do changes in this array to save the extra space.
if (nums[i] !== nums[insertIndex - 1]) {
nums[insertIndex] = nums[i];
insertIndex++;
}

This is the most important part of the code. Where we put our logic. We check everytime that if the numsi is equal to the last element of insertIndex (-1)?
Without nums[insertIndex - 1] would throw an error on an empty array. Because we started the index from 1.

Example: - nums = [] // length is 0
So checking nums[insertIndex] = 1 array index out of Bound error.

If not then this is the unique element so we add the new element at the index of insertIndex. And increment the insertIndex so we add the next unique element at the next place of this operation.

Step-4: Return the last updated index: insterIndex
At the end we return the last updated index insertIndex which is pointing to the next point of the last added element.

Dry Run:

We can better understand this by dry running the code on the example array.

Example: [ 0, 0, 1, 1, 2 ]

Step
i (Explorer)
nums[i]
nums[insertIndex-1]
Comparison
Action
Array State
Start
1
0
0 (at index 0)
0 !== 0? No
Skip
[0, 0, 1, 1, 2]
Iter 1
2
1
0 (at index 0)
1 !== 0? Yes
nums[1] = 1; insertIndex++
[0, 1, 1, 1, 2]
Iter 2
3
1
1 (at index 1)
1 !== 1? No
Skip
[0, 1, 1, 1, 2]
Iter 3
4
2
1 (at index 1)
2 !== 1? Yes
nums[2] = 2; insertIndex++
[0, 1, 2, 1, 2]

Key Takeaway:
Time Complexity: O(n)
Space Complexity: O(1)
Best for: In-place modifications of sorted arrays.

Conclusion
So, the Two pointer Approach is a classic and easy to implement algorithm. In three steps we can implement this. 1st is return on an empty array, 2nd is defining the variable (pointer to 1 or 0 depending on the problem) 3rd would be to loop through it and check if the current element is unique to the last updated element? 4th return the last updated variable. simple and effective.

To check your knowledge? The Problem: Given an array of integers, move all the zeroes to the end of it while maintaining the relative order of the non-zero elements.
Example: [0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]
Constraint: You must do this in-place without making a copy of the array.