Rings and Rods

Easy

#1915Time: O(N), where N is the length of the `rings` string. We iterate through the string once. Map and set operations (put, get, add) take average O(1) time. The final loop runs at most 10 times, which is a constant factor.Space: O(1) - Constant space. Since there are at most 10 rods and 3 colors, the space required for the map and sets is bounded by a constant (10 keys, each with a set of at most 3 characters).

Data structures

Hash Table String

Prompt

There are n rings and each ring is either red, green, or blue. The rings are distributed across ten rods labeled from 0 to 9.

You are given a string rings of length 2n that describes the n rings that are placed onto the rods. Every two characters in rings forms a color-position pair that is used to describe each ring where:

The first character of the i^th pair denotes the i^th ring's color ('R', 'G', 'B').
The second character of the i^th pair denotes the rod that the i^th ring is placed on ('0' to '9').

For example, "R3G2B1" describes n == 3 rings: a red ring placed onto the rod labeled 3, a green ring placed onto the rod labeled 2, and a blue ring placed onto the rod labeled 1.

Return the number of rods that have all three colors of rings on them.

Example 1:

Input: rings = "B0B6G0R6R0R6G9"
Output: 1
Explanation: 
- The rod labeled 0 holds 3 rings with all colors: red, green, and blue.
- The rod labeled 6 holds 3 rings, but it only has red and blue.
- The rod labeled 9 holds only a green ring.
Thus, the number of rods with all three colors is 1.

Example 2:

Input: rings = "B0R0G0R9R0B0G0"
Output: 1
Explanation: 
- The rod labeled 0 holds 6 rings with all colors: red, green, and blue.
- The rod labeled 9 holds only a red ring.
Thus, the number of rods with all three colors is 1.

Example 3:

Input: rings = "G4"
Output: 0
Explanation: 
Only one ring is given. Thus, no rods have all three colors.

Constraints:

rings.length == 2 * n
1 <= n <= 100
rings[i] where i is even is either 'R', 'G', or 'B' (0-indexed).
rings[i] where i is odd is a digit from '0' to '9' (0-indexed).

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a Hash Map to store the information about which colors are present on each rod. The keys of the map are the rod indices (0-9), and the values are Sets of characters representing the colors ('R', 'G', 'B'). Using a Set for colors automatically handles duplicate colors on the same rod, simplifying the logic.

Algorithm

Create a HashMap<Integer, Set<Character>> named rods to map rod indices to the set of colors on them.
Loop through the rings string with a step of 2.
In each iteration, extract the color character and the rodIndex integer.
Use rods.putIfAbsent(rodIndex, new HashSet<>()) to ensure a set exists for the current rod.
Add the color to the set for the rodIndex using rods.get(rodIndex).add(color).
After the loop, initialize a counter count to 0.
Iterate over the values (the Set<Character>) of the rods map.
If a set's size is 3, it means all three colors are present, so increment count.
Return count.

Walkthrough

The core idea is to model the problem directly using data structures that fit the description. A map is a natural choice to associate rods (keys) with their properties (values). Since each rod can have multiple rings of different colors, a set is used as the value to store the unique colors found on that rod.

Initialize a HashMap<Integer, Set<Character>>.
Iterate through the input string rings by pairs of characters. For each pair, the first character is the color and the second is the rod index.
Parse the rod index and the color. For each rod, find its corresponding set in the map. If the rod is encountered for the first time, create a new HashSet for it.
Add the current color to the rod's set. The set will only store unique colors.
After processing all the rings, iterate through the values of the map (which are the sets of colors).
Count how many of these sets have a size of 3. A size of 3 indicates that the rod contains rings of all three distinct colors (Red, Green, and Blue).
This count is the final answer.

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6class Solution {7    public int countPoints(String rings) {8        Map<Integer, Set<Character>> rods = new HashMap<>();9        10        for (int i = 0; i < rings.length(); i += 2) {11            char color = rings.charAt(i);12            int rodIndex = rings.charAt(i + 1) - '0';13            14            // Get the set of colors for the current rod, or create a new one15            rods.putIfAbsent(rodIndex, new HashSet<>());16            17            // Add the color to the set for that rod18            rods.get(rodIndex).add(color);19        }20        21        int count = 0;22        // Iterate through the map's values (the sets of colors)23        for (Set<Character> colors : rods.values()) {24            // If a set has 3 colors, it means the rod has all three25            if (colors.size() == 3) {26                count++;27            }28        }29        30        return count;31    }32}

Complexity

Time

O(N), where N is the length of the `rings` string. We iterate through the string once. Map and set operations (put, get, add) take average O(1) time. The final loop runs at most 10 times, which is a constant factor.

Space

O(1) - Constant space. Since there are at most 10 rods and 3 colors, the space required for the map and sets is bounded by a constant (10 keys, each with a set of at most 3 characters).

Trade-offs

Pros

The logic is straightforward and easy to understand as it directly models the problem's entities.
It's flexible and would work even if the rod indices were not sequential or small integers.

Cons

Has slightly more overhead compared to using arrays due to the nature of hash maps (e.g., calculating hash codes, handling collisions).
Requires using wrapper classes (Integer) and HashSet objects, which can be less memory-efficient than primitive arrays.

This approach is an optimization of the Hash Map method. Since the rods are labeled from 0 to 9, we can use a fixed-size array of size 10 instead of a Hash Map. Each index in the array corresponds to a rod, and the element at that index is a Set containing the colors of rings on that rod. This avoids the overhead of hashing.

Algorithm

Create an array of Set<Character> of size 10, named rods.
Initialize each element of the rods array with a new HashSet.
Loop through the rings string with a step of 2.
In each iteration, extract the color and rodIndex.
Add the color to the set at rods[rodIndex].
Initialize a counter count to 0.
Loop from i = 0 to 9.
If rods[i].size() is 3, increment count.
Return count.

Walkthrough

Knowing there are exactly 10 rods (0-9) allows us to use an array for direct, constant-time access, which is generally faster than hash map lookups.

Initialize an array of Set<Character> of size 10. It's crucial to also initialize each element of this array with a new HashSet instance.
Iterate through the rings string in pairs. For each color-rod pair, parse the rod index.
Use the rod index to directly access the corresponding set in our array and add the color to it.
After populating the array with all the color information, iterate through the array from index 0 to 9.
For each of the 10 sets, check if its size is 3.
The total count of sets with size 3 is the number of rods with all three colors.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int countPoints(String rings) {6        // Array of sets, one for each rod (0-9)7        Set<Character>[] rods = new Set[10];8        for (int i = 0; i < 10; i++) {9            rods[i] = new HashSet<>();10        }11        12        // Iterate through the rings string13        for (int i = 0; i < rings.length(); i += 2) {14            char color = rings.charAt(i);15            int rodIndex = rings.charAt(i + 1) - '0';16            17            // Add the color to the set for the corresponding rod18            rods[rodIndex].add(color);19        }20        21        int count = 0;22        // Count rods with all three colors23        for (int i = 0; i < 10; i++) {24            if (rods[i].size() == 3) {25                count++;26            }27        }28        29        return count;30    }31}

Complexity

Time

O(N), where N is the length of the `rings` string. The processing is dominated by the single pass through the input string. Array access is O(1).

Space

O(1) - Constant space. The space is fixed by the number of rods (10) and colors (3), so it does not depend on the input size N.

Trade-offs

Pros

More efficient than the Hash Map approach due to direct array indexing, which avoids hashing overhead.
Maintains good readability while improving performance.
Constant space complexity.

Cons

Still involves the overhead of creating and managing HashSet objects.
This approach is less flexible than a map if the rod indices were not small, consecutive integers.

This is the most efficient approach in terms of both space and practical speed. It uses an integer array of size 10 to represent the rods. Each integer acts as a bitmask to store the presence of colors. Specific bits are assigned to each color (e.g., Red=1, Green=2, Blue=4). A rod has all three colors if its corresponding integer value becomes 7 (which is the result of 1 | 2 | 4).

Algorithm

Create an integer array rods of size 10, initialized to all zeros.
Loop through the rings string with a step of 2.
Extract the color and rodIndex.
Determine the bitmask for the color: 1 for 'R', 2 for 'G', 4 for 'B'.
Update the rod's state using a bitwise OR operation: rods[rodIndex] |= mask.
After the loop, initialize a counter count to 0.
Loop through the rods array.
If an element's value is 7 (which is 1 | 2 | 4), it means all three color bits are set, so increment count.
Return count.

Walkthrough

This method leverages bit manipulation for a compact and fast solution. We can represent the presence of the three colors (R, G, B) using 3 distinct bits of an integer.

Assign a bit for each color:
- 'R' -> bit 0 (value 1, i.e., 1 << 0)
- 'G' -> bit 1 (value 2, i.e., 1 << 1)
- 'B' -> bit 2 (value 4, i.e., 1 << 2)

We use an integer array rods of size 10, initialized to all zeros. rods[i] will store the combined color information for rod i as a bitmask.
We iterate through the rings string. For each ring, we identify its color and rod index.
We then set the corresponding bit in the integer for that rod using the bitwise OR operator (|=). For example, if we find a red ring ('R') on rod 3, we perform rods[3] |= 1. If we later find a green ring ('G') on the same rod, we perform rods[3] |= 2. The value of rods[3] would then be 1 | 2 = 3.
After processing all rings, a rod i has all three colors if and only if all three bits (0, 1, and 2) are set in rods[i]. This corresponds to the integer value 1 | 2 | 4 = 7.
Finally, we iterate through the rods array and count how many elements are equal to 7. This count is our result.

1class Solution {2    public int countPoints(String rings) {3        // Each element represents a rod. We use bits to store colors.4        // bit 0: Red, bit 1: Green, bit 2: Blue5        int[] rods = new int[10];6        7        for (int i = 0; i < rings.length(); i += 2) {8            char color = rings.charAt(i);9            int rodIndex = rings.charAt(i + 1) - '0';10            11            int mask = 0;12            if (color == 'R') {13                mask = 1; // binary 00114            } else if (color == 'G') {15                mask = 2; // binary 01016            } else if (color == 'B') {17                mask = 4; // binary 10018            }19            20            // Use bitwise OR to set the color bit for the rod21            rods[rodIndex] |= mask;22        }23        24        int count = 0;25        // The mask for all three colors is 1 | 2 | 4 = 726        int allColorsMask = 7;27        for (int rodColors : rods) {28            if (rodColors == allColorsMask) {29                count++;30            }31        }32        33        return count;34    }35}

Complexity

Time

O(N), where N is the length of the `rings` string. The single pass through the string is the dominant operation, and all operations inside the loop are constant time.

Space

O(1) - Constant space. We only use a fixed-size integer array of size 10.

Trade-offs

Pros

Extremely space-efficient, using only a small, primitive integer array.
Very fast due to the use of primitive types and bitwise operations, which are highly optimized at the hardware level.
Minimal object creation overhead.

Cons

The logic might be slightly less intuitive for developers not comfortable with bit manipulation.
Less extensible if the number of colors were to increase significantly.

Solutions

Solution

1class Solution {2public3  int countPoints(String rings) {4    int[] d = new int['Z'];5    d['R'] = 1;6    d['G'] = 2;7    d['B'] = 4;8    int[] mask = new int[10];9    for (int i = 0, n = rings.length(); i < n; i += 2) {10      int c = rings.charAt(i);11      int j = rings.charAt(i + 1) - '0';12      mask[j] |= d[c];13    }14    int ans = 0;15    for (int x : mask) {16      if (x == 7) {17        ++ans;18      }19    }20    return ans;21  }22}

1class Solution { public: int countPoints ( string rings ) { int d [ 'Z' ]{[ 'R' ] = 1 , [ 'G' ] = 2 , [ 'B' ] = 4 }; int mask [ 10 ]{}; for ( int i = 0 , n = rings . size (); i < n ; i += 2 ) { int c = rings [ i ]; int j = rings [ i + 1 ] - '0' ; mask [ j ] |= d [ c ]; } return count ( mask , mask + 10 , 7 ); } };

1class Solution : def countPoints ( self , rings : str ) -> int : mask = [ 0 ] * 10 d = { "R" : 1 , "G" : 2 , "B" : 4 } for i in range ( 0 , len ( rings ), 2 ): c = rings [ i ] j = int ( rings [ i + 1 ]) mask [ j ] |= d [ c ] return mask . count ( 7 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int countPoints(String rings) {4    int[] d = new int['Z'];5    d['R'] = 1;6    d['G'] = 2;7    d['B'] = 4;8    int[] mask = new int[10];9    for (int i = 0, n = rings.length(); i < n; i += 2) {10      int c = rings.charAt(i);11      int j = rings.charAt(i + 1) - '0';12      mask[j] |= d[c];13    }14    int ans = 0;15    for (int x : mask) {16      if (x == 7) {17        ++ans;18      }19    }20    return ans;21  }22}

1class Solution { public: int countPoints ( string rings ) { int d [ 'Z' ]{[ 'R' ] = 1 , [ 'G' ] = 2 , [ 'B' ] = 4 }; int mask [ 10 ]{}; for ( int i = 0 , n = rings . size (); i < n ; i += 2 ) { int c = rings [ i ]; int j = rings [ i + 1 ] - '0' ; mask [ j ] |= d [ c ]; } return count ( mask , mask + 10 , 7 ); } };

1class Solution : def countPoints ( self , rings : str ) -> int : mask = [ 0 ] * 10 d = { "R" : 1 , "G" : 2 , "B" : 4 } for i in range ( 0 , len ( rings ), 2 ): c = rings [ i ] j = int ( rings [ i + 1 ]) mask [ j ] |= d [ c ] return mask . count ( 7 )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.