Two Pointers and Sliding Window: Coding Interview Problem Patterns

Algorithms Algorithms 8 min read 1492 words Beginner ExcellentWiki Editorial Team

Two pointers and sliding window are fundamental problem-solving patterns that appear in countless coding interviews at top technology companies. Both techniques work on arrays, strings, and linked lists, often reducing O(n²) brute-force solutions to O(n) time with O(1) or O(k) space. Mastering these patterns is one of the highest-leverage investments you can make for technical interview preparation.

Two Pointers Technique

The two pointers technique uses two indices that move through a data structure to solve problems efficiently. The pointers can move in opposite directions (toward each other), the same direction (fast and slow), or other orchestrated patterns.

Opposite Direction Pointers

Two pointers start at the beginning and end of an array and move toward each other. This pattern is effective for sorted arrays and problems involving comparison of elements from both ends.

Two Sum (Sorted): Given a sorted array, find two numbers that add up to a target. Place left at index 0 and right at the last index. If the sum is less than the target, increment left. If greater, decrement right. If equal, return the indices. This solves the problem in O(n) time with O(1) space — far better than the O(n²) brute force.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

Palindrome Check: Check if a string is a palindrome by comparing characters at the left and right pointers, advancing both inward after each match, and returning false on the first mismatch.

Three Sum: Find all triplets that sum to zero. Sort the array, then for each element, use two pointers on the remaining subarray. The overall complexity is O(n²) — considerably better than O(n³) brute force.

Container With Most Water: Given an array of heights, find the maximum water that can be trapped between two lines. Start with pointers at both ends. Calculate the area, move the pointer at the shorter line inward, and track the maximum area. This greedy approach works because the shorter line limits the container.

Trapping Rain Water: Calculate how much water can be trapped between bars after rain. Maintain left and right pointers with left_max and right_max. At each step, advance the pointer with the smaller max height, adding to the total water based on the difference between the current height and the corresponding max.

Same Direction Pointers (Fast and Slow)

Both pointers start at the same position but move at different speeds. This pattern is also called Floyd’s algorithm or the tortoise-and-hare technique.

Middle of Linked List: The fast pointer moves two steps for each step of the slow pointer. When the fast pointer reaches the end, the slow pointer is at the middle. For an even number of nodes, two conventions exist — return the first or second middle.

def middle_of_linked_list(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Cycle Detection: Floyd’s cycle detection algorithm uses fast-slow pointers to detect cycles in linked lists. If the pointers ever meet, a cycle exists. To find the start of the cycle, reset one pointer to the head and move both at the same speed until they meet again.

Happy Number: Determine if a number is “happy” by repeatedly replacing it with the sum of squares of its digits. Use fast-slow pointer logic — if a cycle exists that does not include 1, the number is not happy.

Sliding Window

Sliding window maintains a subarray (window) of the data structure that expands and contracts as it moves through the array. The window can be fixed-size or variable-size, and it is ideal for problems involving contiguous subsequences.

Fixed Window Size

The window maintains a constant size. As the right pointer advances, the left pointer advances by the same amount — the window slides one position at a time.

Maximum Sum Subarray of Size K: Compute the sum of the first K elements. For each subsequent position, subtract the element leaving the window and add the element entering. Track the maximum sum seen.

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Sliding Window Maximum: Find the maximum value in each window of size K. Use a deque that stores indices in decreasing order of value. Before adding a new element, remove indices outside the window and indices whose values are less than the new element. The front of the deque always contains the maximum of the current window.

Variable Window Size

The window grows and shrinks based on conditions. The right pointer expands the window to include new elements; the left pointer shrinks it when the constraint is violated.

Longest Substring Without Repeating Characters: Maintain a character set for the current window. Move the right pointer forward, adding characters. When a duplicate is found, move the left pointer past the previous occurrence, removing characters from the set.

def longest_substring_without_repeating(s):
    char_set = set()
    left = max_length = 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_length = max(max_length, right - left + 1)
    return max_length

Minimum Window Substring: Find the smallest substring of S that contains all characters of T. Use two hash maps — one for the target character counts and one for the current window. Expand the right pointer until all target characters are present, then shrink from the left while the constraint still holds. Track the minimum window length and start position throughout.

Longest Repeating Character Replacement: Find the length of the longest substring containing the same letter after at most k replacements. Track the frequency of each character in the window. The window is valid if (window_size - max_frequency) ≤ k — the number of characters that need replacement does not exceed k.

Complexity Analysis Reference

Technique	Typical Time	Typical Space	Common Applications
Opposite pointers	O(n)	O(1)	Two sum sorted, palindrome, three sum
Fast and slow	O(n)	O(1)	Cycle detection, middle of list
Fixed window	O(n)	O(1) or O(k)	Max sum subarray, sliding max
Variable window	O(n)	O(k)	Longest substring, min window

The sliding window technique is particularly powerful because it transforms nested loops into a single pass. The left and right pointers each traverse the array at most once, never backtracking. This guarantees O(n) time even for problems that initially appear to require O(n²).

Practice Strategy

Start by identifying whether the input is a linear data structure (array, string, linked list). If the problem asks for a contiguous subarray or subsequence, consider sliding window. If it involves comparing elements from different positions, try two pointers.

Trace through examples on paper before coding. Draw the window boundaries or pointer positions at each step. After mastering these patterns, many interview problems that initially seem complex become variations of a familiar approach.

Frequently Asked Questions

How do I know whether to use two pointers or sliding window?

Two pointers typically involves comparing or pairing elements at different positions — often from opposite ends. Sliding window involves examining contiguous subarrays and maintaining a window that satisfies some constraint. If the problem asks for a contiguous subarray with some property, start with sliding window. If it asks about pairs or elements at specific positions, try two pointers.

What is the time complexity of sliding window algorithms?

Sliding window algorithms run in O(n) time — each element is visited at most twice (once by the right pointer, once by the left). The space complexity depends on the problem: O(1) for fixed windows, O(k) where k is the window size or character set size for variable windows.

Can the two pointers technique be used on unsorted arrays?

Opposite-direction two pointers requires sorted input for problems like two-sum. However, fast-slow pointers work on unsorted structures — cycle detection and middle-of-list do not require sorting. For unsorted arrays where you would need opposite-direction pointers, sorting first (O(n log n)) is usually the right approach.

How do I handle edge cases in sliding window problems?

Always consider: empty input (return 0 or empty result), window size larger than the array (handle gracefully), and cases where no valid window exists. Initialize tracking variables carefully — max_length should start at 0, min_length at infinity. Test with single-element inputs and cases where the window never needs to shrink.

What is the most common mistake with these patterns?

The most common mistake is advancing the wrong pointer or failing to update the window state correctly when shrinking. When the left pointer advances, ensure you remove the element at the left index from the window’s data structure. When the right pointer advances, ensure you add the element at the right index. Testing with small examples catches these errors.

Share this article

X LinkedIn Facebook Email