Solving Two Pointers Coding Problems

Coding problems using two pointers technique

Photo by Jefferson Santos on Unsplash

In this article, I am going to explain how we can utilize the two-pointer technique to solve coding problems

Two Pointers in Quick Sort

Every developer must have heard what Quick Sort is, here is the standard implementation using C++.

// use first element as pivot
int partition(int arr[], int left, int right){
    int pi = arr[left];
    int i = left + 1;
    for (int j = left + 1; j <= right; j++){
        if (arr[j] < pi)
            swap(arr[j], arr[i++]);
    }
    swap(arr[left], arr[i-1]);
    return i-1;
}
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
}

Explanation

The partition function does the following things:

• Use the value of the first element of the specified range as the pivot.
• Move the elements whose values are less than pivot to the left side of the pivot and those the values are greater than pivot to the right side of the pivot. The left part and the right part may not be sorted.
• Return the index of the pivot after the movement

j is used to iterate through the array between [left + 1, right], The values whose indices are less than i are always less than the pivot. So, i — 1 is the last element whose value is less than the pivot. If we were to choose right as the pivot, we can initialize i = j = right — 1 , and swap the values with the following:

if (arr[j] > pi) 
    swap(arr[j], arr[i--]);
swap(arr[right], arr[i+1]);
return i+1;

partition

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Example

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Code

// code 1
void sortColors(vector<int>& nums) {
    int red = 0, blue = (int)nums.size()-1;
    for(int i = 0; i <= blue; i++){
        if(nums[i] == 0)
            swap(nums[i], nums[red++]);
        else if(nums[i] == 2)
            swap(nums[i--], nums[blue--]);
    }
}
// code 2. Use while and another pointer cur, same logic as code 1
void sortColors(vector<int>& nums) {
    int left = 0, right = (int)nums.size() - 1, cur = 0;
    while (cur <= right) {
        if (nums[cur] == 0) {
            swap(nums[cur++], nums[left++]);
        } else if (nums[cur] == 2) {
            swap(nums[cur], nums[right--]);
        } else { //1
            ++cur;
        }
    }
}

Explanation

• blue always points to positions where 2 will be placed and red points to positions where 0 will be placed.
• When 0 is found, we swap and increase red and i.
• When 2 is found, swap and decrease blue and i, as the value of blue might be 0, and we have to check this position again (don't increase i ).
• When 1 is found, just increase i.