Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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.
Example 1:
Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Explanation:
Example 2:
Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Explanation:
Constraints:
1 <= limit <= 1091 <= n == queries.length <= 105queries[i].length == 20 <= queries[i][0] <= limit1 <= queries[i][1] <= 109Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
4 [[1,4],[2,5],[1,3],[3,4]]
4 [[0,1],[1,2],[2,2],[3,4],[4,5]]
maximum-number-of-balls-in-a-box)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3160: Find the Number of Distinct Colors Among the Balls
class Solution {
public int[] queryResults(int limit, int[][] queries) {
Map<Integer, Integer> g = new HashMap<>();
Map<Integer, Integer> cnt = new HashMap<>();
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
int x = queries[i][0], y = queries[i][1];
cnt.merge(y, 1, Integer::sum);
if (g.containsKey(x) && cnt.merge(g.get(x), -1, Integer::sum) == 0) {
cnt.remove(g.get(x));
}
g.put(x, y);
ans[i] = cnt.size();
}
return ans;
}
}
// Accepted solution for LeetCode #3160: Find the Number of Distinct Colors Among the Balls
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
}
# Accepted solution for LeetCode #3160: Find the Number of Distinct Colors Among the Balls
class Solution:
def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
g = {}
cnt = Counter()
ans = []
for x, y in queries:
cnt[y] += 1
if x in g:
cnt[g[x]] -= 1
if cnt[g[x]] == 0:
cnt.pop(g[x])
g[x] = y
ans.append(len(cnt))
return ans
// Accepted solution for LeetCode #3160: Find the Number of Distinct Colors Among the Balls
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3160: Find the Number of Distinct Colors Among the Balls
// class Solution {
// public int[] queryResults(int limit, int[][] queries) {
// Map<Integer, Integer> g = new HashMap<>();
// Map<Integer, Integer> cnt = new HashMap<>();
// int m = queries.length;
// int[] ans = new int[m];
// for (int i = 0; i < m; ++i) {
// int x = queries[i][0], y = queries[i][1];
// cnt.merge(y, 1, Integer::sum);
// if (g.containsKey(x) && cnt.merge(g.get(x), -1, Integer::sum) == 0) {
// cnt.remove(g.get(x));
// }
// g.put(x, y);
// ans[i] = cnt.size();
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #3160: Find the Number of Distinct Colors Among the Balls
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.