Module 8 · set and multiset: Sorted, Unique, Found in log n
CP and Interview Pack: set Patterns, Questions and the Bug Gallery
ProReading
The CSES Problem Set, a free collection of contest problems, has problem 1073, "Towers", in its Sorting and Searching section. Cubes arrive in a fixed order, and each one goes on a tower whose top is larger, or starts a new tower. What is the fewest towers you can end with? Bob checks every tower for every cube, which is O(n²). Amara keeps the tower tops in a multiset, and her whole solution is pattern 1.
Checking what this lesson needs for you…
What is inside CP and Interview Pack: set Patterns, Questions and the Bug Gallery
- Pattern 1: the next larger value with upper_bound
- Pattern 2: intervals in a set
- Pattern 3: erasing while you walk
- Pattern 4: a leaderboard of pairs
- Nine interview questions, with model answers