Skip to main content
Talentd

Rings and Rods - Solution & Explanation

EasyHash TableString21 min readAsked at: Google
Practice this problem

Problem Statement

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

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.

This solution utilizes a 2D boolean array where each row represents a rod and each column represents a color (0 for R, 1 for G, 2 for B). As we iterate through the ring string, we update the respective rod's color status. At the end, we count rods with all color statuses set to true.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of rings. Each ring is processed in constant time.
Space Complexity: O(1), as the size of the rods array is constant (10x3).

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

This C solution uses an integer array where each element stores bitmask values corresponding to the colors on each rod. Each rod's bitmask is composed as rings are processed, and a rod counts if its mask equals 7 (0b111).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as each ring is processed in constant time.
Space Complexity: O(1), given the fixed number of rods (10).

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Approach 4: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Sets to Track Colors on Rods

Time Complexity: O(n), where n is the number of rings. Each ring is processed in constant time.
Space Complexity: O(1), as the size of the rods array is constant (10x3).

Approach 2: Numeric Bitmask Representation

Time Complexity: O(n), as each ring is processed in constant time.
Space Complexity: O(1), given the fixed number of rods (10).

Bit Manipulation—
Default Approach—

Detailed Complexity Analysis

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

Video Solution

Leetcode 2103 - Rings and Rods - Video Editorial • Sandeep Kumar • 3,020 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Rings and Rods with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if All Characters Have Equal Number of Occurrences