2103. Rings and Rods Solution & Explanation

Q: Is Rings and Rods easy or hard?

Rings and Rods is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly involves parsing the string correctly and tracking colors per rod using sets or bitmasks.

Q: Rings and Rods Python/Java solution

In Python or Java, the typical implementation uses an array of sets or integers indexed by rod number 0–9. Iterate through the string in steps of two, update the structure with the ring color, and finally count rods that contain all three colors. Both languages achieve O(n) time and constant space.

Q: How to solve Rings and Rods in O(n)?

Traverse the string two characters at a time. Record the color of each ring on its rod using either a set or a bitmask. After processing all pairs, count rods that contain all three colors. Since each pair is handled once, the algorithm runs in linear O(n) time.

Q: What is the best approach for Rings and Rods?

The best approach uses a small array of sets to track colors placed on each rod. Iterate through the string in pairs and insert the ring color into the corresponding rod's set. After processing, count rods whose set contains all three colors R, G, and B. This runs in O(n) time with O(1) space because there are only 10 rods.

Q: Is Rings and Rods asked at Google/Amazon/Meta?

Rings and Rods is categorized as an easy string and hashing problem and appears in practice sets used by companies like Amazon and Google for early screening rounds. It tests basic iteration, hashing, and data representation skills rather than complex algorithms.

Q: What data structure is used in Rings and Rods?

Common solutions use a hash-based structure such as a set or an array of sets to track colors for each rod. An alternative implementation uses integer bitmasks to represent colors, allowing constant-time updates with bitwise operations.

Q: What is the time complexity of Rings and Rods?

The optimal solution runs in O(n) time where n is the length of the input string. Each ring is processed once while updating a rod’s color record. Space complexity is O(1) because the algorithm stores information for only ten rods regardless of input size.

The problem

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).

Approach overview

Problem Overview: You receive a string where every two characters represent a ring and the rod it is placed on. The first character is the ring color (R, G, B) and the second is a rod index from 0 to 9. The task is to count how many rods end up with all three colors.

Approach 1: Using Sets to Track Colors on Rods (Time: O(n), Space: O(1))

The straightforward solution maps each rod to the set of colors placed on it. Iterate through the string in steps of two characters. For each pair, extract the color and rod index, then insert the color into a set associated with that rod. Because rods are limited to digits 0-9, you can store these sets in a small array or hash map. After processing the entire string, check which rods have a set size of three, meaning they contain R, G, and B. This approach uses constant space because the number of rods never exceeds ten. It relies on fast membership tracking provided by a hash table style structure and straightforward iteration over the string.

Approach 2: Numeric Bitmask Representation (Time: O(n), Space: O(1))

A more compact approach encodes colors using bits instead of storing sets. Assign a bit to each color: R = 1, G = 2, B = 4. Maintain an integer array of size 10 where each index represents a rod. As you iterate through the string pairs, update the rod’s bitmask with a bitwise OR operation corresponding to the ring color. For example, adding a green ring sets the second bit. At the end, a rod containing all three colors will have the mask value 7 (1 | 2 | 4). Counting rods with value 7 gives the answer. This method eliminates set operations and replaces them with constant-time bitwise updates, making it both memory-efficient and fast in practice.

Recommended for interviews: Start with the set-based solution because it clearly models the problem: each rod stores the colors it has seen. The logic is easy to explain and implement quickly. After that, mention the bitmask optimization. Interviewers often like this improvement because it demonstrates comfort with space-efficient representations and bitwise reasoning while keeping the same O(n) runtime.

Approach 1: Approach 1: Using Sets to Track Colors on Rods

In this approach, we use an array of sets to maintain a list of colors present on each rod. As we parse the input, we add the color of each ring to the corresponding set for its rod. Finally, we count the number of sets that contain all three colors.

Python

def countPoints(rings: str) -> int:
    rods = [set() for _ in range(10)]
    for i in range(0, len(rings), 2):
        color, rod = rings[i], int(rings[i + 1])
        rods[rod].add(color)
    return sum(1 for rod in rods if len(rod) == 3)

print(countPoints("B0B6G0R6R0R6G9"))

Java

import java.util.*;

public class Solution {
    public int countPoints(String rings) {
        Set<Character>[] rods = new HashSet[10];
        for (int i = 0; i < 10; i++) {
            rods[i] = new HashSet<>();
        }
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings.charAt(i);
            int rod = rings.charAt(i + 1) - '0';
            rods[rod].add(color);
        }

        int count = 0;
        for (Set<Character> rod : rods) {
            if (rod.size() == 3) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countPoints("B0B6G0R6R0R6G9"));
    }
}

C++

#include <iostream>
#include <unordered_set>
#include <vector>

int countPoints(std::string rings) {
    std::vector<std::unordered_set<char>> rods(10);
    for (size_t i = 0; i < rings.length(); i += 2) {
        char color = rings[i];
        int rod = rings[i + 1] - '0';
        rods[rod].insert(color);
    }

    int count = 0;
    for (const auto &rod : rods) {
        if (rod.size() == 3) ++count;
    }
    return count;
}

int main() {
    std::cout << countPoints("B0B6G0R6R0R6G9") << std::endl;
    return 0;
}

JavaScript

function countPoints(rings) {
    const rods = Array.from({ length: 10 }, () => new Set());
    for (let i = 0; i < rings.length; i += 2) {
        const color = rings[i];
        const rod = parseInt(rings[i + 1], 10);
        rods[rod].add(color);
    }
    return rods.reduce((count, rod) => rod.size === 3 ? count + 1 : count, 0);
}

console.log(countPoints("B0B6G0R6R0R6G9"));

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int countPoints(char *rings) {
    bool rods[10][3] = {0};
    
    for (int i = 0; rings[i]; i += 2) {
        char color = rings[i];
        int rod = rings[i + 1] - '0';
        
        if (color == 'R') rods[rod][0] = true;
        if (color == 'G') rods[rod][1] = true;
        if (color == 'B') rods[rod][2] = true;
    }
    
    int count = 0;
    for (int i = 0; i < 10; i++) {
        if (rods[i][0] && rods[i][1] && rods[i][2]) count++;
    }
    
    return count;
}

int main() {
    printf("%d\n", countPoints("B0B6G0R6R0R6G9"));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountPoints(string rings) {
        HashSet<char>[] rods = new HashSet<char>[10];
        for (int i = 0; i < 10; i++) {
            rods[i] = new HashSet<char>();
        }
        for (int i = 0; i < rings.Length; i += 2) {
            char color = rings[i];
            int rod = rings[i + 1] - '0';
            rods[rod].Add(color);
        }
        
        int count = 0;
        foreach (var rod in rods) {
            if (rod.Count == 3) count++;
        }
        return count;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountPoints("B0B6G0R6R0R6G9"));
    }
}

In Python, we create a list of sets. Each set collects the colors present on a rod. By the end of processing, the number of rods containing all three colors is returned.

Complexity

Time Complexity: O(n), where n is twice the number of rings. Each iteration takes constant time.
Space Complexity: O(1), as we only use a fixed number of sets.

Try this approach in the editor

Approach 2: Approach 2: Numeric Bitmask Representation

In this approach, each rod is represented by a bitmask of three bits indicating the presence of the colors R, G, and B. We iterate through the string to update each rod's bitmask and finally count rods with a bitmask value of 7 (binary 111, meaning all colors are present).

Python

def countPoints(rings: str) -> int:
    rods = [0] * 10
    for i in range(0, len(rings), 2):
        color, rod = rings[i], int(rings[i + 1])
        bit = {'R': 1, 'G': 2, 'B': 4}[color]
        rods[rod] |= bit
    return sum(1 for rod in rods if rod == 7)

print(countPoints("B0B6G0R6R0R6G9"))

Java

public class Solution {
    public int countPoints(String rings) {
        int[] rods = new int[10];
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings.charAt(i);
            int rod = rings.charAt(i + 1) - '0';
            int bit = (color == 'R') ? 1 : (color == 'G') ? 2 : 4;
            rods[rod] |= bit;
        }

        int count = 0;
        for (int rod : rods) {
            if (rod == 7) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countPoints("B0B6G0R6R0R6G9"));
    }
}

C++

#include <iostream>
#include <vector>

int countPoints(std::string rings) {
    std::vector<int> rods(10, 0);
    for (size_t i = 0; i < rings.length(); i += 2) {
        char color = rings[i];
        int rod = rings[i + 1] - '0';
        int bit = (color == 'R') ? 1 : (color == 'G') ? 2 : 4;
        rods[rod] |= bit;
    }

    int count = 0;
    for (const int rod : rods) {
        if (rod == 7) count++;
    }
    return count;
}

int main() {
    std::cout << countPoints("B0B6G0R6R0R6G9") << std::endl;
    return 0;
}

JavaScript

function countPoints(rings) {
    let rods = Array(10).fill(0);
    for (let i = 0; i < rings.length; i += 2) {
        const color = rings[i];
        const rod = parseInt(rings[i + 1], 10);
        const bit = (color === 'R') ? 1 : (color === 'G') ? 2 : 4;
        rods[rod] |= bit;
    }
    return rods.reduce((count, rod) => rod === 7 ? count + 1 : count, 0);
}

console.log(countPoints("B0B6G0R6R0R6G9"));

#include <stdio.h>
#include <string.h>

int countPoints(char *rings) {
    int rods[10] = {0};
    for (int i = 0; rings[i]; i += 2) {
        char color = rings[i];
        int rod = rings[i + 1] - '0';
        int bit = (color == 'R') ? 1 : (color == 'G') ? 2 : 4;
        rods[rod] |= bit;
    }

    int count = 0;
    for (int i = 0; i < 10; i++) {
        if (rods[i] == 7) count++; // 7 = 111 in binary
    }
    return count;
}

int main() {
    printf("%d\n", countPoints("B0B6G0R6R0R6G9"));
    return 0;
}

using System;

public class Solution {
    public int CountPoints(string rings) {
        int[] rods = new int[10];
        for (int i = 0; i < rings.Length; i += 2) {
            char color = rings[i];
            int rod = rings[i + 1] - '0';
            int bit = (color == 'R') ? 1 : (color == 'G') ? 2 : 4;
            rods[rod] |= bit;
        }

        int count = 0;
        foreach (int rod in rods) {
            if (rod == 7) count++;
        }
        return count;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountPoints("B0B6G0R6R0R6G9"));
    }
}

The Python solution uses a list of integers to represent rods' bitmasks, which are manipulated with bitwise operators to position each color’s presence distinctly. We check for a complete set by confirming against the binary full mask.

Complexity

Time Complexity: O(n), where n indicates the length of the input string in characters.
Space Complexity: O(1), reflecting the unchanged size of our rod tracking structure.

Try this approach in the editor

Approach 3: Bit Manipulation

We can use an array mask of length 10 to represent the color situation of the rings on each rod, where mask[i] represents the color situation of the ring on the ith rod. If there are red, green, and blue rings on the ith rod, then the binary representation of mask[i] is 111, that is, mask[i] = 7.

We traverse the string rings. For each color position pair (c, j), where c represents the color of the ring and j represents the number of the rod where the ring is located, we set the corresponding binary bit of mask[j], that is, mask[j] |= d[c], where d[c] represents the binary bit corresponding to color c.

Finally, we count the number of elements in mask that are 7, which is the number of rods that have collected all three colors of rings.

The time complexity is O(n), and the space complexity is O(|\Sigma|), where n represents the length of the string rings, and |\Sigma| represents the size of the character set.

TypeScript

function countPoints(rings: string): number {
    const idx = (c: string) => c.charCodeAt(0) - 'A'.charCodeAt(0);
    const d: number[] = Array(26).fill(0);
    d[idx('R')] = 1;
    d[idx('G')] = 2;
    d[idx('B')] = 4;
    const mask: number[] = Array(10).fill(0);
    for (let i = 0; i < rings.length; i += 2) {
        const c = rings[i];
        const j = rings[i + 1].charCodeAt(0) - '0'.charCodeAt(0);
        mask[j] |= d[idx(c)];
    }
    return mask.filter(x => x === 7).length;
}

func countPoints(rings string) (ans int) {
	d := ['Z']int{'R': 1, 'G': 2, 'B': 4}
	mask := [10]int{}
	for i, n := 0, len(rings); i < n; i += 2 {
		c := rings[i]
		j := int(rings[i+1] - '0')
		mask[j] |= d[c]
	}
	for _, x := range mask {
		if x == 7 {
			ans++
		}
	}
	return
}

Rust

impl Solution {
    pub fn count_points(rings: String) -> i32 {
        let mut d: [i32; 90] = [0; 90];
        d['R' as usize] = 1;
        d['G' as usize] = 2;
        d['B' as usize] = 4;

        let mut mask: [i32; 10] = [0; 10];

        let cs: Vec<char> = rings.chars().collect();

        for i in (0..cs.len()).step_by(2) {
            let c = cs[i] as usize;
            let j = (cs[i + 1] as usize) - ('0' as usize);
            mask[j] |= d[c];
        }

        mask.iter().filter(|&&x| x == 7).count() as i32
    }
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function countPoints(rings: string): number {
    let c = 0;
    for (let i = 0; i <= 9; i++) {
        if (rings.includes('B' + i) && rings.includes('R' + i) && rings.includes('G' + i)) c++;
    }
    return c;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Using Sets to Track Colors on Rods	Time Complexity: O(n), where n is twice the number of rings. Each iteration takes constant time. Space Complexity: O(1), as we only use a fixed number of sets.
Approach 2: Numeric Bitmask Representation	Time Complexity: O(n), where n indicates the length of the input string in characters. Space Complexity: O(1), reflecting the unchanged size of our rod tracking structure.
Bit Manipulation	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Sets to track colors per rod	O(n)	O(1)	Best for readability and interviews when modeling the problem directly with collections
Numeric bitmask representation	O(n)	O(1)	When you want a compact representation and faster constant-time updates using bit operations

Frequently asked questions

Is Rings and Rods easy or hard?

Rings and Rods is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly involves parsing the string correctly and tracking colors per rod using sets or bitmasks.

Rings and Rods Python/Java solution

In Python or Java, the typical implementation uses an array of sets or integers indexed by rod number 0–9. Iterate through the string in steps of two, update the structure with the ring color, and finally count rods that contain all three colors. Both languages achieve O(n) time and constant space.

How to solve Rings and Rods in O(n)?

Traverse the string two characters at a time. Record the color of each ring on its rod using either a set or a bitmask. After processing all pairs, count rods that contain all three colors. Since each pair is handled once, the algorithm runs in linear O(n) time.

What is the best approach for Rings and Rods?

The best approach uses a small array of sets to track colors placed on each rod. Iterate through the string in pairs and insert the ring color into the corresponding rod's set. After processing, count rods whose set contains all three colors R, G, and B. This runs in O(n) time with O(1) space because there are only 10 rods.

Is Rings and Rods asked at Google/Amazon/Meta?

Rings and Rods is categorized as an easy string and hashing problem and appears in practice sets used by companies like Amazon and Google for early screening rounds. It tests basic iteration, hashing, and data representation skills rather than complex algorithms.

What data structure is used in Rings and Rods?

Common solutions use a hash-based structure such as a set or an array of sets to track colors for each rod. An alternative implementation uses integer bitmasks to represent colors, allowing constant-time updates with bitwise operations.

What is the time complexity of Rings and Rods?

The optimal solution runs in O(n) time where n is the length of the input string. Each ring is processed once while updating a rod’s color record. Space complexity is O(1) because the algorithm stores information for only ten rods regardless of input size.

Rings and Rods solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using Sets to Track Colors on Rods

Approach 2: Approach 2: Numeric Bitmask Representation

Approach 3: Bit Manipulation

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rings and Rods solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using Sets to Track Colors on Rods

Approach 2: Approach 2: Numeric Bitmask Representation

Approach 3: Bit Manipulation

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems