Two Pointers Technique in Data Structures

What is the Two Pointers Technique?

The Two Pointers technique is an algorithmic pattern where two index variables (pointers) are used to traverse a linear data structure — usually an array, string, or linked list — simultaneously.

By strategically moving these pointers closer together, further apart, or at different speeds, you can search, compare, swap, and partition data in a single O(N) pass instead of the O(N²) time that nested loops would require.

The technique is deceptively simple but solves a surprisingly wide range of interview problems with elegant efficiency.

When to Use Two Pointers

Look for these signals in a problem:

• Keywords: sorted array, pair with target sum, palindrome, reverse, remove duplicates, merge
• You need to find pairs, triplets, or ranges satisfying a condition
• The brute force solution requires nested loops: for i → for j
• The data structure is linear (array, string, linked list)

Pattern 1: Opposite Ends (Head & Tail)

Both pointers start at the two opposite ends of the array (left = 0, right = n-1) and move toward each other until they meet.

This effectively halves the search space on each step.

Example 1: Two Sum II (Sorted Array)

Find two numbers in a sorted array that sum to a target:

JavaScript:

javascript
function twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];

        if (sum === target) {
            return [left + 1, right + 1];   // 1-indexed result
        } else if (sum < target) {
            left++;    // Sum too small → move left pointer right
        } else {
            right--;   // Sum too large → move right pointer left
        }
    }

    return [-1, -1];  // No pair found
}

console.log(twoSum([2, 7, 11, 15], 9));  // Output: [1, 2]

Python:

python
def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return [-1, -1]

Visual Trace:

Array: [2,  7, 11, 15],  Target = 9
        L               R   → sum = 2+15 = 17 > 9, move right left
        L           R       → sum = 2+11 = 13 > 9, move right left
        L       R           → sum = 2+7  = 9  == 9, FOUND! return [1,2]

Example 2: Valid Palindrome

Check if a string is a valid palindrome (ignore non-alphanumeric, case-insensitive):

javascript
function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        // Skip non-alphanumeric characters from left
        while (left < right && !isAlphanumeric(s[left])) left++;
        // Skip non-alphanumeric characters from right
        while (left < right && !isAlphanumeric(s[right])) right--;

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

function isAlphanumeric(c) {
    return /[a-zA-Z0-9]/.test(c);
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car"));                      // false

Example 3: Reverse an Array In-Place

javascript
function reverseArray(arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];  // Swap
        left++;
        right--;
    }
    return arr;
}

console.log(reverseArray([1, 2, 3, 4, 5])); // [5, 4, 3, 2, 1]

Example 4: Container With Most Water

Given heights of vertical lines, find two that together with the x-axis forms a container holding the most water:

javascript
function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxWater = 0;

    while (left < right) {
        const width = right - left;
        const h = Math.min(height[left], height[right]);
        maxWater = Math.max(maxWater, width * h);

        // Move the pointer pointing to the shorter line
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // Output: 49

Pattern 2: Same Direction (Slow & Fast)

Both pointers start from the same end and move in the same direction, but at different speeds. This is useful for in-place array modifications and cycle detection.

Example 5: Remove Duplicates from Sorted Array

Remove duplicates in-place and return the count of unique elements:

javascript
function removeDuplicates(nums) {
    if (nums.length === 0) return 0;

    let slow = 0;  // Points to the last unique element placed

    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[fast] !== nums[slow]) {
            slow++;                    // Advance unique position
            nums[slow] = nums[fast];   // Place unique element
        }
    }

    return slow + 1;  // Length of unique elements
}

const nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
console.log(removeDuplicates(nums)); // Output: 5
// nums is now [0, 1, 2, 3, 4, ...]

Example 6: Move Zeroes

Move all zeroes to the end while maintaining order of non-zero elements:

javascript
function moveZeroes(nums) {
    let slow = 0;  // Next position for a non-zero element

    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
            slow++;
        }
    }
    return nums;
}

console.log(moveZeroes([0, 1, 0, 3, 12])); // [1, 3, 12, 0, 0]

Pattern 3: Fast & Slow (Floyd's Tortoise & Hare)

One pointer moves 1 step at a time (slow / tortoise), while the other moves 2 steps (fast / hare). This is the classic pattern for linked list problems.

Key Insight: If a cycle exists, the fast pointer will eventually "lap" and catch up to the slow pointer within the cycle.

Example 7: Detect Cycle in Linked List

javascript
function hasCycle(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;        // Move 1 step
        fast = fast.next.next;   // Move 2 steps

        if (slow === fast) return true;  // Cycle detected!
    }

    return false;  // Fast reached null → no cycle
}

Visual:

Linked List with cycle: 1 → 2 → 3 → 4 → 5
                                    ↑           |
                                    └───────────┘

Step 1: slow=1, fast=1
Step 2: slow=2, fast=3
Step 3: slow=3, fast=5
Step 4: slow=4, fast=4  ← MEET! Cycle detected

Example 8: Find Middle of Linked List

javascript
function middleNode(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;  // When fast reaches end, slow is at middle
}

For list 1 → 2 → 3 → 4 → 5, slow will be at node 3 (the middle).

Pattern 4: Merge Two Sorted Arrays / Strings

Use two pointers to merge two sorted sequences into one in O(N + M) time:

javascript
function mergeSortedArrays(arr1, arr2) {
    const merged = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            merged.push(arr1[i++]);
        } else {
            merged.push(arr2[j++]);
        }
    }

    // Append remaining elements
    while (i < arr1.length) merged.push(arr1[i++]);
    while (j < arr2.length) merged.push(arr2[j++]);

    return merged;
}

console.log(mergeSortedArrays([1, 3, 5], [2, 4, 6]));
// Output: [1, 2, 3, 4, 5, 6]

Pattern 5: Three Sum (3 Pointers)

Find all unique triplets in an array that sum to zero — uses one fixed pointer + two-pointer approach:

javascript
function threeSum(nums) {
    nums.sort((a, b) => a - b);    // Sort first!
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;  // Skip duplicates

        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// Output: [[-1,-1,2],[-1,0,1]]

Advantages and Disadvantages

Complexity Reference

Real World Usages

• Memory Management: Finding pairs of free memory blocks whose sizes fit a given allocation request.
• Database Merge Joins: SQL engines use a two-pointer merge to join two pre-sorted result sets efficiently — no nested loops.
• Media Stream Synchronization: Merging audio and video timestamp streams from different sources.
• Merge Phase in Merge Sort: The core of merge sort uses two pointers to merge two sorted halves.
• Network Packet Processing: Detecting anomalous patterns in network traffic using a fast scan with a slow baseline pointer.
• Text Editors: Finding matching brackets or parentheses uses a pointer-based scan from each end.

Common Interview Patterns

1. Valid Palindrome: Compare characters from both ends, skip non-alphanumeric.
2. Two Sum II (Sorted Array): Converging pointers on sorted array to find pair sum.
3. 3Sum: Fix one element, two-pointer on the rest. O(N²).
4. Remove Duplicates: Slow pointer tracks last unique; fast scans ahead.
5. Linked List Cycle Detection: Floyd's tortoise and hare algorithm.
6. Find Middle of Linked List: Fast moves 2x as fast as slow.
7. Container With Most Water: Greedy two-pointer, move shorter side inward.
8. Trapping Rain Water: Two-pointer tracking max heights from each side.
9. Sort Colors (Dutch National Flag): Three-pointer partition for 0s, 1s, 2s.

Frequently Asked Questions

Q: How is two pointers different from sliding window?
A: Two pointers is a general technique where two indices traverse a structure. Sliding window is a specific application of two pointers for contiguous subarray/substring problems. All sliding windows use two pointers, but not all two-pointer problems are sliding windows. For example, the palindrome check and cycle detection use two pointers but are not sliding windows.

Q: Does two pointers only work on sorted arrays?
A: No. Sorting is required for some two-pointer patterns (like finding a pair with target sum) because the sorted order lets you confidently decide which pointer to move. But other patterns like fast-slow (cycle detection), same-direction (remove duplicates), and merge (sorted merge) don't require the full array to be sorted beforehand.

Q: What happens when there are duplicates in the two-sum problem?
A: After finding a valid pair, you need to skip all duplicates by advancing left past repeated values and right past repeated values before continuing. This prevents outputting the same pair multiple times.

Q: Can two pointers work on 2D arrays?
A: Yes! For matrix problems, you can apply two-pointer logic along a single row/column, or use a modified approach where one pointer scans rows and another scans columns (like in the sorted matrix search).

Q: What is the Dutch National Flag problem and why does it use three pointers?
A: The Dutch National Flag problem sorts an array containing only 0s, 1s, and 2s in O(N) with O(1) space. It uses three pointers: low (boundary between 0s and 1s), mid (current element being examined), and high (boundary between 1s and 2s). Elements are swapped based on their value to sort everything in one pass.