# 07.02.2025 [3160. Find the Number of Distinct Colors Among the Balls]
Running colors counter #medium #hashmap
07.02.2025
3160. Find the Number of Distinct Colors Among the Balls medium blog post substack youtube
Join me on Telegram
Problem TLDR
Running colors counter #medium #hashmap
Intuition
Store mappings: balls to colors, colors to balls. The results
are colors size.
Approach
we can only store frequencies of colors
theoretically we can find a perfect hash function to just store [hash(x)] in min(limit, 10^5) array
we can first collect uniq balls and colors, and use binary search in them instead of a hash map
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(n)$$
Code
fun queryResults(limit: Int, queries: Array<IntArray>) = {
val f = HashMap<Int, Int>(); val bc = HashMap<Int, Int>()
queries.map { (b, c) ->
bc[b]?.let { f[it] = f[it]!! - 1; if (f[it]!! < 1) f -= it }
bc[b] = c; f[c] = 1 + (f[c] ?: 0); f.size
}
}()
pub fn query_results(limit: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut f = HashMap::new(); let mut bc = f.clone();
queries.iter().map(|q| { let (b, c) = (q[0], q[1]);
if let Some(&c) = bc.get(&b)
{ *f.entry(c).or_default() -= 1; if f[&c] < 1 { f.remove(&c); }}
bc.insert(b, c); *f.entry(c).or_default() += 1; f.len() as i32
}).collect()
}
vector<int> queryResults(int limit, vector<vector<int>>& q) {
unordered_map<int, int>f, bc; vector<int> res;
for (auto& p: q) bc.count(p[0]) && !--f[bc[p[0]]] && f.erase(bc[p[0]]),
bc[p[0]] = p[1], f[p[1]]++, res.push_back(size(f));
return res;
}