algoadvance

Leetcode 2103. Rings and Rods

Problem Statement

You are tasked with solving the following LeetCode problem:

2103. Rings and Rods

There are n rings and 10 rods numbered from 0 to 9. You are given a string rings of length 2n that describes the rings that are placed onto the rods. The i-th character of rings is either 'R', 'G', or 'B' (representing the colors Red, Green, and Blue), and the (i+1)-th character is a digit from 0 to 9 representing the rod on which the ring is placed.

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

Clarifying Questions

Before we start, let’s clarify the problem with some questions:

1. Is the input string length always even, given it’s 2n by definition?
   • Yes, the string length is always even.
2. Are there any constraints on the value of n?
   • Generally, there’s no strict constraint specified in the problem statement.
3. Should we consider invalid characters in the input string?
   • No, you can assume the input string is always valid as per the problem statement.

Strategy

1. We will use a HashMap to keep track of the colors present on each of the 10 rods.
2. Iterate through the string rings in steps of 2.
   • For each pair, update the HashMap for the respective rod with the color of the ring.
3. After processing the string, count how many rods have all three colors (i.e., ‘R’, ‘G’, and ‘B’).

Code

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    public int countPoints(String rings) {
        HashMap<Integer, HashSet<Character>> rodColors = new HashMap<>();

        // Iterate through the rings string two characters at a time
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings.charAt(i);
            int rod = rings.charAt(i + 1) - '0'; // Convert char to int
            
            rodColors.putIfAbsent(rod, new HashSet<>());
            rodColors.get(rod).add(color);
        }

        int count = 0;
        
        // Count the rods that have all three colors
        for (HashSet<Character> colors : rodColors.values()) {
            if (colors.contains('R') && colors.contains('G') && colors.contains('B')) {
                count++;
            }
        }
        
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countPoints("B0R0G0R9R0B0G0")); // Output should be 1
    }
}

Time Complexity

• Time Complexity: (O(n))
  • We iterate through the rings string, which has (2n) characters, hence the process itself is (O(n)).
  • In the worst case, processing each ring involves accessing and updating a HashSet in constant time (O(1)).
• Space Complexity: (O(1))
  • We maintain a HashMap with at most 10 entries (since there are only 10 rods), and each entry stores a HashSet with at most 3 elements (the colors of the rings).
  • Thus, the space complexity is considered constant, (O(1)), because it doesn’t scale with the size of the input.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?