2103. Rings and Rods

EasyHash TableString

Problem Description

In this problem, we are dealing with n rings of three possible colors: red, green, or blue. These rings are placed on ten rods that are numbered from 0 to 9. We need to determine the number of rods that have at least one ring of each color on them.

We're given a string rings, which is twice as long as the number of rings since it contains pairs of characters. Each pair consists of a color character ('R', 'G', or 'B') followed by a digit character ('0' through '9') that represents the rod number on which the ring is placed. For example, if the string is "R3G2B1", it means we have a red ring on rod 3, a green ring on rod 2, and a blue ring on rod 1.

The task is to parse this string, arrange the rings according to their rods and colors, and finally count how many rods have a full set of all three colors.

Intuition

To address this problem, we need to organize the rings in a manner that easily lets us count the rods with a full set of colors. A good approach for such organization issues is to use a hash table, in this case in the form of a dictionary.

Here's the step-by-step intuition:

Create a hash table to keep track of the rings on each rod. In Python, we can use a dictionary (mp) where each key is a rod number and each value is a set of colors on that rod.
Iterate through the rings string, taking two characters at a time (since the rings are described by pairs of characters).
The first character of the pair represents the color of the ring, and the second character represents the rod it is placed on.
For each pair, add the ring color to the set that corresponds to the rod number in our hash table.
Since a set automatically handles duplicates (it only keeps unique items), we don't need to worry about counting multiple rings of the same color on the same rod.
Once we have processed all the pairs, we count how many rods (keys in the dictionary) have all three colors in their associated set of colors.
There should be exactly three colors in a set to indicate that a rod has a full set.

The solution code implements exactly this process using a defaultdict of sets from Python's collections module. This defaultdict is useful because it automatically creates a new set for a new rod key.

Solution Approach

The solution uses a defaultdict from Python's collections module, which is a subclass of the built-in dict that is provided with a default type when a key does not exist. In this case, the default type is set. This choice of data structure is likely because sets in Python handle uniqueness automatically and provide an efficient way to store the colors associated with each rod without duplicates.

Here is the breakdown of the solution algorithm:

A defaultdict called mp where keys will be integers corresponding to rod numbers (0 to 9), and the values will be sets that store the color characters ('R', 'G', 'B').
The input rings string is parsed two characters at a time with a for loop that starts at index 1 and increments by 2 to ensure that we look at every color-position pair. This loop iterates over the indices of the rod characters.
```
for i in range(1, len(rings), 2):
```
On each iteration, the first character (rings[i - 1]) represents the color of the ring, and the second character (rings[i]) converted to an integer, represents the rod number.
The color character is added to the set of colors corresponding to the rod number in our defaultdict. Since we are using a set, if the same color is added again to the same rod, it won't change the set contents because of the uniqueness constraint of the set.
```
c = int(rings[i])
mp[c].add(rings[i - 1])
```
After all pairs are processed, we count the number of entries in mp whose values are sets with a length of 3. This length check ensures that a rod has all three colors ('R', 'G', and 'B'). We use a generator expression within the sum function to do this count concisely.
```
return sum(len(v) == 3 for v in mp.values())
```

Essentially, this solution capitalizes on the Python set and defaultdict behavior to model the problem as a simple counting problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the solution approach described above. Consider the string rings = "B0R0G0B9R9G9". This string means we have rings of the following colors on the corresponding rods: blue, red, and green on rod 0, and blue, red, and green on rod 9.

Now, let's follow the steps outlined in the solution approach:

Initialize a defaultdict of sets, mp.
We process the rings string two characters at a time. For the first two characters, 'B0', we add the color 'B' (blue) to the set associated with rod 0 in mp.
For the next two characters, 'R0', we add the color 'R' (red) to the set for rod 0 in mp.
Continuing this way, 'G0' adds the color 'G' (green) to the set for rod 0.
At this point, the set for rod 0 contains all three colors: {'B', 'R', 'G'}.
For the characters 'B9', 'R9', and 'G9', we add each of the three colors to the set for rod 9 in mp, resulting in another set with all three colors: {'B', 'R', 'G'}.
Now that we've processed the entire string, we have a defaultdict mp that looks like this:

{
    0: {'B', 'R', 'G'},
    9: {'B', 'R', 'G'}
}

The final step is to count the number of entries in mp with sets of length 3. Both rods 0 and 9 have sets of 3 unique colors, indicating a complete set of colors.
Thus, we count 2 rods that have at least one ring of each color, and the final result would be 2 for this example.

Following these steps with actual code will produce the expected result, demonstrating that the solution corrects the problem.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def countPoints(self, rings: str) -> int:
5        # Initialize a dictionary to hold sets of colors for each rod position
6        rod_to_colors = defaultdict(set)
7      
8        # Iterate over each color-position pair
9        for i in range(1, len(rings), 2):
10            # Retrieve the position of the rod by converting the string number to int
11            rod_position = int(rings[i])
12          
13            # Add the color (denoted by a letter) to the set of colors for this rod
14            rod_to_colors[rod_position].add(rings[i - 1])
15      
16        # Count the rods which have exactly 3 different colors (R, G, B)
17        # and return the total count
18        return sum(len(colors) == 3 for colors in rod_to_colors.values())
19

1class Solution {
2    // Method to count the number of rods that have all three colors of rings
3    public int countPoints(String rings) {
4        // Initialize a map to store the rings on each rod with rod number as key
5        Map<Integer, Set<Character>> rodToRingsMap = new HashMap<>();
6
7        // Iterate over the string to populate the map with rods and their rings
8        for (int i = 1; i < rings.length(); i += 2) {
9            int rodNumber = rings.charAt(i) - '0'; // Get the rod number from the string
10            // Add the ring color to the set associated with the current rod
11            // If the rod does not exist in the map, it initializes with a new HashSet
12            rodToRingsMap.computeIfAbsent(rodNumber, k -> new HashSet<>()).add(rings.charAt(i - 1));
13        }
14
15        int count = 0; // Counter for rods with all three colors
16        // Loop through the values of the map
17        for (Set<Character> ringsOnRod : rodToRingsMap.values()) {
18            // If a rod has all three colors (R, G, B), increment the counter
19            if (ringsOnRod.size() == 3) {
20                count++;
21            }
22        }
23
24        // Return the total count of rods with all three ring colors
25        return count;
26    }
27}
28

1#include <unordered_map>
2#include <unordered_set>
3#include <string>
4
5class Solution {
6public:
7    int countPoints(string rings) {
8        // Create a map to store the sets of rings for each rod
9        unordered_map<int, unordered_set<char>> rodToRingsMap;
10
11        // Iterate through the string, considering pairs of ring color and rod
12        for (int i = 1; i < rings.size(); i += 2) {
13            // Convert the rod character to an integer
14            // '0' character has an int value of 48 according to ASCII,
15            // subtracting '0' translates char '0'-'9' to int 0-9
16            int rod = rings[i] - '0';
17          
18            // Insert the ring color (rings[i - 1]) into the set belonging to the rod
19            rodToRingsMap[rod].insert(rings[i - 1]);
20        }
21
22        // Initialize the answer to count the number of rods with all 3 colors of rings
23        int completeRodsCount = 0;
24      
25        // Iterate through rods 0 to 9
26        for (int rod = 0; rod < 10; ++rod) {
27            // If the set contains all 3 colors, increase the count
28            if (rodToRingsMap[rod].size() == 3) {
29                ++completeRodsCount;
30            }
31        }
32
33        // Return the number of rods that have all 3 colors of rings
34        return completeRodsCount;
35    }
36};
37

1function countPoints(rings: string): number {
2    // Helper function to convert a color character to a unique number.
3    const getColorCode = (color: string) => color.charCodeAt(0) - 'A'.charCodeAt(0);
4
5    const lengthOfRings = rings.length;
6  
7    // Calculate a target number which represents having all three colors on a rod.
8    const targetCombination = (1 << getColorCode('R')) + (1 << getColorCode('G')) + (1 << getColorCode('B'));
9  
10    // Initialize the count-array which holds the combination of colors on each of the 10 rods.
11    const rodColorCounts = new Array(10).fill(0);
12
13    // Iterate over pairs of characters (color, rod number) in the input string.
14    for (let i = 0; i < lengthOfRings; i += 2) {
15        // Bitwise OR the color's code into the count for the corresponding rod.
16        const rod = parseInt(rings[i + 1]);
17        rodColorCounts[rod] |= 1 << getColorCode(rings[i]);
18    }
19
20    // Use reduce to tally rods that have all three colors.
21    return rodColorCounts.reduce((rodCountAccumulator, currentRodValue) => {
22        return rodCountAccumulator + (currentRodValue === targetCombination ? 1 : 0);
23    }, 0);
24}
25

Time and Space Complexity

The given Python code uses a loop that iterates over the string rings and a dictionary to store the colors of rings present on each rod.

Time Complexity

The time complexity of the code is determined by the for loop, which iterates over the characters of the string rings, but skipping every other character (as it increments i by 2 for each iteration). If N is the length of the rings string, then the number of iterations of the loop is approximately N/2. Each operation within the loop (accessing characters, adding them to the set, and incrementing the counter) is performed in constant time, O(1). As such, the total time complexity is O(N/2), which simplifies to O(N).

Space Complexity

The space complexity is determined by the additional data structures used, which, in this case, is the dictionary mp. The dictionary size depends on the number of unique rods (digits) in the rings string. In the worst case, each rod will have a set storing up to three colors (since there are only three different colors possible). Hence, the space occupied by the dictionary is proportional to the number of rods with an additional constant factor for the sets. If there are k different rods, the space complexity is O(k). Moreover, considering that k is bounded by a constant (since rod digits in the string can range only from 0 to 9), the space complexity simplifies to O(1).

Note: Another perspective on space complexity is that it can be considered as O(N) if we count the total number of color entries across all sets. However, since there can only be three entries per set and ten possible rods, the previous conclusion that it's O(1) holds for the maximum possible space taken by the sets.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know