Problem Formulation & Constraints

You are given an integer limit and a 2D integer array queries of size $N \times 2$:

• There are limit + 1 balls labeled from $0$ to limit. Initially, all balls are uncolored.
• Each query is formatted as [ball, color], denoting that ball number ball is painted with color color.
• If ball was previously uncolored, it now has color color.
• If ball already held a color, its old color is overwritten by the new color.
• Return an integer array result of length $N$, where result[i] denotes the count of distinct colors active across all balls after query $i$.

Key Constraints: $1 \le limit \le 10^9$, $1 \le queries.length \le 10^5$. Because limit can reach $10^9$, allocating an array of size limit + 1 causes an immediate Out of Memory (OOM) error. The solution must rely strictly on sparse hash maps bounded by the number of queries ($N$).

Dual Hash Map Architecture & State Transitions

To evaluate the number of distinct colors in $O(1)$ time per query without rescanning, we maintain two complementary hash maps:

1. ballToColor (Map<Integer, Integer>): Maps each active ball ID to its current color.
2. colorFreq (Map<Integer, Integer>): Maps each active color to the number of balls currently painted that color.

State Transition Mechanics

For each query [ball, newColor]:

1. Check for Existing Color: If ballToColor.containsKey(ball):
   • Retrieve prevColor = ballToColor.get(ball).
   • If prevColor == newColor, no state transition occurs. The count remains unchanged.
   • Otherwise, decrement colorFreq[prevColor] by 1.
   • Critical Cleanup Step: If colorFreq[prevColor] == 0, remove prevColor from colorFreq completely.
2. Assign New Color: Update ballToColor[ball] = newColor.
3. Increment New Color Frequency: Increment colorFreq[newColor] by 1 (defaulting to 0 if not present).
4. Record Distinct Count: The number of unique active colors is simply colorFreq.size().

Multi-Language Implementations

1. Java Solution (Original Authentic Formulation)

import java.util.HashMap;

class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        int n = queries.length;
        int[] result = new int[n];
        HashMap<Integer, Integer> ballMap = new HashMap<>();
        HashMap<Integer, Integer> colorMap = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            int ball = queries[i][0];
            int color = queries[i][1];
            
            if (ballMap.containsKey(ball)) {
                int prevColor = ballMap.get(ball);
                colorMap.put(prevColor, colorMap.get(prevColor) - 1);
                
                if (colorMap.get(prevColor) == 0) {
                    colorMap.remove(prevColor);
                }
            }
            
            ballMap.put(ball, color);
            colorMap.put(color, colorMap.getOrDefault(color, 0) + 1);
            result[i] = colorMap.size();
        }
        return result;
    }
}

2. C++20 Optimal Solution

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> queryResults(int limit, std::vector<std::vector<int>>& queries) {
        int n = queries.size();
        std::vector<int> result(n);
        std::unordered_map<int, int> ballToColor;
        std::unordered_map<int, int> colorFreq;
        
        // Reserve bucket space to eliminate rehashing during high-volume query streams
        ballToColor.reserve(n);
        colorFreq.reserve(n);
        
        for (int i = 0; i < n; ++i) {
            int ball = queries[i][0];
            int color = queries[i][1];
            
            auto it = ballToColor.find(ball);
            if (it != ballToColor.end()) {
                int prevColor = it->second;
                if (--colorFreq[prevColor] == 0) {
                    colorFreq.erase(prevColor);
                }
            }
            
            ballToColor[ball] = color;
            colorFreq[color]++;
            result[i] = colorFreq.size();
        }
        
        return result;
    }
};

3. TypeScript Solution

function queryResults(limit: number, queries: number[][]): number[] {
    const n = queries.length;
    const result = new Int32Array(n);
    const ballToColor = new Map<number, number>();
    const colorFreq = new Map<number, number>();
    
    for (let i = 0; i < n; i++) {
        const [ball, color] = queries[i];
        
        if (ballToColor.has(ball)) {
            const prevColor = ballToColor.get(ball)!;
            const currentCount = colorFreq.get(prevColor)!;
            if (currentCount === 1) {
                colorFreq.delete(prevColor);
            } else {
                colorFreq.set(prevColor, currentCount - 1);
            }
        }
        
        ballToColor.set(ball, color);
        colorFreq.set(color, (colorFreq.get(color) ?? 0) + 1);
        result[i] = colorFreq.size;
    }
    
    return Array.from(result);
}

Complexity Analysis