Find the number of distinct colors among the balls

Array Hash Table Simulation

54.2% acceptance

Feb 24, 2026

765

You are given an integer limit and a 2D array queries of size n x 2. There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the form [x, y], you mark ball x with the color y. After each query, you need to find the number of colors among the balls. Return an array result of length n, where result[i] denotes the number of colors after ith query. Note that when answering a query, lack of a color will not be considered as a color.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn query_results(_limit: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
    use std::collections::HashMap;
    let mut ball_color: HashMap<i32, i32> = HashMap::new();
    let mut color_count: HashMap<i32, i32> = HashMap::new();
    let mut distinct = 0i32;
    let mut result = Vec::with_capacity(queries.len());

    for q in &queries {
      let x = q[0];
      let y = q[1];
      // Remove old color from x if it had one
      if let Some(&old_color) = ball_color.get(&x) {
        let cnt = color_count.entry(old_color).or_insert(0);
        *cnt -= 1;
        if *cnt == 0 {
          distinct -= 1;
        }
      }
      // Set new color y for ball x
      ball_color.insert(x, y);
      let cnt = color_count.entry(y).or_insert(0);
      if *cnt == 0 {
        distinct += 1;
      }
      *cnt += 1;
      result.push(distinct);
    }
    result
  }
}