Sliding Window & Two Pointers

Mastering the Core Patterns

The Two Pointers and Sliding Window techniques are powerful strategies for optimizing array and string problems, often reducing time complexity from O(n²) to a much more efficient O(n).

1. Two Pointers

This technique involves using two separate pointers to traverse a data structure. The way they move depends on the problem.

Pattern A: Opposite Ends

This pattern is typically used on sorted arrays. One pointer (left) starts at the beginning, and the other (right) starts at the end. They move towards each other based on a condition.

Finding Target Sum in Sorted Array

Sorted Array: [2, 7, 11, 15]  Target: 9
L         R
[2, 7, 11, 15] -> 2 + 15 = 17. Too high! Move R left.
L      R
[2, 7, 11, 15] -> 2 + 11 = 13. Too high! Move R left.
L   R
[2, 7, 11, 15] -> 2 + 7 = 9. Match found!

Classic Problem: Two Sum II

Given a sorted array, find two numbers that add up to a specific target.

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                return [left + 1, right + 1]
            elif current_sum < target:
                left += 1
            else:
                right -= 1

Classic Problem: Container With Most Water

Find two lines that form a container with the most water. The key insight is to move the pointer of the shorter line inwards, as this is the only way to potentially increase the container's height.

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        left, right = 0, len(height) - 1
        while left < right:
            width = right - left
            current_height = min(height[left], height[right])
            current_area = width * current_height
            max_area = max(max_area, current_area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

Pattern B: Same Direction (Fast/Slow)

Both pointers start at the beginning, but one (fast) moves ahead of the other (slow). This is useful for problems involving processing elements based on some condition or for finding cycles.

Classic Problem: Remove Duplicates from Sorted Array

A "slow" pointer marks the end of the unique elements, while a "fast" pointer iterates through the array to find the next unique element.

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        slow = 1 # Points to where the next unique element should be placed
        for fast in range(1, len(nums)):
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

2. Sliding Window

This is an extension of the same-direction two-pointer technique. The pointers (left and right) define a "window" over a portion of the data. This window can either be a fixed size or a dynamic size that expands and shrinks.

Dynamic Window

The window grows by moving the right pointer and shrinks by moving the left pointer. This is used for problems that ask for the longest or shortest subarray/substring that satisfies some condition.

Finding Longest Unique Substring

String: "aabcda"  Condition: Longest substring with unique characters
R
[a]abcda   -> Window: "a", Len: 1
R

[aa]bcda   -> Duplicate 'a'. Shrink Left.
[a]bcda   -> L,R at same spot. Window "a"
  R

a[ab]cda  -> Window: "ab", Len: 2
   R

a[abc]da -> Window: "abc", Len: 3
...and so on.

Classic Problem: Longest Substring Without Repeating Characters

Expand the window with the right pointer, using a hash set to track characters. If a duplicate is found, shrink the window from the left until the duplicate is removed.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_len = 0
        for right in range(len(s)):
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            char_set.add(s[right])
            max_len = max(max_len, right - left + 1)
        return max_len

Classic Problem: Minimum Size Subarray Sum

Find the minimal length of a subarray whose sum is greater than or equal to a target. Expand the window by adding the right element to a running sum. While the sum meets the target, update the minimum length and shrink the window from the left.

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left, total = 0, 0
        res = float('inf')

        for right in range(len(nums)):
            total += nums[right]
            while total >= target:
                res = min(res, right - left + 1)
                total -= nums[left]
                left += 1
        
        return 0 if res == float('inf') else res

Hard Problem: Minimum Window Subsequence

Given strings s1 and s2, find the minimum contiguous substring of s1 such that s2 is a subsequence of it. This advanced problem requires a dynamic two-pointer approach. One pointer scans through s1 to find a potential match for s2. Once a match is found, a second pair of pointers works backward to find the smallest possible start for that specific window, updating the global minimum found so far.

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        i, j = 0, 0
        min_len = float('inf')
        res = ""

        while i < len(s1):
            if s1[i] == s2[j]:
                j += 1
            if j == len(s2):
                # Found a potential window, now shrink it from the right
                end = i
                j -= 1
                while j >= 0:
                    if s1[i] == s2[j]:
                        j -= 1
                    i -= 1
                i += 1 # move i to the start of the window
                j = 0    # reset j to start of s2 for next search
                
                if end - i + 1 < min_len:
                    min_len = end - i + 1
                    res = s1[i : end + 1]
            i += 1
        return res

Interactive Two Pointers

Visualize the two-pointer technique on a sorted array to find a pair that sums to a target.

Target Sum

Enter a target sum and press Start.

Interactive Sliding Window

Visualize finding the longest substring without repeating characters.

Text String

Characters in Window

Max Length Found

Press Start to visualize.