Introduction to Two Pointers

🧠 What Are Two Pointers?

Two-pointer technique uses two indices to traverse a linear structure like an array or linked list. Compared to nested loops (O(n²)), it often brings down complexity to O(n).

🚀 Why It Works

If the structure has predictable dynamics, like a sorted array or a palindromic string, you can move pointers intelligently rather than checking every possible pair.

🔍 Strategies

1. Inward Traversal

Start from both ends and move inward.

Use case: Check if a string is a palindrome

bool IsPalindrome(string s) {
    int left = 0, right = s.Length - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

2. Unidirectional Traversal

Both pointers start on the same end and move forward.

Use case: Remove duplicates from sorted array

int RemoveDuplicates(int[] nums) {
    if (nums.Length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.Length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

3. Staged Traversal

Second pointer moves after the first satisfies a condition.

Use case: Find max length subarray with sum ≤ k

int MaxSubArrayLen(int[] nums, int k) {
    int left = 0, sum = 0, maxLen = 0;
    for (int right = 0; right < nums.Length; right++) {
        sum += nums[right];
        while (sum > k) {
            sum -= nums[left];
            left++;
        }
        maxLen = Math.Max(maxLen, right - left + 1);
    }
    return maxLen;
}

🛠️ Real-World Example: Memory Compaction

In garbage collection, compaction is used to eliminate gaps left by dead objects and free up continuous memory.

Two pointers:

scan walks through the heap
free marks the next available free space

As scan finds live objects, they’re moved to the free position.

Here’s a simplified simulation:

void CompactMemory(List<Object> heap) {
    int free = 0;
    for (int scan = 0; scan < heap.Count; scan++) {
        if (heap[scan].IsAlive) {
            if (free != scan) {
                heap[free] = heap[scan]; // Move live object
            }
            free++;
        }
    }

    // Nullify remaining space (optional cleanup)
    for (int i = free; i < heap.Count; i++) {
        heap[i] = null;
    }
}

In this code, heap is a list of objects. Dead (deallocated) objects are skipped. Live ones are packed to the front, minimizing fragmentation.