3160. Find the Number of Distinct Colors Among the Balls LeetCode Solution

In this guide, you will get 3160. Find the Number of Distinct Colors Among the Balls LeetCode Solution with the best time and space complexity. The solution to Find the Number of Distinct Colors Among the Balls problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Find the Number of Distinct Colors Among the Balls solution in C++
  4. Find the Number of Distinct Colors Among the Balls solution in Java
  5. Find the Number of Distinct Colors Among the Balls solution in Python
  6. Additional Resources
3160. Find the Number of Distinct Colors Among the Balls LeetCode Solution image

Problem Statement of Find the Number of Distinct Colors Among the Balls

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:

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.

See also  834. Sum of Distances in Tree LeetCode Solution

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 <= 109
1 <= n == queries.length <= 105
queries[i].length == 2
0 <= queries[i][0] <= limit
1 <= queries[i][1] <= 109

Complexity Analysis

  • Time Complexity: O(q)
  • Space Complexity: O(q)

3160. Find the Number of Distinct Colors Among the Balls LeetCode Solution in C++

class Solution {
 public:
  vector<int> queryResults(int limit, vector<vector<int>>& queries) {
    vector<int> ans;
    unordered_map<int, int> ballToColor;
    unordered_map<int, int> colorCount;

    for (const vector<int>& query : queries) {
      const int ball = query[0];
      const int color = query[1];
      if (const auto it = ballToColor.find(ball); it != ballToColor.cend()) {
        const int prevColor = it->second;
        if (--colorCount[prevColor] == 0)
          colorCount.erase(prevColor);
      }
      ballToColor[ball] = color;
      ++colorCount[color];
      ans.push_back(colorCount.size());
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3160. Find the Number of Distinct Colors Among the Balls LeetCode Solution in Java

class Solution {
  public int[] queryResults(int limit, int[][] queries) {
    int[] ans = new int[queries.length];
    Map<Integer, Integer> ballToColor = new HashMap<>();
    Map<Integer, Integer> colorCount = new HashMap<>();

    for (int i = 0; i < queries.length; ++i) {
      final int ball = queries[i][0];
      final int color = queries[i][1];
      if (ballToColor.containsKey(ball)) {
        final int prevColor = ballToColor.get(ball);
        if (colorCount.merge(prevColor, -1, Integer::sum) == 0)
          colorCount.remove(prevColor);
      }
      ballToColor.put(ball, color);
      colorCount.merge(color, 1, Integer::sum);
      ans[i] = colorCount.size();
    }

    return ans;
  }
}
// code provided by PROGIEZ

3160. Find the Number of Distinct Colors Among the Balls LeetCode Solution in Python

class Solution:
  def queryResults(self, limit: int, queries: list[list[int]]) -> list[int]:
    ans = []
    ballToColor = {}
    colorCount = collections.Counter()

    for ball, color in queries:
      if ball in ballToColor:
        prevColor = ballToColor[ball]
        colorCount[prevColor] -= 1
        if colorCount[prevColor] == 0:
          del colorCount[prevColor]
      ballToColor[ball] = color
      colorCount[color] += 1
      ans.append(len(colorCount))

    return ans
# code by PROGIEZ

Additional Resources

See also  3110. Score of a String LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.