How the Two-Pointer Technique Solves Array Problems More Efficiently

The two-pointer technique reduces array manipulation time complexity from O(n²) to O(n) by using fast and slow indices to perform the work of two nested loops in a single pass, eliminating expensive element-shifting operations.

The youngyangyang04/leetcode-master repository provides a comprehensive guide demonstrating how the two-pointer technique (also called fast-slow pointer) transforms brute-force array solutions into optimal linear-time algorithms. According to the source files problems/数组总结篇.md and problems/双指针总结.md, this method replaces nested iteration with dual indices that traverse the array simultaneously, performing in-place overwrites that require zero extra memory allocation.

Why Brute-Force Approaches Fall Short

When removing or rearranging elements in an array, naive implementations typically use two nested loops:

• The outer loop scans each element to identify targets for removal
• The inner loop shifts all remaining elements to fill the gap left by each deletion

Because each removal may shift up to n elements, the total work becomes ∑_{i=1}^{n} i = O(n²). The guide illustrates this inefficiency in problems/0027.移除元素.md, where the brute-force implementation moves the tail of the array every time a target value is found, resulting in quadratic time complexity.

How the Two-Pointer Technique Works

The technique defines two indices—a fast pointer and a slow pointer—that traverse the array in a single loop. As documented in problems/数组总结篇.md (lines 76-84):

“双指针法（快慢指针法）：通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作。”

The Fast and Slow Pointer Strategy

1. Initialize slow at index 0 to mark the position for the next valid element
2. Advance fast through every index from 0 to n-1
3. When nums[fast] is acceptable (e.g., not equal to the target value or non-zero), copy it to nums[slow] and increment slow
4. After completion, the subarray nums[0...slow-1] contains the result; remaining positions can be filled with default values if needed

Because each element is visited exactly once, the algorithm completes in linear time.

Complexity Analysis

• Time Complexity: O(n) – single pass through the array
• Space Complexity: O(1) – only two integer indices required, no additional data structures

Implementation Examples from leetcode-master

Remove Element (C++)

The file problems/0027.移除元素.md implements the technique to remove all instances of a value in-place:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); ++fast) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

This implementation avoids the O(n²) cost of shifting elements after each deletion by overwriting positions in a single traversal.

Move Zeroes (JavaScript)

The solution in problems/0283.移动零.md uses the same pattern to push all zeroes to the end while maintaining non-zero element order:

var moveZeroes = function(nums) {
    let slow = 0;
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            nums[slow++] = nums[fast];
        }
    }
    for (let i = slow; i < nums.length; i++) {
        nums[i] = 0;
    }
};

The first loop compacts non-zero elements to the front in O(n) time, while the second loop fills the remaining positions with zeroes.

Move Zeroes (Python Swap Version)

An alternative in-place swap approach from the same file reduces write operations:

def moveZeroes(self, nums: List[int]) -> None:
    slow, fast = 0, 0
    while fast < len(nums):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[fast]
            slow += 1
        fast += 1

This variant also maintains O(n) time complexity while potentially reducing memory writes compared to the copy-then-fill approach.

Summary

• The two-pointer technique replaces O(n²) nested loops with O(n) single-pass algorithms by eliminating repetitive element shifting
• Fast and slow pointers perform in-place overwrites according to problems/双指针总结.md, keeping the desired subsequence at the array's front
• The method applies to classic problems documented in problems/0027.移除元素.md and problems/0283.移动零.md, including element removal and array partitioning
• O(1) space complexity makes this ideal for memory-constrained environments where additional arrays cannot be allocated

Frequently Asked Questions

What is the two-pointer technique?

The two-pointer technique is an algorithmic pattern that uses two indices (typically a fast pointer and a slow pointer) to traverse an array simultaneously. According to problems/数组总结篇.md, it completes the work of two nested loops within a single iteration, reducing time complexity while maintaining O(1) space usage.

When should I use fast and slow pointers?

Use this technique when you need to remove elements, rearrange arrays, or find subsequences without allocating extra memory. The guide in problems/双指针总结.md specifically recommends it for problems involving element deletion (like remove element) and array compaction (like move zeroes) where the relative order of valid elements must be preserved.

Does the two-pointer technique only work on sorted arrays?

No, the fast-slow pointer variant works on unsorted arrays for in-place filtering and rearrangement. While some two-pointer patterns (like left-right pointers) require sorted data for searching, the technique demonstrated in problems/0027.移除元素.md processes elements sequentially regardless of input order, making it suitable for arbitrary arrays.

What is the space complexity of the two-pointer approach?

The two-pointer approach uses O(1) auxiliary space. As shown in the implementations within problems/0283.移动零.md, only two integer variables (indices) are required regardless of input size, enabling in-place modification without additional data structures.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}