Two-Pointer Techniques for In-Place Array Manipulation

1. The Two-Pointer Technique: A Core Algorithmic Pattern

The "two-pointer" technique is a common strategy for optimizing problems involving arrays or lists. Instead of using nested loops, which often lead to $O(n^2)$ time complexity, this technique uses two pointers that traverse the data structure together to solve the problem in a single pass, typically achieving $O(n)$ time and $O(1)$ space complexity.

The pointers can move in various ways:

• Converging: Pointers start at opposite ends of the array and move toward each other.
• Parallel (or Sliding Window): Pointers start at or near the beginning and move in the same direction, often maintaining a "window" or specific distance between them.

The following video provides an excellent overview of these strategies.

As the video explains, this pattern is particularly effective for problems involving sorted arrays or when you need to process elements from both ends of an array simultaneously.

Now, let's apply this pattern to two classic array manipulation problems.

2. Algorithm 1: In-Place Array Reversal

Our first task is to reverse the elements of an array without using any additional arrays. This is a perfect showcase for the converging two-pointer technique.

The Logic:

1. Initialize two pointers: left at the first element (index 0) and right at the last element (index size - 1).
2. In a loop, swap the elements at the left and right pointers.
3. After the swap, move the left pointer one step to the right (left++) and the right pointer one step to the left (right--).
4. Continue this process until the pointers meet or cross each other (while (left < right)).

This ensures that we only perform $\frac{n}{2}$ swaps, resulting in a complete reversal of the array. The following resource provides a clear walkthrough.

Here is a C implementation of the algorithm.

#include <stdio.h>

// A utility function to swap two integers
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to reverse an array in-place using the two-pointer technique
void reverseArray(int arr[], int size) {
    int* left = arr; // Pointer to the first element
    int* right = arr + size - 1; // Pointer to the last element

    while (left < right) {
        // Swap the values pointed to by left and right
        swap(left, right);

        // Move pointers toward the center
        left++;
        right--;
    }
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    reverseArray(arr, n);

    printf("Reversed array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

// Expected Output:
// Original array: 10 20 30 40 50 60 
// Reversed array: 60 50 40 30 20 10 

Notice how we use actual pointers (left and right) and pointer arithmetic (arr + size - 1, left++, right--). This is a direct and efficient way to implement this algorithm in C.

3. Algorithm 2: In-Place Array Partitioning

Partitioning involves reorganizing an array's elements based on some property. The two-pointer technique is exceptionally well-suited for this. A famous and practical example is the Dutch National Flag problem.

The Problem: You are given an array containing only 0s, 1s, and 2s. Your task is to sort this array in-place, with all 0s first, followed by all 1s, and finally all 2s.

This problem is a staple in interviews and is an elegant extension of the two-pointer pattern, often using three pointers.

The Logic:
We use three pointers: low, mid, and high.

• low points to the boundary where 0s should end.
• mid points to the current element being examined.
• high points to the boundary where 2s should begin.

Initially, low and mid are at index 0, and high is at size - 1. We iterate as long as mid <= high.

1. If arr[mid] is 0: Swap arr[low] with arr[mid]. Increment both low and mid.
2. If arr[mid] is 1: The element is in the correct partition. Just increment mid.
3. If arr[mid] is 2: Swap arr[mid] with arr[high]. Decrement high. Do not increment mid because the element you just swapped into the mid position is unknown and needs to be processed.

The following resources provide a deep dive into this algorithm.

Now that you have the concept, let's look at a detailed implementation.

The C code you just studied is a model of efficiency. It sorts the array in a single pass (O(n)) using only a constant amount of extra memory (O(1)) for the pointers. This is precisely the kind of solution valued in high-performance and resource-constrained programming.

Conclusion

In this lesson, we've generalized the two-pointer technique and applied it to solve common array-based problems with optimal efficiency. You've seen how this single pattern can be adapted for both simple reversal and complex multi-way partitioning.

Key Takeaways:

• The two-pointer technique is a powerful pattern for solving array and list problems in $O(n)$ time and $O(1)$ space.
• Converging pointers, starting from opposite ends, are ideal for tasks like in-place reversal and partitioning.
• For array reversal, we swap elements at left and right pointers and move them inwards until they meet.
• The Dutch National Flag problem is a classic partitioning algorithm that uses a low, mid, and high pointer to sort three unique elements in a single pass.
• In-place algorithms are critical for memory-constrained environments, making this technique highly relevant to your work in embedded systems.

Preview of the Next Lesson

We will continue to hone our pointer skills by applying them to another fundamental C data type. In our next lesson, we will re-implement standard string functions (e.g., strcpy, strstr) using pointer arithmetic. This will reinforce your understanding of C-style strings as null-terminated character arrays and give you more practice with direct memory manipulation.