AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Ordered Set coding problems

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.

32 problems · 1 easy · 17 medium · 14 hard · judged by hidden tests in 13 languages

32problems

1 easy

17 medium

14 hard

Sign in to tick off what you solve.

Study plan: 11 problems · about 7 h 10 min

Start the study plan

Next up: Merge Similar Items

How it works

Ordered Set, step by step

Closest earlier value, with an ordered set

nums = [7, 2, 9, 4, 12, 8]

nums7021924312485sortedemptyclosest so far: none

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.

0:01 / 0:31Step 1 of 8
Transcript · 8 steps

Study plan

Learn ordered set in 7 days

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.

  1. Day 1

    about 1 h 10 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

  2. Day 2

    about 1 h 10 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 50 min

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

  6. Day 6

    about 50 min

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

  7. Day 7

    about 50 min

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

    Next topic: Bit Manipulation

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

nums7021924312485sorted2478912answerminimum difference = 1 (8 and 7)
Closest earlier value, with an ordered set. Example: nums = [7, 2, 9, 4, 12, 8]
  1. 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.
  2. 7 arrives to an empty set, so there is nothing to compare it with yet; it is simply inserted.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.

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.

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.

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

All ordered set problems

Easy (1)

Medium (17)

Hard (14)

Companies that ask ordered set problems

Next topic: Bit Manipulation