W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Two Pointers & Sliding Window

Master the art of O(n) optimization with pointer tricks.

What is the Two Pointer Technique?

The Two Pointer Technique is an algorithmic pattern that uses two distinct indices (pointers) to traverse a data structure (typically an array or list) in O(n) time complexity. It is primarily used to minimize nested loops by moving pointers towards each other or in the same direction based on specific conditions, effectively optimizing brute-force solutions.

Expert Note: Senior Engineers at Google and Meta frequently ask Two Pointer questions (like 3Sum and Container With Most Water) to test a candidate's ability to optimize brute-force O(n²) solutions into linear O(n) solutions.

Patterns

Minutes

O(n)

Complexity

Visualizers

Two-Pointer Technique Basics

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

The Two-Pointer Technique uses indexes (pointers) to minimize nested loops. Instead of brute-forcing pairs in O(n²), we move pointers intelligently to solve problems in O(n).

Real-life Analogy:
Imagine two friends looking for a book in a library row:
- Rahul starts from the left (start).
- Priya starts from the right (end).
They walk towards each other. If the total pages they see is too high, Priya moves left. If too low, Rahul moves right.

When to Use:
- ✅ Sorted Array problems (Find pairs, triplets)
- ✅ Searching from both ends (Palindrome, Trap Rain Water)
- ✅ Cycle detection (Linked List)
- ✅ Partitioning / Merging (QuickSort, MergeSort)

Three Main Types:
1. Opposite Direction: One from start, one from end (Meet in middle)
2. Same Direction: Both move forward (Fast/Slow pattern)
3. Sliding Window: Maintaining a "window" of elements

C++ Template

// Generic Structure
int  left = 0;
int right = n - 1;

while (left < right) {
    if (condition) {
        // success
    } else if (too_small) {
        left++;
    } else {
        right--;
    }
}

Opposite Direction Pointers

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

Used for Sorted Arrays and Palindromes.

Logic:
Since the array is sorted, moving the left pointer increases the sum, and moving the right pointer decreases the sum.

Template (Two Sum Sorted):
left at 0, right at n-1.
- Sum < Target? Need bigger val → left++
- Sum > Target? Need smaller val → right--
- Sum == Target? Found it!

C++ Template

// Finding pair that sums to target in Sorted Array
int left = 0, right = nums.size() - 1;

while (left < right) {
    int sum = nums[left] + nums[right];
    
    if (sum == target) return {left, right};
    else if (sum < target) left++;  // Need bigger sum
    else right--;                   // Need smaller sum
}

Same Direction Pointers (Filters)

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

Used for In-Place operations (Remove duplicates, Move Zeroes).

Logic:
- Reader Pointer (i): Scans every element.
- Writer Pointer (j): Only moves when we "keep" an element.

Example: Remove Duplicates
Only write nums[i] to nums[j] if it's unique. Then increment j.

C++ Template

// Remove Duplicates
int j = 1; // Writer (starts at 1 because index 0 is always unique)

for (int i = 1; i < nums.size(); i++) { // Reader
    if (nums[i] != nums[i-1]) {
        nums[j] = nums[i]; 
        j++;
    }
}
return j; // New length

Fast & Slow Pointers (Tortoise-Hare)

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

Used for Cycle Detection and Linked List Middle.

Logic:
- Slow: Moves 1 step.
- Fast: Moves 2 steps.
- If there is a cycle, Fast will eventually catch valid Slow!
- If Fast reaches NULL, there is no cycle.

C++ Template

// Detect Cycle in Linked List
ListNode *slow = head, *fast = head;

while (fast && fast->next) {
    slow = slow->next;       // 1 step
    fast = fast->next->next; // 2 steps
    
    if (slow == fast) return true; // Collision = Cycle!
}
return false;

Sliding Window (Fixed Size)

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

Interactive

Loading visualizer...

Concept:
Like looking through a fixed-size frame (length K) on a moving train.

Optimization:
Instead of recalculating the sum for every window (O(n*k)), we SLIDE:
1. Subtract the element leaving the window.
2. Add the element entering the window.
This makes it O(1) per step!

Template:
1. Compute sum of first K elements.
2. Loop from K to n.
3. Update sum: sum += arr[i] - arr[i-K]

C++ Template

// Max Sum Subarray of size K
int currentSum = 0;
// 1. Init first window
for (int i=0; i<K; i++) currentSum += arr[i];

int maxSum = currentSum;

// 2. Slide
for (int i=K; i<arr.size(); i++) {
    currentSum += arr[i] - arr[i-K]; // Add new, Drop old
    maxSum = max(maxSum, currentSum);
}
return maxSum;

Sliding Window (Variable Size)

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

Interactive

Loading visualizer...

Concept:
The window expands and shrinks like a caterpillar to meet a condition (e.g., Sum >= Target).

Template:
1. Expand Right: Add elements to window.
2. Shrink Left: While condition is met (or violated), remove elements from left to optimize.

Useful For:
- Subarray with given sum
- Longest substring with no repeats
- Minimum window substring

C++ Template

// Smallest Subarray with sum >= target
int left = 0, sum = 0, minLen = INT_MAX;

for (int right = 0; right < n; right++) {
    sum += arr[right]; // Expand
    
    while (sum >= target) { // Shrink
        minLen = min(minLen, right - left + 1);
        sum -= arr[left];
        left++;
    }
}
return minLen;

Pattern Recognition: Which one to use?

Decision: O(1) logic!

How to choose in an Interview?

1. Two Pointers (Opposite)
- Clue: "Sorted Array", "Pairs", "Target Sum", "Palindrome"
- Action: left = 0, right = n-1

2. Two Pointers (Same Direction)
- Clue: "In-place Remove", "Filter", "Order matters", "Merge Sorted"
- Action: Read pointer + Write pointer

3. Sliding Window (Fixed)
- Clue: "Subarray of size K", "Continuous block of K"
- Action: Build K sum, then add new/remove old.

4. Sliding Window (Variable)
- Clue: "Longest Substring", "Minimum Subarray", "Consecutive elements summing to X"
- Action: Expand Right, Shrink Left loop.

C++ Template

// Quick Decision Checklist
if (Input is Sorted && Find Pair) -> Two Pointers (Opposite)
if (Find Subarray of Size K) -> Sliding Window (Fixed)
if (Find Longest/Shortest Subarray) -> Sliding Window (Variable)
if (Cycle Detection) -> Fast & Slow

Frequently Asked Questions

When should I use Sliding Window vs Two Pointers?

Use Sliding Window when dealing with subarrays (contiguous elements) of size K or finding the longest/shortest substring meeting a condition. Use Two Pointers when the array is sorted (finding pairs) or when comparing elements from both ends (palindromes).

Is Two Pointers only for sorted arrays?

Mostly yes, for finding pairs (like Two Sum). However, for techniques like "Move Zeroes" or "Remove Duplicates" (Writer/Reader pointers) or Linked List cycles (Fast and Slow), sorting is not required.

What is the time complexity of the Sliding Window technique?

The time complexity is O(n) (Linear Time). Although there might be nested loops (like the `while` loop for shrinking), each element is added once and removed at most once, resulting in `2n` operations in the worst case, which simplifies to O(n).

What is the Two Pointer Technique?

The Two-Pointer Technique uses indexes (pointers) to minimize nested loops. Instead of brute-forcing pairs in O(n²), we move pointers intelligently to solve problems in O(n).

// Generic Structure int left = 0; int right = n - 1; while (left < right) { if (condition) { // success } else if (too_small) { left++; } else { right--; } }

// Finding pair that sums to target in Sorted Array int left = 0, right = nums.size() - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) return {left, right}; else if (sum < target) left++; // Need bigger sum else right--; // Need smaller sum }

// Remove Duplicates int j = 1; // Writer (starts at 1 because index 0 is always unique) for (int i = 1; i < nums.size(); i++) { // Reader if (nums[i] != nums[i-1]) { nums[j] = nums[i]; j++; } } return j; // New length

// Detect Cycle in Linked List ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; // 1 step fast = fast->next->next; // 2 steps if (slow == fast) return true; // Collision = Cycle! } return false;

// Max Sum Subarray of size K int currentSum = 0; // 1. Init first window for (int i=0; i<K; i++) currentSum += arr[i]; int maxSum = currentSum; // 2. Slide for (int i=K; i<arr.size(); i++) { currentSum += arr[i] - arr[i-K]; // Add new, Drop old maxSum = max(maxSum, currentSum); } return maxSum;

// Smallest Subarray with sum >= target int left = 0, sum = 0, minLen = INT_MAX; for (int right = 0; right < n; right++) { sum += arr[right]; // Expand while (sum >= target) { // Shrink minLen = min(minLen, right - left + 1); sum -= arr[left]; left++; } } return minLen;

// Quick Decision Checklist if (Input is Sorted && Find Pair) -> Two Pointers (Opposite) if (Find Subarray of Size K) -> Sliding Window (Fixed) if (Find Longest/Shortest Subarray) -> Sliding Window (Variable) if (Cycle Detection) -> Fast & Slow