All oone data structure

Hash Table Linked List Design Doubly-Linked List

44.2% acceptance

Jan 13, 2026

2222

224

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts. Implement the AllOne class: AllOne() Initializes the object of the data structure. inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1. dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement. getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "". getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "". Note that each function must run in O(1) average time complexity.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashMap, BTreeMap, HashSet};

pub struct AllOne {
  key_count: HashMap<String, i32>,
  count_keys: BTreeMap<i32, HashSet<String>>,
}

impl AllOne {
  fn new() -> Self {
    AllOne {
      key_count: HashMap::new(),
      count_keys: BTreeMap::new(),
    }
  }
  
  fn inc(&mut self, key: String) {
    let old_count = self.key_count.get(&key).copied().unwrap_or(0);
    let new_count = old_count + 1;
    
    // Remove from old count bucket
    if old_count > 0 {
      if let Some(keys) = self.count_keys.get_mut(&old_count) {
        keys.remove(&key);
        if keys.is_empty() {
          self.count_keys.remove(&old_count);
        }
      }
    }
    
    // Add to new count bucket
    self.key_count.insert(key.clone(), new_count);
    self.count_keys.entry(new_count).or_insert_with(HashSet::new).insert(key);
  }
  
  fn dec(&mut self, key: String) {
    let old_count = *self.key_count.get(&key).unwrap();
    
    // Remove from old count bucket
    if let Some(keys) = self.count_keys.get_mut(&old_count) {
      keys.remove(&key);
      if keys.is_empty() {
        self.count_keys.remove(&old_count);
      }
    }
    
    if old_count == 1 {
      self.key_count.remove(&key);
    } else {
      let new_count = old_count - 1;
      self.key_count.insert(key.clone(), new_count);
      self.count_keys.entry(new_count).or_insert_with(HashSet::new).insert(key);
    }
  }
  
  fn get_max_key(&self) -> String {
    self.count_keys.iter().next_back()
      .and_then(|(_, keys)| keys.iter().next())
      .map(|s| s.clone())
      .unwrap_or_else(|| String::new())
  }
  
  fn get_min_key(&self) -> String {
    self.count_keys.iter().next()
      .and_then(|(_, keys)| keys.iter().next())
      .map(|s| s.clone())
      .unwrap_or_else(|| String::new())
  }
}