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)

Optimizing Nested Loops

Imagine two friends walking towards each other from opposite sides of a narrow bridge. They adjust their walking speeds based on their distance from one another.

The Two-Pointer Technique is an algorithmic pattern that uses two index variables (pointers) to traverse a data structure concurrently. Rather than checking all pairs using nested loops (O(n²) complexity), we move the pointers based on specific rules, reducing execution time to linear O(n) complexity.

When to Use:

Searching for element pairs or triplets in a sorted array.
Manipulating arrays in-place (e.g., removing elements, reversing elements).
Comparing elements in a single pass from opposite ends.
Checking for cycles or finding middles in Linked Lists.

Three Core Configurations:

Opposite Direction: Pointers start at opposite ends and move towards the middle.
Same Direction: Both pointers start at the beginning but advance at different speeds (Fast & Slow pointers).
Sliding Window: Maintaining a dynamic interval window between two pointers.

C++ Template — Two-Pointer Technique Basics

// Opposite Direction Traversal
int left = 0;
int right = n - 1;

while (left < right) {
    if (condition_met) {
        // Success
    } else if (value_too_small) {
        left++;
    } else {
        right--;
    }
}

Opposite Direction Pointers

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

Converging Boundary Searches

Imagine a balance scale. If the weight is too low, you add weight to the left pan (moving the left pointer up). If the weight is too high, you remove weight from the right pan (moving the right pointer down).

In a sorted array, moving the left pointer increases values, and moving the right pointer decreases values.

Two Sum Sorted Algorithm:

Initialize left = 0 and right = n - 1.
Compute sum = nums[left] + nums[right].
If sum == target, return the indices.
If sum < target, we need a larger value, so we increment left++.
If sum > target, we need a smaller value, so we decrement right--.

C++ Template — Opposite Direction Pointers

#include <vector>
using namespace std;

// Find pair that sums to target in a sorted array
vector<int> twoSumSorted(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};
        } else if (sum < target) {
            left++;  // Move left pointer rightward to increase sum
        } else {
            right--; // Move right pointer leftward to decrease sum
        }
    }
    return {};
}

Same Direction Pointers (Filters)

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

In-Place Array Processing

Imagine a quality control inspector on an assembly line. The conveyor belt continuously feeds products (the reader pointer). If a product passes inspection, the inspector places it directly in the shipping box (the writer pointer). If a product is defective, the inspector skips it, leaving the shipping box pointer where it is.

We use two pointers moving in the same direction to filter or modify array elements in-place:

Reader Pointer (i): Iterates sequentially through every element.
Writer Pointer (j): Points to the next location where a valid element should be written.

C++ Template — Same Direction Pointers (Filters)

#include <vector>
using namespace std;

// Remove duplicates from a sorted array in-place
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int j = 1; // Writer pointer
    for (int i = 1; i < nums.size(); i++) { // Reader pointer
        if (nums[i] != nums[i - 1]) {
            nums[j] = nums[i];
            j++;
        }
    }
    return j; // Returns the new length of unique elements
}

Fast & Slow Pointers (Tortoise-Hare)

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

Cycle Detection in Linked Lists

Imagine two runners on a circular athletics track. If runner A runs twice as fast as runner B, runner A will eventually lap runner B and pass them from behind. If they were running on a straight line, they would never meet again.

The Fast & Slow Pointer configuration uses two pointers traversing at different speeds:

Slow Pointer: Advances by 1 node per iteration.
Fast Pointer: Advances by 2 nodes per iteration.

Applications:

Cycle Detection: If a cycle exists, the fast pointer will eventually overlap and catch up to the slow pointer.
Finding Midpoints: When the fast pointer reaches the end of a Linked List, the slow pointer will be exactly at the middle node.

C++ Template — Fast & Slow Pointers (Tortoise-Hare)

struct ListNode {
    int val;
    ListNode *next;
};

// Check if a linked list contains a cycle
bool hasCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;       // Moves 1 step
        fast = fast->next->next; // Moves 2 steps
        
        if (slow == fast) {
            return true; // Collision detected (cycle exists)
        }
    }
    return false;
}

Sliding Window (Fixed Size)

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

Interactive

Loading visualizer...

VIEWPORT OVERLAYS

Imagine looking through a camera viewfinder frame of fixed width K as you pan across a panoramic view.

Instead of recalculating the sum of all elements inside the window at each step (which takes O(n * k) time), we can update the running sum in O(1) time:

Add the new element entering the window from the right.
Subtract the old element leaving the window from the left.

Algorithm Steps:

Compute the sum of the first K elements.
Loop from index K to n - 1.
Update the sum: currentSum += arr[i] - arr[i - K].

C++ Template — Sliding Window (Fixed Size)

#include <vector>
#include <algorithm>
using namespace std;

// Find maximum sum of a contiguous subarray of size K
int maxSumSubarray(vector<int>& arr, int K) {
    if (arr.size() < K) return -1;
    
    int currentSum = 0;
    for (int i = 0; i < K; i++) {
        currentSum += arr[i]; // Initialize first window
    }
    
    int maxSum = currentSum;
    for (int i = K; i < arr.size(); i++) {
        currentSum += arr[i] - arr[i - K]; // Slide window in O(1)
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

Sliding Window (Variable Size)

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

Interactive

Loading visualizer...

Expanding and Contracting Ranges

Imagine a caterpillar crawling along a branch. It stretches its head forward to search (expanding the window). Once it finds a leaf or satisfies a condition, it pulls its tail forward to contract its body (shrinking the window).

A variable-sized sliding window dynamically expands and contracts to find the optimal subarray satisfying a condition (e.g., sum is at least target).

Algorithm Template:

Expand Right: Add arr[right] to the window state.
Contract Left: While the window satisfies the required constraint, record the result, subtract arr[left] from the window state, and increment left++ to look for a smaller valid window.

C++ Template — Sliding Window (Variable Size)

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// Find length of smallest subarray with a sum >= target
int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0;
    int sum = 0;
    int minLen = INT_MAX;
    
    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right]; // Expand window rightward
        
        while (sum >= target) { // Contract window leftward
            minLen = min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

Pattern Recognition: Which one to use?

Decision: O(1) logic!

Decision Flowchart

Choose the appropriate pattern based on these common problem indicators:

1. Opposite Direction Pointers

Key indicator: Sorted array, looking for pairs/triplets, reversing values, or palindrome matching.
Action: Start pointers at indices 0 and n - 1.

2. Same Direction Pointers

Key indicator: Modifying arrays in-place, removing values, or partitioning.
Action: Maintain a fast reader pointer and a slow writer pointer.

3. Sliding Window (Fixed Size)

Key indicator: Subarray of a fixed size K, running average of a specific duration.
Action: Initialize a window of size K, then slide by adding arr[i] and removing arr[i - K].

4. Sliding Window (Variable Size)

Key indicator: Finding the longest or shortest contiguous subarray meeting a target condition.
Action: Use a nested loop to expand the right pointer and shrink the left pointer.

C++ Template — Pattern Recognition: Which one to use?

// Quick Decisions
// 1. Array Sorted + Find Pair -> Opposite Direction
// 2. Continuous Subarray of Size K -> Fixed Sliding Window
// 3. Find Longest/Shortest Subarray -> Variable Sliding Window
// 4. Linked List Cycles -> Fast & Slow Pointers

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?

// Opposite Direction Traversal int left = 0; int right = n - 1; while (left < right) { if (condition_met) { // Success } else if (value_too_small) { left++; } else { right--; } }

#include <vector> using namespace std; // Find pair that sums to target in a sorted array vector<int> twoSumSorted(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { return {left, right}; } else if (sum < target) { left++; // Move left pointer rightward to increase sum } else { right--; // Move right pointer leftward to decrease sum } } return {}; }

#include <vector> using namespace std; // Remove duplicates from a sorted array in-place int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int j = 1; // Writer pointer for (int i = 1; i < nums.size(); i++) { // Reader pointer if (nums[i] != nums[i - 1]) { nums[j] = nums[i]; j++; } } return j; // Returns the new length of unique elements }

struct ListNode { int val; ListNode *next; }; // Check if a linked list contains a cycle bool hasCycle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast && fast->next) { slow = slow->next; // Moves 1 step fast = fast->next->next; // Moves 2 steps if (slow == fast) { return true; // Collision detected (cycle exists) } } return false; }

#include <vector> #include <algorithm> using namespace std; // Find maximum sum of a contiguous subarray of size K int maxSumSubarray(vector<int>& arr, int K) { if (arr.size() < K) return -1; int currentSum = 0; for (int i = 0; i < K; i++) { currentSum += arr[i]; // Initialize first window } int maxSum = currentSum; for (int i = K; i < arr.size(); i++) { currentSum += arr[i] - arr[i - K]; // Slide window in O(1) maxSum = max(maxSum, currentSum); } return maxSum; }

#include <vector> #include <algorithm> #include <climits> using namespace std; // Find length of smallest subarray with a sum >= target int minSubArrayLen(int target, vector<int>& nums) { int left = 0; int sum = 0; int minLen = INT_MAX; for (int right = 0; right < nums.size(); right++) { sum += nums[right]; // Expand window rightward while (sum >= target) { // Contract window leftward minLen = min(minLen, right - left + 1); sum -= nums[left]; left++; } } return minLen == INT_MAX ? 0 : minLen; }

Decision Flowchart

Choose the appropriate pattern based on these common problem indicators:

1. Opposite Direction Pointers

Key indicator: Sorted array, looking for pairs/triplets, reversing values, or palindrome matching.
Action: Start pointers at indices 0 and n - 1.

2. Same Direction Pointers

Key indicator: Modifying arrays in-place, removing values, or partitioning.
Action: Maintain a fast reader pointer and a slow writer pointer.

3. Sliding Window (Fixed Size)

Key indicator: Subarray of a fixed size K, running average of a specific duration.
Action: Initialize a window of size K, then slide by adding arr[i] and removing arr[i - K].

4. Sliding Window (Variable Size)

Key indicator: Finding the longest or shortest contiguous subarray meeting a target condition.
Action: Use a nested loop to expand the right pointer and shrink the left pointer.

// Quick Decisions // 1. Array Sorted + Find Pair -> Opposite Direction // 2. Continuous Subarray of Size K -> Fixed Sliding Window // 3. Find Longest/Shortest Subarray -> Variable Sliding Window // 4. Linked List Cycles -> Fast & Slow Pointers