LeetCode 2103 - Rings and Rods

The problem is asking us to determine how many rods, labeled from 0 to 9, have all three colors of rings placed on them.

leetcodeeasyhash-tablestring

LeetCode Problem 2103

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem is asking us to determine how many rods, labeled from 0 to 9, have all three colors of rings placed on them. Each ring is described by a two-character string: the first character is the color ('R' for red, 'G' for green, 'B' for blue) and the second character is the rod index ('0' to '9'). The input rings is a string of length 2n representing n rings.

Effectively, we need to scan the input and keep track of which colors appear on each rod. At the end, we count how many rods have all three colors present.

The constraints are modest: 1 <= n <= 100 and there are only 10 rods, so we do not need a heavy optimization. However, we should ensure our solution is clean and correctly handles repeated colors on the same rod, rods with only some colors, and minimal inputs like a single ring.

Important edge cases include:

  • Only one ring given, so no rod can have all three colors.
  • Multiple rings on the same rod with some repeated colors.
  • Maximum input length (2n = 200), ensuring performance remains acceptable.
  • Rods that never receive a ring.

Approaches

The brute-force approach would involve iterating through the rings string and for each rod, maintain a list of the colors that have appeared. At the end, for each rod, check whether it contains all three colors. This works for the problem size, but it requires checking every rod's list and comparing against the set {'R','G','B'}.

A more optimal approach uses a hash map (dictionary) where the keys are rod indices (0 to 9) and the values are sets of colors. We iterate through the string, and for each color-rod pair, we add the color to the set corresponding to that rod. At the end, counting rods with sets of size 3 directly gives the answer. This approach is simple, direct, and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Maintain lists of colors per rod, check for all three colors per rod
Optimal O(n) O(1) Use hash map of sets for rods; only 10 rods, so space is constant

Algorithm Walkthrough

  1. Initialize a dictionary rod_colors where keys are rod indices (0 to 9) and values are empty sets to store colors seen on each rod.
  2. Iterate over the rings string in steps of 2:
  • Extract color as the character at index i.
  • Extract rod as the character at index i+1.
  • Add color to rod_colors[rod].
  1. Initialize a counter count to 0.
  2. Iterate over the sets in rod_colors:
  • If the set contains all three colors (len(set) == 3), increment count.
  1. Return count as the number of rods with all three colors.

Why it works: Each rod's set only contains unique colors, so counting rods with sets of size 3 guarantees the rod has red, green, and blue. The algorithm directly captures the distribution of colors without redundant checks.

Python Solution

class Solution:
    def countPoints(self, rings: str) -> int:
        rod_colors = {str(i): set() for i in range(10)}
        
        for i in range(0, len(rings), 2):
            color = rings[i]
            rod = rings[i+1]
            rod_colors[rod].add(color)
        
        count = 0
        for colors in rod_colors.values():
            if len(colors) == 3:
                count += 1
        
        return count

Explanation: The dictionary comprehension initializes a set for each rod. Iterating in steps of 2 ensures we read color-rod pairs correctly. Adding to a set handles duplicates automatically. Finally, checking the set length determines if a rod has all three colors.

Go Solution

func countPoints(rings string) int {
    rodColors := make(map[byte]map[byte]bool)
    for i := byte('0'); i <= '9'; i++ {
        rodColors[i] = make(map[byte]bool)
    }

    for i := 0; i < len(rings); i += 2 {
        color := rings[i]
        rod := rings[i+1]
        rodColors[rod][color] = true
    }

    count := 0
    for _, colors := range rodColors {
        if len(colors) == 3 {
            count++
        }
    }

    return count
}

Go-specific notes: We use a map of maps to represent sets of colors. The outer map keys are rod bytes, the inner map acts as a set (map[byte]bool). Go requires explicit initialization of maps, unlike Python sets.

Worked Examples

Example 1: "B0B6G0R6R0R6G9"

Iteration Rod Color rod_colors state
0-1 0 B {0:{B}}
2-3 6 B {6:{B}}
4-5 0 G {0:{B,G}}
6-7 6 R {6:{B,R}}
8-9 0 R {0:{B,G,R}}
10-11 6 R {6:{B,R}}
12-13 9 G {9:{G}}

After iteration, rods with set size 3: only rod 0 → output 1.

Example 2: "B0R0G0R9R0B0G0"

Iteration Rod Color rod_colors state
0-1 0 B {0:{B}}
2-3 0 R {0:{B,R}}
4-5 0 G {0:{B,R,G}}
6-7 9 R {9:{R}}
8-9 0 B {0:{B,R,G}}
10-11 0 G {0:{B,R,G}}

Rod 0 has all three colors → output 1.

Example 3: "G4"

Rod 4 only has G → output 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over rings string of length 2n.
Space O(1) Only 10 rods, each storing at most 3 colors; constant space.

Since the number of rods is fixed and small, the space used is effectively constant, regardless of n.

Test Cases

# Provided examples
assert Solution().countPoints("B0B6G0R6R0R6G9") == 1  # rod 0 has all colors
assert Solution().countPoints("B0R0G0R9R0B0G0") == 1  # rod 0 has all colors
assert Solution().countPoints("G4") == 0  # single ring, no rod has all colors

# Edge cases
assert Solution().countPoints("R0G1B2") == 0  # each rod has one color only
assert Solution().countPoints("R0G0B0") == 1  # single rod with all colors
assert Solution().countPoints("R0R0R0") == 0  # repeated color, never all colors
assert Solution().countPoints("R0G0B0R1G1B1R2G2B2R3G3B3") == 4  # multiple rods with all colors
assert Solution().countPoints("R0G0B0R0G0B0R0G0B0") == 1  # repeated colors on one rod
Test Why
"B0B6G0R6R0R6G9" Normal case with mixed rods
"B0R0G0R9R0B0G0" Multiple rings per rod, some missing colors
"G4" Minimum input size
"R0G1B2" No rod with all colors
"R0G0B0" Single rod with all colors
"R0R0R0" Repeated colors, cannot reach 3 colors
"R0G0B0R1G1B1R2G2B2R3G3B3" Multiple rods fully filled
"R0G0B0R0G0B0R0G0B0" Single rod with repeated colors

Edge Cases

The first edge case is when the input string contains only one ring. In this situation, no rod can possibly have all three colors. The implementation handles this correctly by checking set size at the end.

The second edge case is when multiple rings of the same color are placed on the same rod