Ordered set / sorted container

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Numbers arrive one by one: 1, 5, 9, 1, 5, 9. After each arrival you must say whether the new number is within distance t of any of the last k numbers. Take k = 3 and t = 0, so the question becomes "is there an equal number among the last three?". By hand you look back at the three most recent numbers and compare. That is 3 comparisons per arrival; with k = 100,000 it is 100,000 comparisons per arrival, and a million arrivals makes a hundred billion.

The waste is in comparing against every window member when only the two members nearest in value matter: the largest member at most x, and the smallest member at least x. If neither is within t, nothing else is.

Build the structure, one piece at a time

Piece one: keep the window's values in sorted order. In a sorted list the two neighbours of a value are found by bisection, cutting the range in half each step, and they sit next to each other.

Piece two: a container that stays sorted while things are added and removed in O(log k). A balanced tree does it, and so does a skip list; Python offers a sorted list container, Java a TreeMap, C++ a multiset. The exact machinery does not matter for the pattern; what matters is three operations: insert, remove, and "neighbours of x".

Piece three: the sliding window. When a value enters, ask for its neighbours, then insert it. When the window is longer than k, remove the oldest value, which you find by position in the original stream, not by its sorted place:

Had the answer been no, the oldest value 1 would be removed to keep the window at three, giving [1, 5, 9] again with the new 1.

Why it is correct

The invariant is that the container holds exactly the last k values, in sorted order. Insert and remove by value keep it sorted; removing the oldest keeps the membership right. The neighbour test is complete: let a be the largest window value at most x and b the smallest at least x. Any other window value y is either below a, so x − y > x − a, or above b, so y − x > b − x. So if neither neighbour is within t, no window value is:

min over the window of |x − y| = min(x − a, b − x)

Why it is fast

Each arrival does one neighbour lookup, one insert and at most one remove, each O(log k) in a balanced sorted container. For n arrivals that is O(n log k): for a million arrivals and a window of 100,000, about 17 million steps against a hundred billion. The memory is the window, O(k).

The same container answers other window questions. The median is the middle element, reached by index in a sorted list. The maximum minus the minimum is last minus first, which solves "longest subarray with difference at most a limit". "How many earlier values are smaller" is the insertion index of the new value.

How to recognise it in an interview

Cues: "sliding window" together with "median", "within distance t", "difference at most", "k-th smallest so far", or any time you need the value just above or just below x among a changing set. Say: "the only members that matter are the two nearest in value, so I will keep the window in a sorted container and bisect".

Sliding Window Median keeps the window sorted and reads the middle. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit grows a window and shrinks it while last − first exceeds the limit. Count of Smaller Numbers After Self scans from the right and records each value's insertion index.

02The idea in one line

Keep a sorted multiset; bisect for neighbours, insert/delete in O(log n).

Reach for it when: Contains duplicate III, sliding window median, 132 pattern, exam room, my calendar.

Cost: O(log n) per op.

03The walk-through, step by step

The video works one example: Contains Duplicate III window k=3, t=0 on [1,5,9,1,5,9]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Keep the window's values in a sorted container; neighbours of x are one bisect away
2. x = 1: nearest values — / —, none within 0
3. insert 1 in sorted position
4. x = 5: nearest values 1 / —, none within 0
5. insert 5 in sorted position
6. x = 9: nearest values 5 / —, none within 0
7. insert 9 in sorted position
8. x = 1: neighbour 1 is within t = 0 → true
9. Insert, remove and neighbour lookup are all O(log k): O(n log k) total

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Advanced Structures: Segment tree (range query + point update), Fenwick tree (binary indexed tree), Bucketing by value range, Matrix exponentiation for recurrences, Meet in the middle.