DSA Notes

Data Structures

Set & Multiset

A sorted collection with fast search, insert and erase.

The idea

set keeps distinct values in sorted order; insert, erase and find are O(log n). multiset is the same but allows duplicates.

Its real strength is order queries on data that keeps changing: lower_bound(x) is the first value ≥ x, upper_bound(x) the first value > x, begin() the smallest, rbegin() the largest. Iterators step to the next or previous value.

Reach for it when you need “the closest value to x” or “the smallest value still available” while inserting and deleting.

Sample problem

220. Contains Duplicate III ↗ Hard

Decide whether there are two different indices i and j with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff.

nums = [8,1,14,5,11], indexDiff = 2, valueDiff = 3
output = true   (14 and 11)

Why the solution works

For each index only the previous indexDiff values matter, so keep them in a sliding window.

The question for the window is “does it contain a value in the range [x − valueDiff, x + valueDiff]?”. A sorted set answers it with one lower_bound: find the smallest value ≥ x − valueDiff and check that it is ≤ x + valueDiff.

A hash set could not do this: it only finds exact values. The ordered set is what makes a range lookup O(log n) while values keep entering and leaving.

Complexity: O(n log k) time, O(k) memory, with k = indexDiff.

Watch out

  • On a multiset, erase(value) removes every copy. Erase an iterator to remove one.
  • Use the member s.lower_bound(x). The free function lower_bound(s.begin(), s.end(), x) is O(n) on a set.
  • Never dereference end() or step back from begin(): test first.
Watch it run

Try your own input

Practise on LeetCode