Scale Engineer

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 TableString

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 ith pair denotes the ith ring's color ('R', 'G', 'B').
  • The second character of the ith pair denotes the rod that the ith 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.

  1. Initialize a HashMap<Integer, Set<Character>>.
  2. 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.
  3. 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.
  4. Add the current color to the rod's set. The set will only store unique colors.
  5. After processing all the rings, iterate through the values of the map (which are the sets of colors).
  6. 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).
  7. This count is the final answer.
import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set; class Solution {    public int countPoints(String rings) {        Map<Integer, Set<Character>> rods = new HashMap<>();                for (int i = 0; i < rings.length(); i += 2) {            char color = rings.charAt(i);            int rodIndex = rings.charAt(i + 1) - '0';                        // Get the set of colors for the current rod, or create a new one            rods.putIfAbsent(rodIndex, new HashSet<>());                        // Add the color to the set for that rod            rods.get(rodIndex).add(color);        }                int count = 0;        // Iterate through the map's values (the sets of colors)        for (Set<Character> colors : rods.values()) {            // If a set has 3 colors, it means the rod has all three            if (colors.size() == 3) {                count++;            }        }                return count;    }}

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.

Solutions

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

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 →

Next problem