DDSA Solutions

3160. Find the Number of Distinct Colors Among the Balls

MediumView on LeetCode
ArrayHash TableSimulation
Time: O(q)
Space: O(n + q)

Problem Overview

Count queries where XOR of element at index equals query value.

Intuition

Count queries where XOR of element at index equals query value. Maintain current values and XOR results.

Algorithm

  1. 1Simulate: for each query (idx, val): update value[idx], XOR[idx] ^= old_val ^ val. Count matching queries.

Common Pitfalls

  • •Track current values to compute XOR changes. Count pairs matching target after each update.
3160.cs
C#
// Approach: HashMap ball→color and color→count; swap colors updating counts; track distinct color count.
// Time: O(q) Space: O(n + q)

public class Solution
{
    public int[] QueryResults(int limit, int[][] queries)
    {
        int n = queries.Length;
        int[] ans = new int[n];

        Dictionary<int, int> ballToColor = new Dictionary<int, int>();
        Dictionary<int, int> colorCount = new Dictionary<int, int>();

        for (int i = 0; i < n; i++)
        {
            int ball = queries[i][0];
            int color = queries[i][1];

            if (ballToColor.TryGetValue(ball, out int prevColor))
            {
                if (--colorCount[prevColor] == 0)
                    colorCount.Remove(prevColor);
            }
            ballToColor[ball] = color;

            if (colorCount.ContainsKey(color))
                colorCount[color]++;
            else
                colorCount[color] = 1;

            ans[i] = colorCount.Count;
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems