Two Pointers — [Notes]

Refer this link for all DSA articles

· Important points
· Types of Two Pointers
· Sample Problem
· Problems
· 3.1 Collision
· 3.2 Forward
· 3.3 Parallel
· References

Why use two-pointer

• By reducing nested loops, the two-pointers strategy reduces time complexity.
• The fundamental requirement for employing the two-pointers technique to solve a problem effectively is that each pointer travels independently in a single direction.
• They can travel in opposite directions, but the direction should not change.

The two-pointer technique can be expanded to more sophisticated techniques such as sliding windows and dynamic programming.

🌟 Important points

1. The physical significance of the pointer
   → range
   → pair (i, j)
2. How to initialize the pointer
3. How to change the pointer / move the pointer
4. When to stop

Types of Two Pointers

• Collision — One array, move from two sides to the middle / towards each other
  → Two Sum problem
• Forward — One array, both move forward/the same direction
• Parallel — Two arrays, each array has been assigned a pointer
  → Interval List Intersections’ problem on LeetCode.
• Sliding Window — Both pointers moving in the same direction at a fixed difference of k
• Fast/Slow: One pointer moves faster than the other.
  → removing duplicates from an array
  → Move Zeros

Sample Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, find if there exists any pair of elements (nums[i], nums[j], i!=j) such that their sum is equal to target.

// Two pointers, O(n)
public boolean isPairSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    int start = 0;
    int end = nums.length - 1;
 
    while (start < end) {
        int sum = nums[start] + nums[end];
        if (sum == target) {
            return true; // pair exists
        } else if (sum < target) {
            start++; // move start forward to get larger value
        } else {
            end--; // move end backward to get smaller value
        }
    }
 
    // not found
    return false;
}

Problems

3.1 Collision

Sub type: Two Sum

• LeetCode 167 — Two Sum II — Input array is sorted
• LeetCode 15–3Sum (Sort + Loop + Two Pointers)
• LeetCode 16–3Sum Closest (Sort + Loop + Two Pointers + diff)
• LeetCode 18–4Sum (Sort + Double Loop + Two Pointers + HashSet)
• LeetCode 611 — Valid Triangle Number
• LeetCode 42 — Trapping Rain Water
• LeetCode 11 — Container With Most Water

Sub type: Partition

• LintCode 31 — Partition Array(Quick sort)
• LeetCode 125 — Valid Palindrome
• LeetCode 75 — Sort Colors
• LintCode 373 — Partition Array by Odd and Even
• LintCode 49 — Sort Letters by Case

3.2 Forward

Sub type: Window

• LeetCode 209 — Minimum Size Subarray Sum
• LeetCode 3 — Longest Substring Without Repeating Characters (HashMap + Two Pointers)
• LeetCode 76 — Minimum Window Substring (HashMap + Two Pointers)
• LeetCode 159 — Longest Substring with At Most Two Distinct Characters (HashMap + Two Pointers)
• LeetCode 340 — Longest Substring with At Most K Distinct Characters
• LeetCode 19 — Remove Nth Node From End of List (One pass, moving window, linked list)
• https://www.interviewbit.com/problems/max-continuous-series-of-1s/

Sub type: fast and slow

• LeetCode 876 — Middle of the Linked List(second middle node)
• LeetCode 141 — Linked List Cycle
• LeetCode 142 — Linked List Cycle II

3.3 Parallel

Two arrays, one pointer each.

• LintCode 387 — The Smallest Difference
• LeetCode 21 — Merge Two Sorted Lists

Others- Todo

• LeetCode 26 — Remove Duplicates from Sorted Array
• LeetCode 186 — Reverse Words in a String II
• LeetCode 189 — Rotate Array
• LeetCode 238 — Product of Array Except Self

Sliding Window vs Two-pointer technique — [Notes]

References

Algorithm - Two Pointers