Two Pointers coding pattern

1. Introduction to the Two Pointers Pattern

The Two Pointers pattern is a fundamental algorithmic approach used when you need to process elements in pairs or comparative sequences within a data structure such as an array, string, or linked list.

It involves maintaining two distinct indices (pointers) that move across the structure in a controlled way to solve problems involving:

Searching pairs
Partitioning data
Reversing or merging elements
Eliminating duplicates
Checking palindromes

The two pointers may move:

Inward (from both ends)
Outward (from the center)
In one direction (both moving forward at different speeds)

2. Why Two Pointers?

The primary reason for using this pattern is efficiency.
Many brute-force solutions require nested loops, resulting in O(n²) complexity.
With two pointers, you can usually reduce it to O(n) because you traverse the structure only once (or at most twice).

3. When to Identify a Two Pointers Problem

You can usually identify that a problem can be solved using this pattern when:

The input is a sorted array or string, or sorting is allowed.
The problem involves comparing or matching pairs of elements.
The problem asks for pair sums, duplicates, partitions, or palindromic checks.
The problem involves merging or sliding along two structures simultaneously.

Common signs include:

“Find pairs that satisfy…”
“Remove duplicates…”
“Reverse elements…”
“Compare elements from both ends…”

4. Core Idea

The essence of the Two Pointers technique is to use two moving indices to control the range of examination:

Left pointer (start) — begins at the beginning.
Right pointer (end) — begins at the end.

At each step, based on some condition or comparison, you move one of the pointers toward the other or forward in the structure.

5. Variants of the Two Pointers Pattern

There are three main variants, depending on how the pointers move:

(a) Opposite Directions (Inward Movement)

Used when the array is sorted and you are looking for a pair that satisfies a condition (e.g., a target sum).

One pointer starts at the beginning (left).
Another starts at the end (right).
Move inward based on conditions.

Example problems:

Pair sum (Two Sum II)
Valid Palindrome check
Container with most water

(b) Same Direction (Forward Movement)

Used when both pointers move forward, but at different speeds.
Typical use cases involve removing duplicates, merging arrays, or fast-slow traversal in linked lists.

Example problems:

Remove duplicates from sorted array
Move zeroes
Detect cycle in linked list (Floyd’s Tortoise and Hare)

(c) Sliding Window (Dynamic Range)

A modified version where two pointers define a window (a subarray or substring) that expands or shrinks based on certain conditions.

Example problems:

Longest substring without repeating characters
Minimum window substring
Maximum sum subarray of size k

6. Example 1: Pair Sum in a Sorted Array

Problem:
Given a sorted array of integers and a target value, find if there exists a pair that adds up to the target.

Input: [1, 2, 3, 4, 6], target = 6
Output: true (2 + 4 = 6)

Algorithm:

Initialize two pointers:
- left = 0 (start of array)
- right = n - 1 (end of array)
Compute sum = arr[left] + arr[right].
If sum == target → found pair.
If sum < target → move left++ to increase sum.
If sum > target → move right-- to decrease sum.
Repeat until left >= right.

Java Implementation:

public class TwoSumSorted {
    public static boolean hasPairWithSum(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) return true;
            if (sum < target) left++;
            else right--;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6};
        System.out.println(hasPairWithSum(arr, 6)); // true
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

7. Example 2: Valid Palindrome Check (Inward Pointers)

Problem:
Check if a given string is a palindrome (reads the same backward and forward).

Algorithm:

Initialize left = 0, right = n - 1.
Compare characters s[left] and s[right].
If not equal → not palindrome.
Move inward: left++, right--.
Continue until pointers meet.

Java Implementation:

public class PalindromeCheck {
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("madam")); // true
        System.out.println(isPalindrome("hello")); // false
    }
}

Time Complexity: O(n)

8. Example 3: Removing Duplicates from a Sorted Array (Same Direction)

Problem:
Given a sorted array, remove duplicates in-place such that each element appears only once.

Algorithm:

Use two pointers:
- slow keeps track of the unique index.
- fast explores the array.
If arr[slow] != arr[fast], increment slow and copy value.
At the end, unique elements are from 0 to slow.

Java Implementation:

public class RemoveDuplicates {
    public static 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;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 3, 3};
        int len = removeDuplicates(nums);
        for (int i = 0; i < len; i++) {
            System.out.print(nums[i] + " "); // 1 2 3
        }
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

9. Example 4: Linked List Cycle Detection (Different Speeds)

Problem:
Detect if a linked list has a cycle.

Algorithm:

Use two pointers:
- slow moves one step at a time.
- fast moves two steps at a time.
If they ever meet → cycle detected.
If fast reaches null → no cycle.

Java Implementation:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class DetectCycle {
    public static boolean hasCycle(ListNode head) {
        if (head == null) return false;

        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast)
                return true;
        }
        return false;
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

10. Example 5: Container With Most Water (Opposite Directions)

Problem:
Given heights of vertical lines, find the maximum area of water a container can store.

Algorithm:

Initialize left = 0, right = n - 1.
Calculate area = (right - left) * min(height[left], height[right]).
Move pointer pointing to the smaller height.
Track maximum area found.

Key Insight:
Moving the taller line inward cannot increase area; only moving the smaller one might.

11. Time and Space Complexity (General)

Operation Type	Time Complexity	Space Complexity
Array-based two pointers	O(n)	O(1)
String-based two pointers	O(n)	O(1)
Linked list (fast/slow)	O(n)	O(1)
Sliding window variant	O(n)	O(1) or O(k) depending on window

12. How to Identify Two Pointers Problems Quickly

Look for these signals:

Problem involves pair comparison (sum, difference, match).
Problem involves sorted input.
You’re told to do something in-place (without extra space).
You need to merge, partition, or scan elements efficiently.
The question mentions “window,” “subarray,” or “substring.”

13. Advantages of the Two Pointers Pattern

Reduces time complexity drastically.
Uses constant space.
Ideal for streaming or large data.
Simplifies logic by avoiding nested loops.

14. Common Mistakes and Edge Cases

Forgetting to handle equal conditions (like duplicates).
Incorrect pointer movement leading to infinite loops.
Not handling boundaries properly (left < right conditions).
Overlooking sorted requirement in problems like two-sum.

15. Summary of Key Insights

Variant	Movement	Typical Problems	Example
Opposite ends	Inward	Pair sum, Palindrome, Container	Two Sum II
Same direction	Forward	Remove duplicates, Cycle detection	Linked List cycle
Sliding window	Expanding/shrinking	Substrings, subarrays	Longest substring without repeat