LeetCode Entry

3160. Find the Number of Distinct Colors Among the Balls

07.02.2025 medium 2025 kotlin rust

Running colors counter

3160. Find the Number of Distinct Colors Among the Balls medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/888

Problem TLDR

Running colors counter #medium #hashmap

Intuition

Store mappings: balls to colors, colors to balls. 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;
    }