Skip to main content

Arrays, Two Pointers, Stacks, and Sliding Window

Arrays

Arrays may look simple, but they’re the foundation of coding interviews. Mastering them helps you move faster and avoid mistakes when tackling more advanced problems.

Clarifying questions to ask

These questions show interviewers that you’re thinking ahead:

  • Can the input have negative numbers? This matters for sliding window, sum-based or product-based problems.
  • What’s the maximum size of the array? This tells you if O(n^2) is acceptable.
  • Are duplicates allowed, and if so, how should they be handled?
  • Is the input already sorted? This is often a hint to use two pointers or binary search.

What to think about first

When you see an array problem, pause and run this quick mental checklist:

  • Does sorting help? Sorting often unlocks simpler approaches like two pointers or binary search. The O(n log n) cost is worth it if it reduces nested loops.
  • Do I need an extra data structure?
    • Set: When uniqueness is required (e.g., remove duplicates, check existence).
    • Dictionary: When you need to store relationships (value → index, frequency counts, prefix sums).
  • Can I do this in-place? Many interview problems (e.g., move zeroes, remove duplicates) want O(1) extra space solutions.

Edge cases

  • Empty array [] → should return 0, [], or false depending on problem.
  • Single element [x] → tests off-by-one errors.
  • All same elements [5,5,5] → helps catch duplicate handling mistakes.
  • Strictly increasing/decreasing arrays → good stress tests for pointer-based solutions.

Arrays Cheatsheet

Practice problems

Two pointers

The two-pointer technique is a simple but powerful way to work with arrays, linked lists, or strings. It uses two indices that either start at different positions and move toward each other, or move in the same direction, to efficiently compare, scan, or rearrange elements.

Learn more about the two pointer coding pattern here.

1. Opposite ends (converging)

  • Idea: Place one pointer at the start l, one at the end r, move them inward based on a rule.
  • When to use: Array is sorted and you need a pair satisfying a relation such as sum, area, distance.
l = 0, r = n-1 while l < r: # do work with a[l], a[r] if condition_to_shrink_right: r -= 1 else: l += 1

2. Same direction (slow/fast)

  • Idea: fast scans; slow marks the “write” or “valid” region.
  • When to use: Compacting, deduplicating, partitioning, or finding cycles (Floyd’s).
slow = 0 for fast in range(n): if keep(a[fast]): a[slow] = a[fast] # optional (in-place) slow += 1 # result often in a[0:slow]

Time complexity: O(n). If sorting is required then O(n log n).

Space complexity: O(1). O(n) if you return a new result list.

Common pitfalls

  • Duplicates: After finding a match, skip over repeated values (while l<r && a[l]==a[l-1] l++) to avoid duplicate answers.
  • Overflow/precision: Be careful with products or areas. Use long (Java) or long long (C++) if numbers can get large.
  • Indices vs values: Sorting changes indices. Clarify if the problem wants indices or just values.
  • Bounds: Always check loop conditions (l < r or fast < n) so pointers don’t cross or go out of range.
  • In-place writes: When modifying the array, don’t overwrite elements you haven’t processed yet. Write in the correct order.

Two Pointer Cheatsheet

Practice problems

Stack

A stack is a Last-In-First-Out (LIFO) data structure. You can only insert (push) or remove (pop) elements from the “top.” Stacks are extremely useful when the problem requires reversing order, remembering state, or keeping track of “previously seen but not yet matched” elements.

1. Simple stack

  • Idea: Use a regular stack for matching and balancing problems.
  • When to use: Parentheses validation, backspace string compare, undo operations, evaluating expressions.
stack = [] for ch in input: if condition: stack.append(ch) else: stack.pop()

2. Monotonic stack (increasing/decreasing)

  • Idea: Use a stack that always stays ordered (monotonic).
    • Monotonic increasing stack: Each new element is larger than the one before. If the current element is smaller, pop until the order is restored → helps find the next greater element.
    • Monotonic decreasing stack: Each new element is smaller than the one before. If the current element is larger, pop until the order is restored → helps find the next smaller element.
  • When to use: Whenever you need to efficiently find the next greater/smaller element or compare with nearby values. Classic problems include:
    • Stock span: For each day, how many consecutive past days had a price ≤ today’s price?
    • Daily temperatures: For each day, how many days until a warmer temperature?
    • Next greater/smaller element: For each element, find the next number to the right that’s larger/smaller.
    • Largest rectangle in histogram: Find the biggest rectangle area you can form between histogram bars.
    • Trapping rain water: Given bar heights, compute how much water is trapped between them.
stack = [] for i, x in enumerate(arr): while stack and arr[stack[-1]] > x: idx = stack.pop() # process arr[idx] knowing x is the next smaller stack.append(i)

Time complexity

  • Simple stack ops: O(1) per push/pop.
  • Stack-based scan (mono): O(n) overall. Each element is pushed and popped at most once.

Space complexity

  • Stack storage: O(n) in worst case.

Common pitfalls

  • Empty stack access: Always check before popping. Accessing an empty stack causes errors.
  • Infinite loops: Make sure push/pop conditions eventually progress the loop.
  • Wrong monotonic direction: Be clear whether the problem needs increasing or decreasing.
  • Index vs. value: Sometimes store indices (for ranges) instead of raw values.

Stack Cheatsheet

Practice Problems

Sliding window

Idea: Instead of checking every possible subarray or substring with nested loops, keep a “window” that slides across the input. Update the result as the window moves, so you avoid re-computing everything from scratch.

There are two main types:

  • Fixed-size window: The window length is constant.
    • Example: Find the maximum sum of any subarray of length k. You slide the window one step at a time, subtract the element that leaves and add the new one.
  • Variable (dynamic) window: The window can grow or shrink depending on conditions.
    • Example: Find the length of the longest substring without repeating characters. Expand the window until a repeat appears, then shrink from the left until it’s valid again.

When to use:

  • Subarray sums: e.g. maximum/minimum sum of a subarray of size k.
  • Longest/shortest substring: e.g. longest substring without repeating characters, smallest substring containing all target characters.
  • Counting problems: e.g. count the number of subarrays with sum ≤ k, or number of substrings matching a condition.

Learn more about the sliding window coding pattern here.

1. Fixed window

  • Window size k is given.
  • Keep a running sum/aggregate as the window slides.
  • Each step: add new element, remove old element.
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)

2. Variable (dynamic) window

  • Window grows/shrinks depending on conditions.
  • Typically two pointers: l (left), r (right).
  • Expand by moving r; shrink by moving l.
l = 0 for r in range(len(arr)): # expand window with arr[r] while condition_not_satisfied: # shrink from left l += 1 # process window [l, r]

Time complexity: O(n) (each element added/removed at most once)

Space complexity: O(1) to O(charset size) if using dict/set

Common pitfalls

  • Forgetting to shrink → infinite loop
  • Off-by-one errors (while l <= r vs l < r)
  • Misunderstanding “at most” vs “exactly” conditions
  • Forgetting to reset counts when window shrinks

Sliding Window Cheatsheet

Practice problems

Next Lesson