Problem overview
The task is to build a collection of integers, initially empty, that supports three operations: insert adds one occurrence of a number, remove takes one occurrence away, and count says how many occurrences of a number are currently in the collection. The same number can be inserted several times.
In the example, 5, 2 and 5 are inserted, so count(5) gives 2. After remove(5), count(5) gives 1. Each operation must run in O(1) time and the collection may use O(n) space, where n is the number of inserted values.
Approach: a frequency table
A plain vector of numbers would make count a scan of every element and remove a search, both O(n). A hash map from a number to its number of occurrences makes all three operations constant time on average: insert adds 1 to the number's counter, remove subtracts 1, and count reads the counter.
Two details need care. A number that was never inserted has no entry, so count must report 0 instead of failing. And remove must never push a counter below zero, so removing a number that is absent, or whose count is already 0, does nothing.
Where the table lives
The functions here are associated functions of Solution: none of them takes self. They can't see any value that would carry the table around, so the table has to be a static. A plain static in Rust is immutable and, for a map, must be safe to share between threads. The usual answer is thread_local!, which creates a separate copy of the static for each thread, wrapped in a RefCell.
A RefCell allows changing its contents through a shared reference. Instead of the compiler, it checks the borrowing rules at run time: borrow() gives read access and borrow_mut() gives write access, and a conflicting borrow at the same moment panics. Each function here borrows once and lets the borrow end before returning, so no conflict can happen.
A thread-local static is used through FREQ.with(|f| ...). The closure receives a reference f to the RefCell, and whatever the closure returns is returned by with.
Step by step
- Declare the table inside
thread_local!asstatic FREQ: RefCell<HashMap<i32, i32>>, initialised withRefCell::new(HashMap::new()). The keys are the numbers and the values are their counts. - Write
count. InsideFREQ.with, borrow the map withborrow()and callget(&val). That returns anOption<&i32>.unwrap_or(&0)supplies a reference to 0 when the key is missing, and*copies the number out to return ani32. - Write
insert. Borrow mutably withborrow_mut(), callentry(val).or_insert(0)to get a mutable reference to the counter (creating it with 0 for a new number), and add 1 through*. - Guard
remove. The existing code borrows the map mutably and usesget_mut(&val)insideif let Some(c). When the number has no entry, nothing happens. When it has one,cis a&mut i32, and the lesson checks*c > 0, comparing the number and not the reference. - Decrement with
*c -= 1. Assigning through*cchanges the value stored inside the map.
The solution in Rust
use std::cell::RefCell;
use std::collections::HashMap;
thread_local! {
static FREQ: RefCell<HashMap<i32, i32>> = RefCell::new(HashMap::new());
}
impl Solution {
fn reset() {
FREQ.with(|f| f.borrow_mut().clear());
}
fn count(val: i32) -> i32 {
FREQ.with(|f| *f.borrow().get(&val).unwrap_or(&0))
}
fn insert(val: i32) {
FREQ.with(|f| *f.borrow_mut().entry(val).or_insert(0) += 1);
}
fn remove(val: i32) {
FREQ.with(|f| {
let mut m = f.borrow_mut();
if let Some(c) = m.get_mut(&val) {
if *c > 0 {
*c -= 1;
}
}
});
}
}
Rust details worth a closer look:
resetclears the table so that a new sequence of operations starts from an empty collection. It is not one of the three operations.- Fallback by reference.
getreturns a reference inside theOption, so the fallback given tounwrap_orhas to be a reference as well, hence&0. - Reading and the borrow. In
count, the dereference copies the integer out before the temporary borrow ends, which is why returning it is allowed. - Mutable borrow of the entry.
entry(val).or_insert(0)returns&mut i32. Without the*,+= 1would try to add to a reference and fail to compile. let mut m. The guard returned byborrow_mut()must be declaredmutso thatget_mutcan be called through it.- One copy per thread. A value inserted on one thread is invisible to another. This doesn't matter for a single-threaded program.
Complexity
Time: O(1) per operation on average. Each of insert, remove and count does one hash-map lookup or update. reset takes time proportional to the number of stored keys.
Space: O(n). The map holds one entry per distinct number. An entry whose count has dropped to 0 stays in the map, which keeps the code simple and doesn't affect the answers.
Edge cases and common mistakes
- Counting a number never inserted.
count(9)on an empty collection returns 0, thanks tounwrap_or(&0). Indexing the map with[]would panic. - Removing a number that is absent.
get_mutgivesNone, and nothing happens. - Removing too often. After 5 is inserted once, calling
remove(5)twice leaves the count at 0, not -1, because of the*c > 0check. - Comparing the reference.
c > 0doesn't compile, sincecis a&mut i32. Compare*c. - Holding a borrow too long. Calling
borrow_mut()while another borrow of the sameRefCellis alive panics at run time. Keep each borrow inside one function. - Negative numbers and zero are ordinary keys.
Testing
- Insert 5, 2, 5, then
count(5)gives 2. Afterremove(5)it gives 1. - On an empty collection,
count(9)gives 0. - Insert 5 once, remove it twice, and
count(5)gives 0. - After
reset(), every count is 0.
