Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 63 ยท Search and Greedy Thinking

Two Pointers and Sliding Windows in Practice

Count subarrays in O(n) with two pointers: sum limits, the at-most-k trick for exactly-k distinct values, monotone pointers on sorted data and shortest covering windows.

Many contest problems ask you to count or measure contiguous ranges of an array: how many subarrays have a sum at most S, what is the shortest piece that contains every color, how many pairs are within distance d. The obvious solution tries every pair of endpoints and costs O(n^2), which is far too slow when n is 2 * 10^5. Two pointers, also called a sliding window, solves these in O(n) by moving both endpoints only forward.

The basic techniques are introduced in Two Pointers and Sliding Window. Here we focus on what contests add: counting every valid subarray instead of finding one, the "at most k" trick, pointers over sorted data, and how to convince yourself the window is allowed to shrink.

When the window may move

A sliding window is valid when the condition is monotone in the window size: if a window is good, every smaller window inside it is good too (or the reverse). Sums of positive numbers behave this way: a subarray with sum at most S stays at most S when you shorten it. That monotonicity is what guarantees that, once the left pointer has moved past a position, it never needs to go back.

flowchart LR
    A["Extend right by one"] --> B["Window still valid?"]
    B -->|yes| C["Count windows ending here"]
    B -->|no| D["Advance left until valid"]
    D --> C
    C --> A

The loop of a counting window: extend, repair, count.

The counting step is the contest-specific part. If the window [left, right] is the longest valid window ending at right, then every start from left to right also gives a valid subarray ending at right. That is right - left + 1 subarrays, all counted in one addition.

Windows with negative numbers are not monotone: adding an element can make a sum smaller, so shrinking from the left no longer repairs anything. Use prefix sums with sorting or a data structure for those cases (see Prefix Sums and Difference Arrays).

Counting subarrays with a limited sum

Problem. Given positive integers, count the subarrays whose sum is at most S.

The code below keeps the running sum of the window and moves left while the sum is too big. A brute-force counter checks the result on many seeded random arrays, the way you would stress test it before submitting.

Python Subarrays with sum at most S

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two details protect you from bugs. An element larger than S makes left jump to right + 1, the window becomes empty, and right - left + 1 is 0, which is correct. And the pointer left only increases, so the whole loop is O(n): each element enters the window once and leaves it once.

The "at most k" trick

Some conditions are only monotone in one direction. "Exactly k distinct values" is not monotone: extending a window can break it, but shrinking can also break it. "At most k distinct values" is monotone. The trick:

TEXT
exactly(k) = at_most(k) - at_most(k - 1)

Every subarray with exactly k distinct values has at most k distinct values but not at most k - 1, so subtracting the two counts leaves precisely those subarrays. The same idea works for "exactly k odd numbers" and "exactly k ones in a binary array".

Python Exactly k distinct values via at most k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that at_most_distinct(a, 0) returns 0, because no non-empty window has zero distinct values; this makes exactly_distinct(a, 1) work without a special case.

Monotone pointers on sorted data

When the data is sorted, two pointers can sweep without a "window" at all. For each i, the farthest j with a[j] - a[i] <= d only moves right as i grows, because a[i] only grows. That lets you count pairs in O(n) after sorting.

A second family asks for the shortest window satisfying a requirement, such as containing every kind of item. Here the roles flip: extend right until the window is valid, then shrink left as far as it stays valid, recording the length at each step.

Python Close pairs and the shortest covering window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In count_close_pairs, j never moves backward, so the loop is O(n) after the O(n log n) sort. In shortest_cover both pointers move forward only, so it is O(n) too.

Choosing between a window and other tools

Ask these questions in order:

  1. Are all numbers non-negative and is the condition monotone in window size? Use a window.
  2. Is the condition "exactly k"? Convert to at_most(k) - at_most(k - 1).
  3. Are there negative numbers or no monotonicity? Think prefix sums with a dictionary or sorted list, or binary search on the window length.
  4. Do you need the maximum or minimum inside the window? Add a monotonic deque (covered in Monotonic Stacks, Heaps and Deques in Contests).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can a sliding window count subarrays with sum at most S in O(n) for positive numbers?

    Positive numbers make the condition monotone in window size, so left never has to move back. Each element enters and leaves the window once.
  2. 2. The window [left, right] is the longest valid one ending at right. How many valid subarrays end at right?

    Every start from left to right gives a valid, shorter subarray ending at right, so there are right - left + 1 of them.
  3. 3. How do you count subarrays with exactly k distinct values using a window?

    Subarrays with at most k distinct values minus those with at most k - 1 leaves exactly the ones with k.
  4. 4. Why does a sum window fail for arrays that contain negative numbers?

    With negatives, removing the left element can increase the sum, so the repair step no longer moves toward validity and left can skip good starts.

Summary

  • Two pointers turn many O(n^2) subarray problems into O(n) because both ends only move forward.
  • Counting windows: after repairing, add right - left + 1 for the subarrays ending at right.
  • Windows need a condition that stays true when the window shrinks, which holds for sums of non-negative numbers and for "at most k" rules.
  • Use exactly(k) = at_most(k) - at_most(k - 1) for exact-count conditions.
  • On sorted data a second pointer that never moves back counts close pairs in O(n).
  • For shortest-window problems, extend until valid, then shrink while it stays valid.

Next: Greedy Algorithms and How to Trust Them