Find the Number of Distinct Colors Among the Balls solution and explanation
Google
9 more videos on this problem
Find the Number of Distinct Colors Among the Balls | 2 Approaches | Leetcode 3160 | codestorywithMIKcodestorywithMIK · 24:27 · 9K views
Find the Number of Distinct Colors Among the Balls | Leetcode 3160Techdose · 15:28 · 7K views
3160. Find the Number of Distinct Colors Among the Balls | leetcode daily challenge | shashcode dsaShashCode · 14:40 · 2K views
3160. Find the Number of Distinct Colors Among the Balls | Leetcode Daily ChallengeEthos Typos · 9:05 · 2K views
3160. Find the Number of Distinct Colors Among the Balls (Leetcode Medium)Programming Live with Larry · 7:32 · 649 views
Leetcode 3160 | Find the Number of Distinct Colors Among the Balls | Leetcode Biweekly Contest 131Road To FAANG · 9:47 · 637 views
LeetCode 3160 Find the Number of Distinct Colors Among the Balls | Hash TableCode Harmony · 16:39 · 294 views
🔍 LeetCode 3160 - Find the Number of Distinct Colors Among the Balls (Best Java Solution 🚀)RAHUL VIJAYAN · 13:09 · 230 views
Find the Number of Distinct Colors Among the Balls - Leetcode 3160 - PythonTim Huang · 4:34 · 175 views
3160. Find the Number of Distinct Colors Among the Balls | Hash Map | Array | LeetcodeRapid Syntax · 13:34 · 107 views
The problem
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 distinct colors among the balls.
Return an array result of length n, where result[i] denotes the number of distinct colors after ith query.
Note that when answering a query, lack of a color will not be considered as a color.
Example 1:
Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Explanation:
- After query 0, ball 1 has color 4.
- After query 1, ball 1 has color 4, and ball 2 has color 5.
- After query 2, ball 1 has color 3, and ball 2 has color 5.
- After query 3, ball 1 has color 3, ball 2 has color 5, and ball 3 has color 4.
Example 2:
Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Explanation:
- After query 0, ball 0 has color 1.
- After query 1, ball 0 has color 1, and ball 1 has color 2.
- After query 2, ball 0 has color 1, and balls 1 and 2 have color 2.
- After query 3, ball 0 has color 1, balls 1 and 2 have color 2, and ball 3 has color 4.
- After query 4, ball 0 has color 1, balls 1 and 2 have color 2, ball 3 has color 4, and ball 4 has color 5.
Constraints:
1 <= limit <= 1091 <= n == queries.length <= 105queries[i].length == 20 <= queries[i][0] <= limit1 <= queries[i][1] <= 109
Approach overview
Problem Overview: You receive queries that assign a color to a specific ball. After each assignment, you must report how many distinct colors currently exist among all colored balls. Balls may change colors multiple times, so the solution must correctly update color counts as assignments overwrite previous ones.
Approach 1: HashMap to Track Ball and Color Frequency (O(n) time, O(n) space)
Use two hash maps. The first maps ball -> color, storing the current color of each ball. The second maps color -> frequency, tracking how many balls currently use that color. For every query, check if the ball already has a color. If it does, decrement the frequency of the old color and remove it from the map when the count reaches zero. Then assign the new color, increment its frequency, and record the number of distinct colors as colorFrequency.size(). Each operation is constant time because hash lookups, insertions, and deletions are O(1) on average. This approach handles arbitrary ball IDs and color values efficiently and is the standard solution using Hash Table techniques combined with simple Simulation.
Approach 2: Arrays for Color Frequency (O(n) time, O(k) space)
If the maximum color value is reasonably bounded, replace the color-frequency hash map with an array. Maintain an array colorCount[color] that tracks how many balls currently have that color. You still keep a structure mapping ball -> color to detect previous assignments. When processing a query, decrement the previous color count, update the new color count, and maintain a running integer storing the number of distinct colors. Increment it when a color count transitions from 0 to 1, and decrement it when a count drops from 1 to 0. Array indexing is slightly faster than hashing and reduces overhead, making this a good optimization when color limits are known. The algorithm still processes each query once, so the total time remains O(n). This approach relies on simple operations over Array structures.
Recommended for interviews: The HashMap approach is what most interviewers expect. It works for large or sparse color ranges and demonstrates proper handling of state updates and frequency tracking. The array optimization is useful when constraints guarantee small color values, but the hash-based solution shows stronger general problem-solving skills.
Approach 1: Using a HashMap or Dictionary to Track Colors
This approach uses a HashMap (or Dictionary in Python) to map each ball to its current color. By iterating over the queries, you update the color of each specified ball in the map. To determine the distinct colors, you can utilize a HashSet (or Set in Python) which keeps track of all unique values in the HashMap.
def distinct_colors(limit, queries):
ball_to_color = {}
color_set = set()
results = []
for ball, color in queries:
if ball in ball_to_color:
color_set.discard(ball_to_color[ball])
ball_to_color[ball] = color
color_set.add(color)
results.append(len(color_set))
return results
queries = [(0, 1), (1, 2), (2, 2), (3, 4), (4, 5)]
limit = 4
print(distinct_colors(limit, queries))import java.util.*;
public class DistinctColors {
public static List<Integer> distinctColors(int limit, int[][] queries) {
Map<Integer, Integer> ballToColor = new HashMap<>();
Set<Integer> colorSet = new HashSet<>();
List<Integer> results = new ArrayList<>();
for (int[] query : queries) {
int ball = query[0];
int color = query[1];
if (ballToColor.containsKey(ball)) {
colorSet.remove(ballToColor.get(ball));
}
ballToColor.put(ball, color);
colorSet.add(color);
results.add(colorSet.size());
}
return results;
}
public static void main(String[] args) {
int[][] queries = {{0, 1}, {1, 2}, {2, 2}, {3, 4}, {4, 5}};
int limit = 4;
List<Integer> result = distinctColors(limit, queries);
System.out.println(result);
}
}#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
std::vector<int> distinctColors(int limit, std::vector<std::pair<int, int>> &queries) {
std::unordered_map<int, int> ballToColor;
std::unordered_set<int> colorSet;
std::vector<int> results;
for (const auto &query : queries) {
int ball = query.first;
int color = query.second;
if (ballToColor.count(ball)) {
colorSet.erase(ballToColor[ball]);
}
ballToColor[ball] = color;
colorSet.insert(color);
results.push_back(colorSet.size());
}
return results;
}
int main() {
std::vector<std::pair<int, int>> queries = {{0, 1}, {1, 2}, {2, 2}, {3, 4}, {4, 5}};
int limit = 4;
std::vector<int> result = distinctColors(limit, queries);
for (int res : result) {
std::cout << res << " ";
}
std::cout << std::endl;
return 0;
}function distinctColors(limit, queries) {
const ballToColor = new Map();
const colorSet = new Set();
const results = [];
for (const [ball, color] of queries) {
if (ballToColor.has(ball)) {
colorSet.delete(ballToColor.get(ball));
}
ballToColor.set(ball, color);
colorSet.add(color);
results.push(colorSet.size);
}
return results;
}
const queries = [[0, 1], [1, 2], [2, 2], [3, 4], [4, 5]];
const limit = 4;
console.log(distinctColors(limit, queries));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_BALLS 100000 // Assumes a reasonable limit for balls handled in an example
int distinctColors(int limit, int queries[][2], int queriesSize) {
int *ballColors = (int *)calloc(limit + 1, sizeof(int));
bool *colorPresence = (bool *)calloc(MAX_BALLS, sizeof(bool));
int distinctCount = 0;
int *result = (int *)malloc(queriesSize * sizeof(int));
for (int i = 0; i < queriesSize; i++) {
int x = queries[i][0];
int y = queries[i][1];
if (ballColors[x] != 0) { // If ball was already colored.
if (!colorPresence[y]) {
distinctCount++;
colorPresence[y] = true;
}
if (colorPresence[ballColors[x]]) {
if (--colorPresence[ballColors[x]] == 0) {
distinctCount--;
}
}
} else {
if (!colorPresence[y]) {
distinctCount++;
colorPresence[y] = true;
}
}
ballColors[x] = y; // Set the new color.
result[i] = distinctCount;
}
// You may want to clean up if necessary
free(ballColors);
free(colorPresence);
return result;
}
int main() {
int queries[][2] = {{0,1}, {1,2}, {2,2}, {3,4}, {4,5}};
int queriesSize = sizeof(queries) / sizeof(queries[0]);
int limit = 4;
int *result = distinctColors(limit, queries, queriesSize);
for (int i = 0; i < queriesSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class DistinctColors {
public static List<int> DistinctColors(int limit, int[][] queries) {
Dictionary<int, int> ballToColor = new Dictionary<int, int>();
HashSet<int> colorSet = new HashSet<int>();
List<int> results = new List<int>();
foreach (int[] query in queries) {
int ball = query[0];
int color = query[1];
if (ballToColor.ContainsKey(ball)) {
colorSet.Remove(ballToColor[ball]);
}
ballToColor[ball] = color;
colorSet.Add(color);
results.Add(colorSet.Count);
}
return results;
}
public static void Main() {
int[][] queries = new int[][] { new int[]{0, 1}, new int[]{1, 2}, new int[]{2, 2}, new int[]{3, 4}, new int[]{4, 5} };
int limit = 4;
List<int> result = DistinctColors(limit, queries);
Console.WriteLine(string.Join(" ", result));
}
}The Python solution works similarly, using a dictionary to keep track of the color assigned to each ball and a set to store distinct colors. During each query, the current color of a ball is replaced in the dictionary, and the distinct color count is maintained efficiently by adding or removing colors from the set.
Time Complexity: O(n), where n is the number of queries, as each query operation is handled in constant time.
Space Complexity: O(m), for the set storing the distinct colors.
Approach 2: Using Arrays for Color Frequency
This approach leverages arrays to keep track of the last-assigned color for each ball and the frequency of each color used. By maintaining these two structures, we can efficiently query the number of distinct colors active at any moment.
def count_distinct_colors(limit, queries):
ball_colors = [0] * (limit + 1)
color_frequency = {}
distinct_count = 0
result = []
for ball, color in queries:
if ball_colors[ball] != 0:
color_frequency[ball_colors[ball]] -= 1
if color_frequency[ball_colors[ball]] == 0:
distinct_count -= 1
ball_colors[ball] = color
color_frequency[color] = color_frequency.get(color, 0) + 1
if color_frequency[color] == 1:
distinct_count += 1
result.append(distinct_count)
return result
queries = [(0, 1), (1, 2), (2, 2), (3, 4), (4, 5)]
limit = 4
print(count_distinct_colors(limit, queries))import java.util.*;
public class Solution {
public static List<Integer> countDistinctColors(int limit, int[][] queries) {
int[] ballColors = new int[limit + 1];
Map<Integer, Integer> colorFrequency = new HashMap<>();
int distinctCount = 0;
List<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int ball = query[0];
int color = query[1];
if (ballColors[ball] != 0) {
colorFrequency.put(ballColors[ball], colorFrequency.get(ballColors[ball]) - 1);
if (colorFrequency.get(ballColors[ball]) == 0) {
distinctCount--;
}
}
ballColors[ball] = color;
colorFrequency.put(color, colorFrequency.getOrDefault(color, 0) + 1);
if (colorFrequency.get(color) == 1) {
distinctCount++;
}
result.add(distinctCount);
}
return result;
}
public static void main(String[] args) {
int[][] queries = {{0, 1}, {1, 2}, {2, 2}, {3, 4}, {4, 5}};
int limit = 4;
List<Integer> result = countDistinctColors(limit, queries);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <unordered_set>
std::vector<int> countDistinctColors(int limit, std::vector<std::pair<int, int>> &queries) {
std::vector<int> ballColors(limit + 1, 0);
std::vector<int> colorFrequency(queries.size() + 1, 0); // slightly oversized
int distinctCount = 0;
std::vector<int> result;
for (const auto &query : queries) {
int ball = query.first;
int color = query.second;
if (ballColors[ball] != 0) {
if (--colorFrequency[ballColors[ball]] == 0) {
--distinctCount;
}
}
ballColors[ball] = color;
if (++colorFrequency[color] == 1) {
++distinctCount;
}
result.push_back(distinctCount);
}
return result;
}
int main() {
std::vector<std::pair<int, int>> queries = {{0, 1}, {1, 2}, {2, 2}, {3, 4}, {4, 5}};
int limit = 4;
std::vector<int> result = countDistinctColors(limit, queries);
for (int res : result) {
std::cout << res << " ";
}
std::cout << std::endl;
return 0;
}function countDistinctColors(limit, queries) {
const ballColors = Array(limit + 1).fill(0);
const colorFrequency = new Map();
let distinctCount = 0;
const results = [];
for (const [ball, color] of queries) {
if (ballColors[ball] !== 0) {
const oldColor = ballColors[ball];
colorFrequency.set(oldColor, colorFrequency.get(oldColor) - 1);
if (colorFrequency.get(oldColor) === 0) {
distinctCount--;
}
}
ballColors[ball] = color;
colorFrequency.set(color, (colorFrequency.get(color) || 0) + 1);
if (colorFrequency.get(color) === 1) {
distinctCount++;
}
results.push(distinctCount);
}
return results;
}
const queries = [[0, 1], [1, 2], [2, 2], [3, 4], [4, 5]];
const limit = 4;
console.log(countDistinctColors(limit, queries));#include <stdio.h>
#include <stdlib.h>
#define MAX_COLORS 100000 // assumed max unique colors for example
int* countDistinctColors(int limit, int queries[][2], int queriesSize) {
int *ballColors = (int *)calloc(limit + 1, sizeof(int));
int *colorFreq = (int *)calloc(MAX_COLORS, sizeof(int));
int distinctCount = 0;
int *result = (int *)malloc(queriesSize * sizeof(int));
for (int i = 0; i < queriesSize; ++i) {
int ball = queries[i][0];
int color = queries[i][1];
if (ballColors[ball] > 0) {
if (--colorFreq[ballColors[ball]] == 0) {
distinctCount--;
}
}
ballColors[ball] = color;
if (++colorFreq[color] == 1) {
distinctCount++;
}
result[i] = distinctCount;
}
free(ballColors);
free(colorFreq);
return result;
}
int main() {
int queries[][2] = {{0,1}, {1,2}, {2,2}, {3,4}, {4,5}};
int queriesSize = sizeof(queries) / sizeof(queries[0]);
int limit = 4;
int* result = countDistinctColors(limit, queries, queriesSize);
for (int i = 0; i < queriesSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private class ColorFrequency {
public int Count { get; set; } = 0;
}
public static List<int> CountDistinctColors(int limit, int[][] queries) {
int[] ballColors = new int[limit + 1];
Dictionary<int, ColorFrequency> colorFrequency = new Dictionary<int, ColorFrequency>();
int distinctCount = 0;
List<int> result = new List<int>();
foreach (int[] query in queries) {
int ball = query[0];
int color = query[1];
if (ballColors[ball] != 0) {
ColorFrequency freq = colorFrequency[ballColors[ball]];
freq.Count--;
if (freq.Count == 0) {
distinctCount--;
}
}
ballColors[ball] = color;
if (!colorFrequency.ContainsKey(color)) {
colorFrequency[color] = new ColorFrequency();
}
if (colorFrequency[color].Count == 0) {
distinctCount++;
}
colorFrequency[color].Count++;
result.Add(distinctCount);
}
return result;
}
public static void Main(string[] args) {
int[][] queries = new int[][] { new int[]{0, 1}, new int[]{1, 2}, new int[]{2, 2}, new int[]{3, 4}, new int[]{4, 5} };
int limit = 4;
List<int> result = CountDistinctColors(limit, queries);
Console.WriteLine(string.Join(" ", result));
}
}The Python code employs two straightforward structures: a list for storing ball's colors and a dictionary for tracking the occurrence of each color. It results in an effective computation of distinct colors in response to each query.
Time Complexity: O(n), where n is the number of queries, owing to constant-time lookup and update operations for each ball.
Space Complexity: O(m + k), where m is number of balls and k is the number of unique color records created.
Approach 3: Double Hash Tables
We use a hash table g to record the color of each ball, and another hash table cnt to record the count of each color.
Next, we traverse the array queries. For each query (x, y), we increase the count of color y by 1, then check whether ball x has been colored. If it has, we decrease the count of the color of ball x by 1. If the count drops to 0, we remove it from the hash table cnt. Then, we update the color of ball x to y, and add the current size of the hash table cnt to the answer array.
After the traversal, we return the answer array.
The time complexity is O(m), and the space complexity is O(m), where m is the length of the array queries.
function queryResults(limit: number, queries: number[][]): number[] {
const g = new Map<number, number>();
const cnt = new Map<number, number>();
const ans: number[] = [];
for (const [x, y] of queries) {
cnt.set(y, (cnt.get(y) ?? 0) + 1);
if (g.has(x)) {
const v = g.get(x)!;
cnt.set(v, cnt.get(v)! - 1);
if (cnt.get(v) === 0) {
cnt.delete(v);
}
}
g.set(x, y);
ans.push(cnt.size);
}
return ans;
}func queryResults(limit int, queries [][]int) (ans []int) {
g := map[int]int{}
cnt := map[int]int{}
for _, q := range queries {
x, y := q[0], q[1]
cnt[y]++
if v, ok := g[x]; ok {
cnt[v]--
if cnt[v] == 0 {
delete(cnt, v)
}
}
g[x] = y
ans = append(ans, len(cnt))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a HashMap or Dictionary to Track Colors | Time Complexity: O(n), where n is the number of queries, as each query operation is handled in constant time. Space Complexity: O(m), for the set storing the distinct colors. |
| Using Arrays for Color Frequency | Time Complexity: O(n), where n is the number of queries, owing to constant-time lookup and update operations for each ball. Space Complexity: O(m + k), where m is number of balls and k is the number of unique color records created. |
| Double Hash Tables | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap for Ball Color + Color Frequency | O(n) | O(n) | General case when ball IDs and colors may be large or sparse |
| Array for Color Frequency | O(n) | O(k) | When color values are bounded and an array is more memory‑efficient |
Frequently asked questions
Is Find the Number of Distinct Colors Among the Balls easy or hard?
Find the Number of Distinct Colors Among the Balls is categorized as a Medium difficulty problem. The challenge comes from correctly updating counts when a ball changes colors and ensuring distinct colors are tracked efficiently using hash maps.
Find the Number of Distinct Colors Among the Balls Python/Java solution
Python and Java implementations typically use dictionaries or HashMap structures. The algorithm updates ball-to-color mappings and maintains a color frequency map to track distinct colors after every query. Each update is O(1) on average, producing an O(n) overall solution.
How to solve Find the Number of Distinct Colors Among the Balls in O(n)?
Process each query once while maintaining two structures: a map from ball to its current color and a frequency map for colors. When a ball gets a new color, decrement the old color frequency and increment the new one. Track the number of colors with non-zero frequency to output the distinct count after each update.
What is the best approach for Find the Number of Distinct Colors Among the Balls?
The best approach uses two hash maps: one mapping each ball to its current color and another tracking the frequency of each color. When a ball changes color, decrease the old color count and increase the new one, removing colors with zero frequency. This keeps the number of distinct colors available in O(1) time per query and results in O(n) total complexity.
Is Find the Number of Distinct Colors Among the Balls asked at Google/Amazon/Meta?
Problems involving dynamic frequency tracking with hash maps are common in interviews at companies like Google, Amazon, and Meta. Variants that require maintaining counts during updates appear frequently in coding rounds because they test understanding of hash tables and state management.
What data structure is used in Find the Number of Distinct Colors Among the Balls?
The primary data structure is a hash table (dictionary). One hash table maps ball IDs to their current colors, while another tracks how many balls share each color. Some optimized solutions replace the color-frequency map with an array when color values are bounded.
What is the time complexity of Find the Number of Distinct Colors Among the Balls?
The optimal solution runs in O(n) time where n is the number of queries. Each query performs constant-time hash map operations such as lookup, insert, and update. Space complexity is O(n) in the worst case because each ball and color may need to be stored.