Medium
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:
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 <= 109
1 <= n == queries.length <= 105
queries[i].length == 2
0 <= queries[i][0] <= limit
1 <= queries[i][1] <= 109
class Solution {
fun queryResults(ignoredLimit: Int, queries: Array<IntArray>): IntArray {
val ballToColor: MutableMap<Int, Int> = HashMap()
val colorToCnt: MutableMap<Int, Int> = HashMap()
val ret = IntArray(queries.size)
var i = 0
while (i < queries.size) {
val ball = queries[i][0]
val color = queries[i][1]
if (ballToColor.containsKey(ball)) {
val oldColor = ballToColor[ball]!!
val oldColorCnt = colorToCnt[oldColor]!!
if (oldColorCnt >= 2) {
colorToCnt[oldColor] = oldColorCnt - 1
} else {
colorToCnt.remove(oldColor)
}
}
ballToColor[ball] = color
colorToCnt[color] = colorToCnt.getOrDefault(color, 0) + 1
ret[i] = colorToCnt.size
i += 1
}
return ret
}
}