No history yet

Applications in Array Manipulation

Removing Duplicates from a Sorted Array

The two-pointer technique shines when you need to modify an array in-place. Consider a common problem: removing duplicate elements from a sorted array. The goal is to have each unique number appear only once and to return the new length of the modified array. You don't need to worry about the elements beyond the new length.

A brute-force approach might involve creating a new array, but that uses extra space. With two pointers, we can solve this efficiently using constant extra space, O(1)O(1).

We'll use a "slow" pointer to track the position for the next unique element and a "fast" pointer to scan the array for new elements.

Let's call the slow pointer write_idx and the fast pointer read_idx. Since the array is sorted, duplicates will be grouped together. The read_idx will iterate through the array, and whenever it finds an element different from the one before it, we know we've found a new unique element. We then copy this value to the position indicated by write_idx and advance write_idx.

The first element at index 0 is always unique by definition, so we can initialize write_idx to 1 and start our scan with read_idx from index 1.

#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    // write_idx points to where the next unique element should be placed.
    int write_idx = 1;

    // read_idx scans the array.
    for (int read_idx = 1; read_idx < nums.size(); ++read_idx) {
        // If the current element is different from the previous one...
        if (nums[read_idx] != nums[read_idx - 1]) {
            // ...it's a unique element. Place it at write_idx.
            nums[write_idx] = nums[read_idx];
            write_idx++;
        }
    }

    return write_idx; // The new length of the array.
}

Partitioning an Array

Partitioning is the process of rearranging an array around a chosen value, called a pivot. All elements smaller than the pivot are moved to its left, and all elements greater than or equal to it are moved to its right. This operation is the core of famous sorting algorithms like Quicksort.

We can achieve this with two pointers, left and right, starting at opposite ends of the array. The left pointer moves forward, looking for an element that is greater than or equal to the pivot. The right pointer moves backward, searching for an element that is smaller than the pivot. When both pointers find such elements, and left is still to the left of right, the two elements are swapped. This process continues until the pointers meet or cross, completing the partition.

#include <vector>
#include <utility> // For std::swap

void partitionArray(std::vector<int>& nums, int pivot) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        // Move left pointer while element is less than pivot
        while (left <= right && nums[left] < pivot) {
            left++;
        }

        // Move right pointer while element is greater than or equal to pivot
        while (left <= right && nums[right] >= pivot) {
            right--;
        }

        // If pointers haven't crossed, swap elements
        if (left < right) {
            std::swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }
}

Merging Two Sorted Arrays

Another classic application is merging two sorted arrays. A common variant of this problem asks you to merge a second sorted array (nums2) into a first sorted array (nums1), assuming nums1 has enough empty space at the end to accommodate all elements from nums2.

A naive approach might be to append nums2 to the end of nums1 and then sort the entire nums1 array. This is inefficient, with a time complexity of roughly O((m+n)log⁡(m+n))O((m+n) \log(m+n)), where mm and nn are the lengths of the arrays.

A better way uses three pointers. Instead of building the merged array from the beginning (which would require shifting elements in nums1 constantly), we can build it from the end. We place the largest elements first.

  1. A pointer p1 starts at the end of the initial elements in nums1.
  2. A pointer p2 starts at the end of nums2.
  3. A pointer write_idx starts at the very end of the allocated space in nums1.

We compare the elements at p1 and p2. The larger of the two is placed at the write_idx position, and both the write_idx and the pointer of the larger element are moved one step to the left. We repeat this until one of the arrays has been fully copied. If any elements remain in nums2, we copy them over.

Lesson image
#include <vector>

// m is the number of initialized elements in nums1
// n is the number of elements in nums2
void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
    int p1 = m - 1; // Pointer for last element of initial nums1
    int p2 = n - 1; // Pointer for last element of nums2
    int write_idx = m + n - 1; // Pointer for where to write in nums1

    // Iterate from the end and place the larger element
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[write_idx] = nums1[p1];
            p1--;
        } else {
            nums1[write_idx] = nums2[p2];
            p2--;
        }
        write_idx--;
    }

    // If there are remaining elements in nums2, copy them
    // (No need to handle remaining elements in nums1 as they are already in place)
    while (p2 >= 0) {
        nums1[write_idx] = nums2[p2];
        p2--;
        write_idx--;
    }
}

The elegance of the Two-Pointer Method lies in its in-place efficiency, allowing you to manipulate sequences without creating unnecessary copies.

In all these examples, the two-pointer technique provides a significant advantage. It allows for in-place modifications, which saves memory, and typically reduces the time complexity to a single pass, O(n)O(n), making it a powerful tool for array manipulation.

Quiz Questions 1/5

When removing duplicates from a sorted array using a 'write_idx' (slow) and 'read_idx' (fast) pointer, why is the 'write_idx' often initialized to 1?

Quiz Questions 2/5

What is the primary advantage of merging two sorted arrays (nums2 into nums1) from the end rather than the beginning, assuming nums1 has sufficient space?