Data Structures and Algorithms — Two Pointers Technique
--
Two-pointers is a technique to solve array or string algorithm problems. It reduces time complexity to O(n) if you keep the work inside.
Basically, there are two integer variables which they could be called i and j or left and right which move along a loop.
If you are able to use the two-pointers technique, your algorithm will have never more than O(n) because two-pointers will keep the work inside a loop. (However, sometimes the time complexity is O(m+n) but we will investigate it later)
You might use either a while loop or for loop to manage pointers.
The concept is;
There are two variables which are one of those starts at 0-index, and the other one starts either at the end of the array or at 0-index.
int left=0;
int right=s.Length-1; // or int right=0;There is a while loop that iterates until either
One pointer is bigger than the other one
or
One of the pointers is less than and equal to the input array.
while(left < right) // while(right <= nums.Length - 1)The last part is you should put your logic in the while loop depending on your problem and manage your pointers
left++
right--
Both left++ and right --
The final code should be as below
int left=0;
int right=s.Length-1; // int right=0;
while(left < right) // while(right <= nums.Length - 1)
{
//your logic here
left++;
right--;
}This concept has a time complexity of O(n) and a space complexity of O(1).
Reverse String
We will use the two-pointers technique and one of those will start at the 0-index and one of those will start at the last index of the array.
int left=0;
int right=s.Length-1;Then we need a while loop to check each letter and swap them if necessary.
while(left < right)
{
char temp=s[left];
s[left] = s[right];
s[right]=temp;
left++;
right--;
}The code should be as below
int left=0;
int right=s.Length-1;
while(left < right)
{
char temp=s[left];
s[left] = s[right];
s[right]=temp;
left++;
right--;
}The code has a time complexity of O(n) and a space complexity of O(1).
Remove Duplicates from the Sorted Array
This problem could be solved using the two-pointers technique and the complexity will be O(n) because we will keep the solution in the while loop.
First, we need a counter and two variables in this problem to keep our process and calculate the indexes.
int left=0;
int right=0;
int counter=1;The counter is starting at one because we get the first element of the array all the time
Second, we need a while loop to proceed with our algorithm
while(right <= nums.Length - 1)Third, we implement our logic in the while loop
if(nums[left] == nums[right]) // 1
{
right++;
}
else // 2
{
left++;
nums[left] = nums[right];
counter++;
}When we look at the number 1;
We are checking the elements for left and right pointers and if they are equal then only we increase the right pointer because we use the right pointer as a runner and the left pointer as deciding the index.
When we look at the number 2,
if elements are not equal, swap them after the left is increased and increase the counter.
We increase the left pointer before swapping because we want to change the correct index. If you look at the number 1, you will see that we increase only the right pointer and keep the left stable when they are equal.
Lastly, return the counter.
return counter;All code should be as below
if(nums.Length == 0) return 0;
int left=0;
int right=0;
int counter=1;
while(right <= nums.Length - 1)
{
if(nums[left] == nums[right])
{
right++;
}
else
{
left++;
nums[left] = nums[right];
counter++;
}
}
return counter;Another concept is we have a loop and after the loop is done, we check two pointers to make sure they are exhausted.
Let’s check an example and understand the concept
Basically, we have been given two sorted arrays and we need to combine them into one array and they have to be sorted.
int[] array1 = { 1, 4, 7 };
int[] array2 = { 2, 3, 8, 9 };We need a new array and two pointers to compare the elements of given arrays
int[] resultArray = new int[m+n];
int index = 0;
int i = 0;
int j = 0;We need a while loop to check the arrays and sort them.
while (i < n && j < m)
{
if (arr1[i] < arr2[j])
{
resultArray[index++] = arr1[i++];
}
else
{
resultArray[index++] = arr2[j++];
}
}In this concept, we need to make sure that all pointers have been exhausted.
while (i < n)
{
resultArray[index++] = arr1[i++];
}
while (j < m)
{
resultArray[index++] = arr2[j++];
}It will have a time complexity of O(n+m) where n is the length of arr1 and m is the length of arr2 and the space complexity of O(n).
Median of Two Sorted Arrays
This question could be solved in different ways but we will use two pointers.
I will sort the array using the previous concept
double result=0;
int n=nums1.Length;
int m=nums2.Length;
int[] resultArray=new int[n+m];
int index=0;
int i=0;
int j=0;
while(i<n&j<m)
{
if(nums1[i] < nums2[j])
{
resultArray[index++] = nums1[i++];
}
else
{
resultArray[index++] = nums2[j++];
}
}
while(i<n)
{
resultArray[index++] = nums1[i++];
}
while(j<m)
{
resultArray[index++] = nums2[j++];
}The second part is totally math of calculating the median of an array
int length = m+n;
if(length % 2 ==1)
{
result=resultArray[length / 2];
}
else
{
result = ((double)resultArray[length / 2] + (double)resultArray[(length / 2)-1]) / 2;
}
return result;The final code should be as below
double result=0;
int n=nums1.Length;
int m=nums2.Length;
int[] resultArray=new int[n+m];
int index=0;
int i=0;
int j=0;
while(i<n&j<m)
{
if(nums1[i] < nums2[j])
{
resultArray[index++] = nums1[i++];
}
else
{
resultArray[index++] = nums2[j++];
}
}
while(i<n)
{
resultArray[index++] = nums1[i++];
}
while(j<m)
{
resultArray[index++] = nums2[j++];
}
int length = m+n;
if(length % 2 ==1)
{
result=resultArray[length / 2];
}
else
{
result = ((double)resultArray[length / 2] + (double)resultArray[(length / 2)-1]) / 2;
}
return result;This algorithm has a time complexity of O(n+m) where n is the length of nums1 and m is the length of nums2 and a space complexity of O(n).
Is Subsequence
We will solve the problem using the two-pointers technique and will be easy.
It says s has to be in t and they need to have the same sequence which is why we will create two variables one of them will store the index and the second one will check each letter of s.
After we are done with the loop, the left pointer has to be as same as the length of s.
If the left is not equal to the length of s it means s is not in t or the order is different.
int left=0;
int right=0;
while(left < s.Length && right < t.Length)
{
if(s[left] == t[right])
{
left++;
right++;
}
else
{
right++;
}
}
return left == s.Length;This algorithm has a time complexity of O(n) and a space complexity of O(1).
Container With Most Water
The question wants us to find and return the maximum amount of water a container can store which is why first we need to calculate the maximum area and then get rid of the shorter line for each iteration. This is how we approach this question to be able to solve it.
We will use Two-Pointer Technique which is why we will create 2 variables which are left and right. Also, we need one more variable which is the max that will store the max value.
int max=0;
int left=0;
int right=height.Length-1;The left will start at the 0-index, and the right will start at the last index of the height because the height array will be getting smaller for each iteration.
We need a while loop to check each item of the height array.
while(left < right)Now, we are able to access the heights. Then we need to find the minimum height because we do not want to spill the water.
int min = Math.Min(height[left],height[right]);After we find the min-height, we are ready to calculate the area
int maxArea = min * (right-left);Then, we need to update our max variable to keep the maximum value.
max = Math.Max(max,maxArea);The last process is that we need to check to see which one is shorter — left or right
if(height[left] <= height[right])
{
left++;
}
else
{
right--;
}All code should be like this
public int MaxArea(int[] height) {
int max=0;
int left=0;
int right=height.Length-1;
while(left < right)
{
int min = Math.Min(height[left],height[right]);
int maxArea = min * (right-left);
max = Math.Max(max,maxArea);
if(height[left] <= height[right])
{
left++;
}
else
{
right--;
}
}
return max;
}Time complexity is O(n) because we kept all work inside the loop. The space complexity is O(n).
I tried to explain how we use the two-pointers technique and how we implement it.
