Ordered Set Coding Problems: 32 Questions with Solutions
32 ordered set coding problems — 1 easy · 17 medium · 14 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.
- Problems: 32
- By difficulty: 1 easy · 17 medium · 14 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
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
11 of the 32 Ordered Set problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 21 in the full list below are practice at your own pace. Then move on to Bit Manipulation.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.
Day 2
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Continuous Subarrays Medium
- Minimum Absolute Sum Difference Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Odd Even Jump Hard
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- The Skyline Problem Hard
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
TreeSetorstd::set, which keep one copy; use aTreeMapof counts or astd::multiset. - Erasing a value from a
std::multiset, which removes every copy; erase the one iteratorfindreturns. ceiling(x)may return x itself,higher(x)never does; "at least" or "greater than" decides.- No element qualifying: Java gives
null, C++end(),bisectthe 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
Easy (1)
- Merge Similar Items Array, Hash Table, Sorting
Medium (17)
- Implement Router Array, Hash Table, Binary Search
- Design Task Manager Hash Table, Heap (Priority Queue), Design
- Longest Uploaded Prefix Hash Table, Binary Search, Union Find
- Design a Food Rating System Array, Hash Table, String
- Design a Number Container System Hash Table, Heap (Priority Queue), Design
- Smallest Number in Infinite Set Hash Table, Heap (Priority Queue), Design
- Stock Price Fluctuation Hash Table, Design, Heap (Priority Queue)
- Tweet Counts Per Frequency Hash Table, Binary Search, Sorting
- My Calendar II Array, Binary Search, Prefix Sum
- My Calendar I Array, Binary Search, Segment Tree
- Power Grid Maintenance Array, Hash Table, Depth-First Search
- Minimum Absolute Difference Between Elements With Constraint Array, Binary Search, Binary Indexed Tree
- Minimum Absolute Sum Difference Array, Binary Search, Sorting
- Continuous Subarrays Array, Sliding Window, Monotonic Queue
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Array, Sliding Window, Monotonic Queue
- The Number of the Smallest Unoccupied Chair Array, Hash Table, Heap (Priority Queue)
- 132 Pattern Array, Binary Search, Stack
Hard (14)
- Sequentially Ordinal Rank Tracker Design, Heap (Priority Queue)
- Design Movie Rental System Array, Hash Table, Heap (Priority Queue)
- Finding MK Average Queue, Heap (Priority Queue), Binary Indexed Tree
- Range Module Segment Tree, Design, Binary Search
- Data Stream as Disjoint Intervals Binary Search, Design
- Sum of Imbalance Numbers of All Subarrays Array, Hash Table
- Shortest Distance After Road Addition Queries II Array, Graph
- Minimum Reverse Operations Array, Breadth-First Search, Union Find
- Maximum Strictly Increasing Cells in a Matrix Array, Hash Table, Binary Search
- Max Sum of Rectangle No Larger Than K Array, Binary Search, Matrix
- My Calendar III Binary Search, Segment Tree, Prefix Sum
- The Skyline Problem Array, Divide and Conquer, Heap (Priority Queue)
- Odd Even Jump Array, Dynamic Programming, Stack
- Minimize Deviation in Array Array, Greedy, Heap (Priority Queue)
Companies that ask ordered set problems
- Amazon 25 problems on ordered set
- Google 24 problems on ordered set
- Uber 5 problems on ordered set
- Microsoft 3 problems on ordered set
- Bloomberg 2 problems on ordered set
- Capital One 2 problems on ordered set
- Sprinklr 2 problems on ordered set
- Twitter 2 problems on ordered set
- Atlassian 1 problem on ordered set
- CRED 1 problem on ordered set
- Databricks 1 problem on ordered set
- Flipkart 1 problem on ordered set
Next topic: Bit Manipulation