02. Two Pointer

Theory

Description

The Two Pointer Pattern is a technique used to solve problems involving sequences (such as arrays or lists) by utilizing two pointers that traverse the sequence in different ways. This approach is particularly effective in optimizing performance by reducing time complexity, especially for problems that involve checking pairs, subarrays, or sliding windows.

Types

Running from Beginning of 2 Arrays / Merging 2 Arrays
When to Use
This technique is commonly used in problems where you need to merge two sorted arrays or process two sequences simultaneously.
How It Works
- One pointer is used to iterate through each of the two arrays.
- Typically, both pointers start at the beginning of their respective arrays.
- Compare elements at both pointers, select the smaller (or larger, depending on the problem), and move the corresponding pointer forward.
- This is often used in merge operations (e.g., merging two sorted arrays) or problems like finding the intersection of two arrays.
Pointers Moving Towards Each Other
When to Use
This technique is ideal for problems where you need to find pairs that satisfy a specific condition, such as a target sum or product, especially in sorted arrays.
How It Works
- One pointer starts at the beginning of the array (left pointer), and the other starts at the end (right pointer).
- Both pointers move towards each other, adjusting based on the condition being checked.
- If the sum of the values at both pointers meets the condition (e.g., equals a target sum), return the result.
- If the sum is too low, move the left pointer forward; if it's too high, move the right pointer backward.
- This method is efficient for problems like "two-sum" or "pair sum" problems in sorted arrays.
Pointers Moving in the Same Direction
When to Use
This technique is ideal for problems like finding unique elements, counting subarrays, or rearranging elements.
How It Works
- One pointer (typically called slow) moves through the array, while the other pointer (called fast) explores further elements.
- The slow pointer often keeps track of the current valid position, while the fast pointer scans for new valid elements.
- This is especially useful for sliding window problems, where the window expands and shrinks by adjusting the pointers.
- It can also be used to remove duplicates in-place in an array.
One Fixed Pointer, One Moving Pointer
When to Use
This approach is commonly used for problems where you need to count subarrays or combinations that satisfy certain conditions (e.g., subarrays with a sum less than a target).
How It Works
- One pointer remains fixed (often at the start), while the other pointer (often called end or right) moves across the array.
- The fixed pointer may adjust based on the condition being tracked (for example, shrinking a window to meet a target sum).
- This approach is effective for problems where you need to track ranges or dynamic subarrays, like finding subarrays whose sum is less than or equal to a target value.
Expanding/Contracting Window
When to Use
This technique is ideal for problems where you need to manage subarrays or substrings that must satisfy a condition.
How It Works
- One pointer expands the window by moving forward, while the other pointer contracts it to maintain the desired condition (e.g., sum or length).
- This is particularly useful for sliding window problems where the window size adjusts dynamically based on conditions.

Benefits

Efficiency: The two-pointer approach often reduces time complexity from O(n²) to O(n), making it much faster for certain problems.
Simplicity: It simplifies complex problems (such as checking for pairs or subarrays) into a single pass through the array, resulting in cleaner and more efficient code.
Memory Efficiency: Unlike other approaches that may require extra space (such as hash tables), the two-pointer technique typically operates in-place, minimizing memory usage.

Problems