Facebook Pixel

726. Number of Atoms

HardStackHash TableStringSorting
Leetcode Link

Problem Description

This problem asks you to parse a chemical formula string and return the count of each atom in alphabetical order.

The parsing rules are:

  • Each element starts with an uppercase letter, followed by zero or more lowercase letters (e.g., H, Ca, Mg)
  • A number after an element indicates its count. If no number follows, the count is 1 (e.g., H2 means 2 hydrogen atoms, O means 1 oxygen atom)
  • Multiple elements can be concatenated (e.g., H2O contains 2 H atoms and 1 O atom)
  • Parentheses can group elements together, and a number after the closing parenthesis multiplies all elements inside (e.g., (OH)2 means 2 O atoms and 2 H atoms)
  • Parentheses can be nested

The solution processes the formula from right to left, using:

  • A multiplier variable to track the current multiplication factor from parentheses
  • A stack to save multipliers when entering nested parentheses (encountering ) from right to left)
  • A frequency counter to build multi-digit numbers
  • A HashMap to accumulate the total count for each element

The algorithm:

  1. Traverse the formula string from right to left
  2. When encountering lowercase letters, build the complete element name backwards
  3. When encountering an uppercase letter (alone or after building lowercase letters), it marks the start of an element - add it to the map with count = freq * multiplier
  4. When encountering digits, build the complete number (which applies to the element/group to its left)
  5. When encountering ), push the current multiplier to stack and update multiplier by multiplying with the frequency
  6. When encountering (, restore the previous multiplier from stack

Finally, sort the element names alphabetically and build the output string, appending counts only when greater than 1.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that parsing from right to left simplifies handling parentheses and multipliers. When we parse left to right, we don't know what multiplier applies to an element until we've seen all the closing parentheses and numbers that follow it. But parsing right to left, we always know the current multiplier before we encounter any element.

Consider Ca(OH)2 - if parsing left to right, when we see O and H, we don't yet know they'll be multiplied by 2. But parsing right to left, we see the 2 first, then the ), so we know everything inside the parentheses should be multiplied by 2 before we even reach O and H.

The stack becomes necessary for nested parentheses. Each time we encounter a ) (moving right to left), we're entering a new group that has its own multiplier. We need to save the current multiplier so we can restore it when we exit this group (when we hit the matching (). Think of it like diving into nested layers - we need to remember what multiplication factor we had at each level.

The formula Mg(OH)2 when parsed right to left becomes:

  • See 2: this is the frequency for the next group
  • See ): entering a group, save current multiplier (1), new multiplier = 1 * 2 = 2
  • See H: add H with count 1 * 2 = 2
  • See O: add O with count 1 * 2 = 2
  • See (: exiting the group, restore multiplier to 1
  • See g, then M: add Mg with count 1 * 1 = 1

This right-to-left approach with a multiplier stack elegantly handles all nesting levels without needing recursive parsing or complex lookahead logic.

Learn more about Stack and Sorting patterns.

Solution Approach

The implementation uses a HashMap to store element counts, a stack array for managing multipliers, and processes the formula string from right to left.

Data Structures:

  • Map<String, Integer> map: Stores the final count of each element
  • int[] [stack](/problems/stack_intro): Manages multipliers for nested parentheses (size 1000 is sufficient for the problem constraints)
  • int top: Stack pointer
  • int multiplier: Current multiplication factor (initially 1)
  • int freq: Accumulates digits to form numbers

Algorithm Steps:

  1. Convert formula to character array and traverse from right to left (i = c.length - 1 to 0)

  2. Handle lowercase letters (c[i] >= 'a' && c[i] <= 'z'):

    • Mark the end position and continue left to find all lowercase letters
    • Combine with the uppercase letter to form the complete element name
    • Add to map: count = Math.max(freq, 1) * multiplier
    • Reset freq = 0

  3. Handle uppercase letters (c[i] >= 'A' && c[i] <= 'Z'):

    • This is a single-letter element (like H, O, N)
    • Add to map with count calculation same as above
    • Reset freq = 0

  4. Handle digits (c[i] >= '0' && c[i] <= '9'):

    • Build multi-digit numbers from right to left
    • Start with freq = c[i] - '0'
    • Continue left with freq += p * (c[--i] - '0') where p multiplies by 10 each iteration
    • This correctly builds numbers like 123 as 3 + 102 + 1001

  5. Handle closing parenthesis ')':

    • Save current multiplier to stack: stack[top++] = multiplier
    • Update multiplier for the group: multiplier *= Math.max(freq, 1)
    • Reset freq = 0

  6. Handle opening parenthesis '(':

    • Restore previous multiplier: multiplier = [stack](/problems/stack_intro)[--top]

  7. Generate output:

    • Extract all keys from the map and sort alphabetically
    • Build result string by appending each element name
    • Only append count if it's greater than 1

The Math.max(freq, 1) pattern ensures that when no number is specified (freq = 0), we treat it as 1. This handles cases like H2O where O has no explicit count.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through parsing the formula K4(ON(SO3)2)2 step by step, processing from right to left.

Initial state:

  • multiplier = 1
  • freq = 0
  • stack = [] (empty)
  • map = {} (empty)

Processing right to left:

  1. Index 13: '2' - It's a digit

    • freq = 2

  2. Index 12: ')' - Closing parenthesis

    • Push current multiplier to stack: stack = [1]
    • Update multiplier: multiplier = 1 * 2 = 2
    • Reset freq = 0

  3. Index 11: '2' - It's a digit

    • freq = 2

  4. Index 10: ')' - Closing parenthesis

    • Push current multiplier to stack: stack = [1, 2]
    • Update multiplier: multiplier = 2 * 2 = 4
    • Reset freq = 0

  5. Index 9: '3' - It's a digit

    • freq = 3

  6. Index 8: 'O' - Uppercase letter

    • Add to map: O with count 3 * 4 = 12
    • Reset freq = 0
    • map = {O: 12}

  7. Index 7: 'S' - Uppercase letter

    • Add to map: S with count 1 * 4 = 4 (freq was 0, so use 1)
    • Reset freq = 0
    • map = {O: 12, S: 4}

  8. Index 6: '(' - Opening parenthesis

    • Restore multiplier from stack: multiplier = 2
    • stack = [1]

  9. Index 5: 'N' - Uppercase letter

    • Add to map: N with count 1 * 2 = 2
    • Reset freq = 0
    • map = {O: 12, S: 4, N: 2}

  10. Index 4: 'O' - Uppercase letter

    • Add to existing O count: O gets 1 * 2 = 2 more
    • map = {O: 14, S: 4, N: 2}

  11. Index 3: '(' - Opening parenthesis

    • Restore multiplier from stack: multiplier = 1
    • stack = []

  12. Index 2: '4' - It's a digit

    • freq = 4

  13. Index 1: 'K' - Uppercase letter

    • Add to map: K with count 4 * 1 = 4
    • Reset freq = 0
    • map = {O: 14, S: 4, N: 2, K: 4}

Final step - Generate output:

  • Sort keys alphabetically: [K, N, O, S]
  • Build result string:
    • K has count 4, append "K4"
    • N has count 2, append "N2"
    • O has count 14, append "O14"
    • S has count 4, append "S4"
  • Result: "K4N2O14S4"

The key insight is how the multiplier changes as we enter ()) and exit (() parentheses groups, always maintaining the correct multiplication factor for each element we encounter.

Solution Implementation

1def countOfAtoms(formula: str) -> str:
2    """
3    Counts atoms in a chemical formula and returns them in alphabetical order
4  
5    Args:
6        formula: Chemical formula string (e.g., "H2O", "Mg(OH)2")
7  
8    Returns:
9        Formatted string with atom counts (e.g., "H2O", "H2MgO2")
10    """
11  
12    def get_count(formula: str, factor: int = 1) -> dict:
13        """
14        Recursively counts atoms in a formula with a multiplication factor
15      
16        Args:
17            formula: Formula or sub-formula to process
18            factor: Multiplication factor for nested groups
19      
20        Returns:
21            Dictionary mapping atom names to their counts
22        """
23        formula_length = len(formula)
24        atom_counts = {}
25        current_token = []
26        atom = ''
27        count = 0
28      
29        index = 0
30        while index <= formula_length:
31            # Handle opening parenthesis - find matching closing parenthesis
32            if index < formula_length and formula[index] == '(':
33                stack = ['(']
34                closing_index = index
35              
36                # Find the matching closing parenthesis
37                while stack:
38                    closing_index += 1
39                    if formula[closing_index] == '(':
40                        stack.append('(')
41                    elif formula[closing_index] == ')':
42                        stack.pop()
43              
44                # Extract the molecule within parentheses
45                molecule_in_parentheses = formula[index + 1:closing_index]
46                multiplier_digits = []
47              
48                # Extract multiplier after closing parenthesis
49                closing_index += 1
50                while closing_index < formula_length and is_digit(formula[closing_index]):
51                    multiplier_digits.append(formula[closing_index])
52                    closing_index += 1
53              
54                # Recursively process the molecule with its multiplier
55                multiplier = int(''.join(multiplier_digits)) if multiplier_digits else 1
56                nested_counts = get_count(molecule_in_parentheses, multiplier)
57              
58                # Add nested atom counts to current counts
59                for nested_atom, nested_count in nested_counts.items():
60                    atom_counts[nested_atom] = atom_counts.get(nested_atom, 0) + nested_count * factor
61              
62                index = closing_index
63                continue
64          
65            # Process accumulated token when we hit end or next uppercase letter
66            if current_token and (index >= formula_length or is_upper_case(formula[index])):
67                atom, count = parse_atom_with_count(current_token)
68                count *= factor
69                atom_counts[atom] = atom_counts.get(atom, 0) + count
70                current_token = []
71          
72            # Add current character to token if not at end
73            if index < formula_length:
74                current_token.append(formula[index])
75          
76            index += 1
77      
78        return atom_counts
79  
80    def parse_atom_with_count(token_chars: list) -> tuple:
81        """
82        Parses an atom token to extract atom name and count
83      
84        Args:
85            token_chars: List of characters forming the atom token
86      
87        Returns:
88            Tuple of (atom name, count)
89        """
90        token_string = ''.join(token_chars)
91      
92        # Extract atom name (letters) and count (digits)
93        atom = ''
94        count_str = ''
95      
96        for char in token_string:
97            if char.isalpha():
98                atom += char
99            elif char.isdigit():
100                count_str += char
101      
102        count = int(count_str) if count_str else 1
103        return atom, count
104  
105    def is_digit(character: str) -> bool:
106        """
107        Checks if a character is a digit
108      
109        Args:
110            character: Character to check
111      
112        Returns:
113            True if character is a digit
114        """
115        return character.isdigit()
116  
117    def is_upper_case(character: str) -> bool:
118        """
119        Checks if a character is uppercase
120      
121        Args:
122            character: Character to check
123      
124        Returns:
125            True if character is uppercase
126        """
127        return character.isupper()
128  
129    # Get atom counts and format the result
130    counts = get_count(formula)
131  
132    # Sort atoms alphabetically and format output
133    sorted_atoms = sorted(counts.items(), key=lambda x: x[0])
134    result = []
135  
136    for atom, count in sorted_atoms:
137        if count > 1:
138            result.append(f"{atom}{count}")
139        else:
140            result.append(atom)
141  
142    return ''.join(result)
143
1class Solution {
2    public String countOfAtoms(String formula) {
3        // Map to store element names and their total counts
4        Map<String, Integer> elementCountMap = new HashMap<>();
5      
6        // Stack to keep track of multipliers when entering nested parentheses
7        int[] multiplierStack = new int[1000];
8        int stackTop = 0;
9      
10        // Current multiplier for elements (affected by parentheses)
11        int currentMultiplier = 1;
12      
13        // Frequency/count number being parsed
14        int currentFrequency = 0;
15      
16        // Convert formula string to char array for easier manipulation
17        char[] formulaChars = formula.toCharArray();
18      
19        // Process formula from right to left
20        for (int i = formulaChars.length - 1; i >= 0; i--) {
21          
22            // Handle lowercase letters (part of multi-character element names)
23            if (formulaChars[i] >= 'a' && formulaChars[i] <= 'z') {
24                int endIndex = i;
25                i--;
26              
27                // Continue collecting lowercase letters for the element name
28                while (i >= 0 && formulaChars[i] >= 'a' && formulaChars[i] <= 'z') {
29                    i--;
30                }
31              
32                // Extract the complete element name (uppercase + lowercase letters)
33                String elementName = new String(formulaChars, i, endIndex - i + 1);
34              
35                // Add element count to map (use frequency if specified, otherwise 1)
36                int count = Math.max(currentFrequency, 1) * currentMultiplier;
37                elementCountMap.put(elementName, elementCountMap.getOrDefault(elementName, 0) + count);
38              
39                // Reset frequency for next element
40                currentFrequency = 0;
41            }
42            // Handle uppercase letters (single character element or start of multi-character element)
43            else if (formulaChars[i] >= 'A' && formulaChars[i] <= 'Z') {
44                // Single character element name
45                String elementName = new String(formulaChars, i, 1);
46              
47                // Add element count to map
48                int count = Math.max(currentFrequency, 1) * currentMultiplier;
49                elementCountMap.put(elementName, elementCountMap.getOrDefault(elementName, 0) + count);
50              
51                // Reset frequency for next element
52                currentFrequency = 0;
53            }
54            // Handle digits (element count or parentheses multiplier)
55            else if (formulaChars[i] >= '0' && formulaChars[i] <= '9') {
56                // Parse the digit
57                currentFrequency = formulaChars[i] - '0';
58                int placeValue = 10;
59              
60                // Continue parsing multi-digit numbers from right to left
61                while (i - 1 >= 0 && formulaChars[i - 1] >= '0' && formulaChars[i - 1] <= '9') {
62                    i--;
63                    currentFrequency += placeValue * (formulaChars[i] - '0');
64                    placeValue *= 10;
65                }
66            }
67            // Handle closing parenthesis ')' - entering a group from right to left
68            else if (formulaChars[i] == ')') {
69                // Save current multiplier to stack
70                multiplierStack[stackTop++] = currentMultiplier;
71              
72                // Update multiplier for elements inside parentheses
73                currentMultiplier *= Math.max(currentFrequency, 1);
74              
75                // Reset frequency
76                currentFrequency = 0;
77            }
78            // Handle opening parenthesis '(' - exiting a group from right to left
79            else {
80                // Restore previous multiplier from stack
81                currentMultiplier = multiplierStack[--stackTop];
82            }
83        }
84      
85        // Sort element names alphabetically
86        List<String> sortedElements = new ArrayList<>(elementCountMap.keySet());
87        Collections.sort(sortedElements);
88      
89        // Build the result string
90        StringBuilder result = new StringBuilder();
91        for (String element : sortedElements) {
92            result.append(element);
93          
94            // Append count only if greater than 1
95            int elementCount = elementCountMap.get(element);
96            if (elementCount > 1) {
97                result.append(elementCount);
98            }
99        }
100      
101        return result.toString();
102    }
103}
104
1#include <string>
2#include <unordered_map>
3#include <vector>
4#include <algorithm>
5#include <cctype>
6
7class Solution {
8public:
9    /**
10     * Counts atoms in a chemical formula and returns them in alphabetical order
11     * @param formula - Chemical formula string (e.g., "H2O", "Mg(OH)2")
12     * @return Formatted string with atom counts (e.g., "H2O", "H2MgO2")
13     */
14    string countOfAtoms(string formula) {
15        // Get atom counts and format the result
16        unordered_map<string, int> counts = getCount(formula, 1);
17      
18        // Sort atoms alphabetically
19        vector<pair<string, int>> sortedCounts(counts.begin(), counts.end());
20        sort(sortedCounts.begin(), sortedCounts.end(), 
21             [](const pair<string, int>& a, const pair<string, int>& b) {
22                 return a.first < b.first;
23             });
24      
25        // Build result string
26        string result = "";
27        for (const auto& [atom, count] : sortedCounts) {
28            result += atom;
29            if (count > 1) {
30                result += to_string(count);
31            }
32        }
33      
34        return result;
35    }
36
37private:
38    /**
39     * Recursively counts atoms in a formula with a multiplication factor
40     * @param formula - Formula or sub-formula to process
41     * @param factor - Multiplication factor for nested groups
42     * @return Map of atom names to their counts
43     */
44    unordered_map<string, int> getCount(const string& formula, int factor) {
45        int formulaLength = formula.length();
46        unordered_map<string, int> atomCounts;
47        string currentToken = "";
48        string atom = "";
49        int count = 0;
50      
51        for (int index = 0; index <= formulaLength; index++) {
52            // Handle opening parenthesis - find matching closing parenthesis
53            if (index < formulaLength && formula[index] == '(') {
54                vector<char> stack = {'('};
55                int closingIndex = index;
56              
57                // Find the matching closing parenthesis
58                while (!stack.empty()) {
59                    closingIndex++;
60                    if (formula[closingIndex] == '(') {
61                        stack.push_back('(');
62                    } else if (formula[closingIndex] == ')') {
63                        stack.pop_back();
64                    }
65                }
66              
67                // Extract the molecule within parentheses
68                string moleculeInParentheses = formula.substr(index + 1, closingIndex - index - 1);
69                string multiplierDigits = "";
70              
71                // Extract multiplier after closing parenthesis
72                closingIndex++;
73                while (closingIndex < formulaLength && isDigit(formula[closingIndex])) {
74                    multiplierDigits += formula[closingIndex];
75                    closingIndex++;
76                }
77              
78                // Recursively process the molecule with its multiplier
79                int multiplier = multiplierDigits.empty() ? 1 : stoi(multiplierDigits);
80                unordered_map<string, int> nestedCounts = getCount(moleculeInParentheses, multiplier);
81              
82                // Add nested atom counts to current counts
83                for (const auto& [nestedAtom, nestedCount] : nestedCounts) {
84                    atomCounts[nestedAtom] += nestedCount * factor;
85                }
86              
87                index = closingIndex - 1;
88                continue;
89            }
90          
91            // Process accumulated token when we hit end or next uppercase letter
92            if (!currentToken.empty() && 
93                (index == formulaLength || (index < formulaLength && isUpperCase(formula[index])))) {
94                pair<string, int> atomAndCount = parseAtomWithCount(currentToken);
95                atom = atomAndCount.first;
96                count = atomAndCount.second * factor;
97                atomCounts[atom] += count;
98                currentToken.clear();
99            }
100          
101            if (index < formulaLength) {
102                currentToken += formula[index];
103            }
104        }
105      
106        return atomCounts;
107    }
108  
109    /**
110     * Parses an atom token to extract atom name and count
111     * @param token - String forming the atom token
112     * @return Pair of [atom name, count]
113     */
114    pair<string, int> parseAtomWithCount(const string& token) {
115        string atom = "";
116        string countStr = "";
117      
118        // Extract atom name (uppercase followed by lowercase letters)
119        int i = 0;
120        while (i < token.length() && !isdigit(token[i])) {
121            atom += token[i];
122            i++;
123        }
124      
125        // Extract count (remaining digits)
126        while (i < token.length() && isdigit(token[i])) {
127            countStr += token[i];
128            i++;
129        }
130      
131        int count = countStr.empty() ? 1 : stoi(countStr);
132        return {atom, count};
133    }
134  
135    /**
136     * Checks if a character is a digit
137     * @param character - Character to check
138     * @return True if character is a digit
139     */
140    bool isDigit(char character) {
141        return isdigit(character);
142    }
143  
144    /**
145     * Checks if a character is uppercase
146     * @param character - Character to check
147     * @return True if character is uppercase
148     */
149    bool isUpperCase(char character) {
150        return isupper(character);
151    }
152};
153
1/**
2 * Counts atoms in a chemical formula and returns them in alphabetical order
3 * @param formula - Chemical formula string (e.g., "H2O", "Mg(OH)2")
4 * @returns Formatted string with atom counts (e.g., "H2O", "H2MgO2")
5 */
6function countOfAtoms(formula: string): string {
7    /**
8     * Recursively counts atoms in a formula with a multiplication factor
9     * @param formula - Formula or sub-formula to process
10     * @param factor - Multiplication factor for nested groups
11     * @returns Object mapping atom names to their counts
12     */
13    const getCount = (formula: string, factor: number = 1): Record<string, number> => {
14        const formulaLength = formula.length;
15        const atomCounts: Record<string, number> = {};
16        const currentToken: string[] = [];
17        let atom: string = '';
18        let count: number = 0;
19
20        for (let index = 0; index <= formulaLength; index++) {
21            // Handle opening parenthesis - find matching closing parenthesis
22            if (formula[index] === '(') {
23                const stack: string[] = ['('];
24                let closingIndex = index;
25              
26                // Find the matching closing parenthesis
27                while (stack.length > 0) {
28                    closingIndex++;
29                    if (formula[closingIndex] === '(') {
30                        stack.push('(');
31                    } else if (formula[closingIndex] === ')') {
32                        stack.pop();
33                    }
34                }
35
36                // Extract the molecule within parentheses
37                const moleculeInParentheses = formula.slice(index + 1, closingIndex);
38                const multiplierDigits: string[] = [];
39
40                // Extract multiplier after closing parenthesis
41                while (isDigit(formula[++closingIndex])) {
42                    multiplierDigits.push(formula[closingIndex]);
43                }
44
45                // Recursively process the molecule with its multiplier
46                const multiplier = multiplierDigits.length > 0 ? parseInt(multiplierDigits.join('')) : 1;
47                const nestedCounts = getCount(moleculeInParentheses, multiplier);
48              
49                // Add nested atom counts to current counts
50                for (const [nestedAtom, nestedCount] of Object.entries(nestedCounts)) {
51                    atomCounts[nestedAtom] = (atomCounts[nestedAtom] ?? 0) + nestedCount * factor;
52                }
53
54                index = closingIndex - 1;
55                continue;
56            }
57
58            // Process accumulated token when we hit end or next uppercase letter
59            if (currentToken.length > 0 && (!formula[index] || isUpperCase(formula[index]))) {
60                [atom, count] = parseAtomWithCount(currentToken);
61                count *= factor;
62                atomCounts[atom] = (atomCounts[atom] ?? 0) + count;
63                currentToken.length = 0;
64            }
65
66            currentToken.push(formula[index]);
67        }
68
69        return atomCounts;
70    };
71
72    // Get atom counts and format the result
73    const counts = getCount(formula);
74    return Object.entries(counts)
75        .sort(([atomA], [atomB]) => atomA.localeCompare(atomB))
76        .map(([atom, count]) => count > 1 ? `${atom}${count}` : atom)
77        .join('');
78}
79
80// Regular expressions for atom parsing and character checks
81const atomRegex = /(\D+)(\d+)?/;
82const upperCaseRegex = /[A-Z]+/;
83
84/**
85 * Parses an atom token to extract atom name and count
86 * @param tokenChars - Array of characters forming the atom token
87 * @returns Tuple of [atom name, count]
88 */
89const parseAtomWithCount = (tokenChars: string[]): [string, number] => {
90    const tokenString = tokenChars.join('');
91    const matches = atomRegex.exec(tokenString)!;
92    const atom = matches[1];
93    const count = matches[2] ? parseInt(matches[2]) : 1;
94    return [atom, count];
95};
96
97/**
98 * Checks if a character is a digit
99 * @param character - Character to check
100 * @returns True if character is a digit
101 */
102const isDigit = (character: string): boolean => {
103    return !Number.isNaN(Number.parseInt(character));
104};
105
106/**
107 * Checks if a character is uppercase
108 * @param character - Character to check
109 * @returns True if character is uppercase
110 */
111const isUpperCase = (character: string): boolean => {
112    return upperCaseRegex.test(character);
113};
114

Time and Space Complexity

Time Complexity: O(n + k log k) where n is the length of the input formula string and k is the number of unique atoms.

  • The main loop traverses the formula string once from right to left: O(n)
  • Within the loop:
    • Parsing lowercase letters for multi-character atoms: Each character is visited at most once, contributing O(1) amortized per character
    • Parsing uppercase letters for single-character atoms: O(1) per character
    • Parsing digits to build numbers: Each digit is processed once, O(1) amortized per digit
    • HashMap operations (put, getOrDefault): O(1) average case per operation
    • Stack operations for parentheses: O(1) per operation
  • After parsing, sorting the keys: O(k log k) where k is the number of unique atoms
  • Building the final string: O(k) for iterating through sorted keys

Overall: O(n) for parsing + O(k log k) for sorting = O(n + k log k)

Space Complexity: O(n + k)

  • HashMap to store atoms and their counts: O(k) where k is the number of unique atoms
  • Stack array of fixed size 1000: O(1) (though technically allocated as O(1000), it's constant)
  • Character array c from toCharArray(): O(n)
  • List of keys: O(k)
  • StringBuilder for output: O(n) in worst case (output length is bounded by input length plus count digits)
  • Temporary strings created during parsing: O(n) total across all atom names

Overall: O(n + k) dominated by the character array and potential output size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Multi-Digit Numbers

When parsing numbers that follow elements or closing parentheses, a common mistake is only reading a single digit instead of the complete multi-digit number. For example, in Ca(OH)12, the multiplier is 12, not just 1.

Pitfall Example:

# Wrong: Only reads one digit
if formula[i].isdigit():
    count = int(formula[i])

Solution:

# Correct: Reads all consecutive digits
count_str = ''
while i < len(formula) and formula[i].isdigit():
    count_str += formula[i]
    i += 1
count = int(count_str) if count_str else 1

2. Mishandling Nested Parentheses

A frequent error is not properly tracking multiplication factors when parentheses are nested. Each level of nesting requires maintaining its own multiplier, and these multipliers must be combined correctly.

Pitfall Example:

# Wrong: Doesn't properly handle nested multipliers
if char == '(':
    # Process without maintaining multiplier stack
    multiplier = get_number_after_closing()

Solution:

# Correct: Use a stack to maintain multipliers at each nesting level
if char == ')':  # Processing right-to-left
    stack.append(current_multiplier)
    current_multiplier *= get_following_number()
elif char == '(':  # Processing right-to-left
    current_multiplier = stack.pop()

3. Element Name Parsing Errors

Elements can have lowercase letters (like Ca, Mg), and failing to capture the complete element name is a common mistake. Reading only the uppercase letter would incorrectly parse "Ca" as "C" with "a" being treated separately.

Pitfall Example:

# Wrong: Only captures uppercase letter
if char.isupper():
    element = char
    add_to_map(element, count)

Solution:

# Correct: Captures uppercase followed by all lowercase letters
if char.isupper():
    element = char
    j = i + 1
    while j < len(formula) and formula[j].islower():
        element += formula[j]
        j += 1
    add_to_map(element, count)

4. Incorrect Order of Operations When Processing Right-to-Left

When processing the formula from right to left, the order of building numbers and element names must be reversed. Numbers that appear before elements (when reading left-to-right) must be accumulated correctly.

Pitfall Example:

# Wrong: Building number incorrectly when going right-to-left
freq = 0
for digit in reversed_digits:
    freq = freq * 10 + int(digit)  # Wrong order

Solution:

# Correct: Building number with proper positional values
freq = 0
power = 1
for digit in digits_right_to_left:
    freq += int(digit) * power
    power *= 10

5. Forgetting Default Count of 1

When an element or group has no explicit number, its count should default to 1. Missing this leads to incorrect atom counts.

Pitfall Example:

# Wrong: Doesn't handle missing count
count = freq  # freq could be 0 if no number was found

Solution:

# Correct: Uses 1 as default when no number is specified
count = freq if freq > 0 else 1
# Or more concisely:
count = max(freq, 1)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More