Number of Atoms - Solution & Explanation
Problem Statement
Given a string formula representing a chemical formula, return the count of each atom.
The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.
One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow.
- For example,
"H2O"and"H2O2"are possible, but"H1O2"is impossible.
Two formulas are concatenated together to produce another formula.
- For example,
"H2O2He3Mg4"is also a formula.
A formula placed in parentheses, and a count (optionally added) is also a formula.
- For example,
"(H2O2)"and"(H2O2)3"are formulas.
Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
The test cases are generated so that all the values in the output fit in a 32-bit integer.
Example 1:
Input: formula = "H2O"
Output: "H2O"
Explanation: The count of elements are {'H': 2, 'O': 1}.
Example 2:
Input: formula = "Mg(OH)2"
Output: "H2MgO2"
Explanation: The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.
Example 3:
Input: formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation: The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.
Constraints:
1 <= formula.length <= 1000formulaconsists of English letters, digits,'(', and')'.formulais always valid.
Approach Overview
Problem Overview: The formula string represents a chemical compound such as "K4(ON(SO3)2)2". Each atom may have a count, and parentheses indicate grouped multipliers. Your job is to parse the formula, correctly apply nested multipliers, and return the total count of every atom in lexicographic order.
Approach 1: Recursive Parsing with Stack (O(n + k log k) time, O(n) space)
This approach treats the formula like a recursive grammar. When you encounter (, recursively parse the inner expression until the matching ). Each recursive call returns a frequency map of atoms found inside the group. After the closing parenthesis, read the numeric multiplier and multiply all counts in that map before merging them into the parent scope.
A hash table stores atom frequencies during parsing. The parser scans the string character by character, building atom names (uppercase followed by lowercase letters) and their counts. Nested groups naturally map to recursive calls, which keeps the logic clean and mirrors the structure of the formula. After parsing completes, sort the atom names alphabetically using sorting and construct the output string.
This method is intuitive because it directly models the nested structure of chemical formulas. Time complexity is O(n + k log k), where n is the formula length and k is the number of unique atoms that must be sorted.
Approach 2: Iterative Stack-Based Parsing (O(n + k log k) time, O(n) space)
The iterative version replaces recursion with an explicit stack. Each stack frame stores a map of atom counts for the current scope. When you see (, push a new empty map onto the stack. When you encounter ), pop the top map, read the multiplier that follows, scale all counts, and merge them into the previous map.
Atom parsing works the same way as in the recursive approach. Scan an uppercase letter, continue consuming lowercase characters to form the full atom name, then read any digits that represent the count. If no number follows, the count defaults to 1. Add the count to the map on the top of the stack.
This approach avoids recursion depth issues and is often preferred in languages where explicit stack management is clearer. The algorithm still processes each character once, giving O(n) parsing time, and the final step sorts atom keys to build the result string.
Recommended for interviews: The iterative stack-based parser is typically what interviewers expect. It demonstrates strong control over parsing logic, stack usage, and careful handling of nested multipliers. Explaining the recursive idea first shows conceptual understanding of the formula structure, while implementing the stack solution proves you can translate that idea into an efficient, production-style parser.
Approach 1: Recursive Parsing with Stack
This approach uses a recursive parsing strategy combined with a stack to handle the nested nature of formulas within parenthesis. When encountering a parenthesis, we call the function recursively to process the sub-formula, using the stack to apply multipliers correctly once recursion unwinds back to the outer level.
We create a recursive function parse_formula that tracks the current index in the formula. We loop through characters, processing each segment as either an atom, number, opening parenthesis, or closing parenthesis. For each atom or sub-formula, we determine its count and add it to a dictionary, which accumulates the counts of each atom in the current context. When encountering a closing parenthesis, we return from the recursion with the accumulated counts for that segment to be multiplied accordingly. Finally, the main function uses a sorted list of atoms for output formatting.
Complexity
Time Complexity: O(n), where n is the length of the formula, since we parse through each character once.
Space Complexity: O(n), due to the recursion stack and the storage of atom counts.
Approach 2: Iterative Stack-based Approach
This approach leverages an iterative stack-based strategy to process the formula without recursion. By using an explicit stack, the nested structure is managed more explicitly by keeping track of counts at each level of parentheses, applying multipliers when unwinding back.
This C++ solution uses an iterative approach with a stack to manage ongoing calculations and resolve nested parentheses structures. A map is maintained for the current level of parsing, storing atom counts and using a stack to save the state when entering new parentheses. On encountering a closing parenthesis, values are multiplied and merged back into the previous level. The std::map is employed for automatic alphabetical ordering of keys.
Code
C++
JavaScript
Complexity
Time Complexity: O(n), traversing through the formula.
Space Complexity: O(n), due to the stack's and map's memory usage.
Approach 3: Default Approach
Code
Java
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Parsing with Stack | Time Complexity: O(n), where n is the length of the formula, since we parse through each character once. |
| Iterative Stack-based Approach | Time Complexity: O(n), traversing through the formula. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Parsing with Stack | O(n + k log k) | O(n) | When modeling nested formulas naturally with recursion |
| Iterative Stack-Based Parsing | O(n + k log k) | O(n) | Preferred in interviews and production parsers without recursion |
Video Solution
Number of Atoms | Made Easy | Full Dry Run | Leetcode 726 | Google | codestorywithMIK • codestorywithMIK • 13,413 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Atoms easy or hard?
How to solve Number of Atoms in O(n)?
Number of Atoms Python or Java solution?
What is the best approach for Number of Atoms?
What data structure is used in Number of Atoms?
What is the time complexity of Number of Atoms?
Is Number of Atoms asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Number of Atoms with our built-in code editor and test cases.
Practice on FleetCode