visual walkthrough
All O`one Data Structure
O(1) inc/dec/min/max with a bucket list.
The idea
Counts only ever change by one. So if keys are grouped into buckets by count and the buckets are kept in order, a key always moves to the bucket right next to its current one.
With the buckets in a doubly linked list, the smallest count is at the head and the largest at the tail: min and max are instant.
Complexity
| approach | time | space |
|---|---|---|
| Map and scan | O(n) for max/min | O(n) |
| Linked list of count buckets | O(1) per op | O(n) |