Find the Number of Distinct Colors Among the Balls

MediumArrayHash TableSimulation

Solution

balls는 현재 공의 색깔을 저장하고, colors는 각 색깔의 개수 저장
queries를 반복하면서, 주어진 공의 이전 색깔에 대한 개수를 줄이고, 바뀐 색깔의 개수를 추가
만약 이전의 색깔의 개수가 0보다 작아지면, delete를 사용하여, Map에서 삭제
Map의 size를 통해, 현재 총 색깔의 개수를 구할 수 있다.

export function queryResults(limit: number, queries: number[][]): number[] {
  const balls = new Map<number, number>();
  const colors = new Map<number, number>([]);
 
  const answer: number[] = [];
  for (const [ball, color] of queries) {
    const prevColor = balls.get(ball) ?? 0;
    if (prevColor !== 0) {
      const prevCount = colors.get(prevColor) ?? 0;
      if (prevCount <= 1) {
        colors.delete(prevColor);
      } else {
        colors.set(prevColor, prevCount - 1);
      }
    }
 
    balls.set(ball, color);
    colors.set(color, (colors.get(color) ?? 0) + 1);
    answer.push(colors.size);
  }
  return answer;
}

Complexity

Time: $O(queries.length)$ $O (q u er i es . l e n g t h)$
- queries를 반복하기 때문에, queries의 길이만큼의 시간 복잡도가 소요.
Space: $O(limit + distinct\ color)$ $O (l imi t + d i s t in c t co l or)$
- balls는 최대 limit의 공간 복잡도를 사용, colors는 queries의 고유한 색깔의 개수만큼의 공간 복잡도를 사용

LeetCode

Find the Number of Distinct Colors Among the Balls

https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls