Ordered Set Coding Problems: 4 Questions with Solutions

4 ordered set coding problems — 2 medium · 2 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 4-day plan.

Problems: 4
By difficulty: 2 medium · 2 hard
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Cost: Free on every plan; sign in to run and submit

An ordered set keeps its elements sorted while they are inserted and removed, and answers what a hash set cannot: the smallest, the largest, the first value at least x, the last value at most x. Java's TreeSet and TreeMap and C++'s set and map are balanced search trees that do each of these in logarithmic time; Python has no built-in equivalent, so solutions use a heap, a list kept sorted with bisect, or a third-party sorted list. The problems here practise choosing between those and the successor and predecessor lookups they serve.

How ordered set works, step by step

Closest earlier value, with an ordered set. Example: nums = [7, 2, 9, 4, 12, 8]

Values arrive one at a time, and for each we want the closest value seen before it. Keep the earlier values in a sorted set (a balanced tree): the closest one is either the floor, the largest value below, or the ceiling, the smallest above.
7 arrives to an empty set, so there is nothing to compare it with yet; it is simply inserted.
2 arrives. A binary search in [7] finds no floor and the ceiling 7, 5 above; nothing further out can be closer. That is the first gap: 5. 2 is inserted at the front.
9 arrives. A binary search in [2, 7] finds the floor 7, 2 below and no ceiling; nothing further out can be closer. That beats the best so far: 2. 9 is inserted at the back.
4 arrives. A binary search in [2, 7, 9] finds the floor 2, 2 below and the ceiling 7, 3 above; nothing further out can be closer. The best stays 2. 4 is inserted between them.
12 arrives. A binary search in [2, 4, 7, 9] finds the floor 9, 3 below and no ceiling; nothing further out can be closer. The best stays 2. 12 is inserted at the back.
8 arrives. A binary search in [2, 4, 7, 9, 12] finds the floor 7, 1 below and the ceiling 9, 1 above; nothing further out can be closer. That beats the best so far: 1. 8 is inserted between them.
The smallest gap between a value and any earlier one is 1, between 8 and 7. Each arrival costs one O(log n) search and one O(log n) insertion, so all n cost O(n log n), against O(n²) for comparing every pair.

Ordered Set study plan

All 4 Ordered Set problems (2 medium and 2 hard) over 4 days, about 3 h 5 min in all — the pattern first, then easiest to hardest. Then move on to Bit Manipulation.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

The Number of the Smallest Unoccupied Chair Medium

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

132 Pattern Medium

Day 3

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Odd Even Jump Hard

Day 4

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Minimize Deviation in Array Hard

Next topic: Bit Manipulation

Ordered Set: the essentials

When to reach for it

A collection that changes while you ask about its order: the smallest free chair, the smallest value at least arr[i] to its right, the maximum and minimum after each change. A Heap suffices when only one end matters; an ordered set also removes any element and finds ceilings (the first value at least x) and floors (the last value at most x).

The pattern

Java's TreeSet and TreeMap (ceiling, floor, higher, lower, pollFirst) and C++'s std::set and std::map (lower_bound, upper_bound) are balanced search trees. Python has none built in; a list kept sorted with bisect does the lookups. Scanning from the right, querying before inserting, gives each index its ceiling among the elements after it.

from bisect import bisect_left, insort

def odd_jumps(arr):                     # the j > i with the smallest arr[j] >= arr[i]
    right, out = [], [-1] * len(arr)    # right: sorted (value, index) pairs after i
    for i in range(len(arr) - 1, -1, -1):
        k = bisect_left(right, (arr[i], i))     # equal values: the smaller index
        if k < len(right):
            out[i] = right[k][1]
        insort(right, (arr[i], i))
    return out

Cost

A balanced tree inserts, removes and finds a ceiling or floor in O(log n). A sorted Python list finds in O(log n) but inserts in O(n) as elements shift: fine for tens of thousands, and sortedcontainers goes further.

Common mistakes

Repeated values in a TreeSet or std::set, which keep one copy; use a TreeMap of counts or a std::multiset.
Erasing a value from a std::multiset, which removes every copy; erase the one iterator find returns.
ceiling(x) may return x itself, higher(x) never does; "at least" or "greater than" decides.
No element qualifying: Java gives null, C++ end(), bisect the list's length.

Start with

The Number of the Smallest Unoccupied Chair: the smallest free chair as friends come and go.
132 Pattern: the smallest value on the right above the minimum on the left.
Odd Even Jump: ceilings and floors, scanning from the right.

All ordered set problems

Medium (2)

The Number of the Smallest Unoccupied Chair Array, Hash Table, Heap (Priority Queue)
132 Pattern Array, Binary Search, Stack

Hard (2)

Odd Even Jump Array, Dynamic Programming, Stack
Minimize Deviation in Array Array, Greedy, Heap (Priority Queue)

Companies that ask ordered set problems

Amazon 4 problems on ordered set
Google 4 problems on ordered set
Bloomberg 1 problem on ordered set
Cred 1 problem on ordered set
Meta 1 problem on ordered set
Uber 1 problem on ordered set