This problem requires parsing nested chemical formulas while maintaining counts for each atom, handling multipliers and parentheses correctly. A stack-based approach allows managing state for nested groups, while a hash table aggregates counts efficiently. Carefully extracting element names and numeric multipliers ensures accurate output in lexicographical order.
Problem Statement
Given a string representing a chemical formula, return a string that lists each atom and its count in sorted order. Elements start with an uppercase letter followed by optional lowercase letters, and may be followed by digits indicating quantity.
Formulas can contain nested parentheses with multipliers; your task is to expand all groups correctly, sum counts for identical atoms, and output the canonical string with elements in lexicographical order and counts omitted if 1.
Examples
Example 1
Input: formula = "H2O"
Output: "H2O"
The count of elements are {'H': 2, 'O': 1}.
Example 2
Input: formula = "Mg(OH)2"
Output: "H2MgO2"
The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.
Example 3
Input: formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.
Constraints
- 1 <= formula.length <= 1000
- formula consists of English letters, digits, '(', and ')'.
- formula is always valid.
Solution Approach
Stack-Based Parsing for Nested Groups
Traverse the formula left to right, pushing and popping hash tables onto a stack whenever '(' or ')' are encountered. This handles nested multipliers correctly while maintaining local counts for each group.
Element Name and Count Extraction
When an uppercase letter is found, extract the full element name including subsequent lowercase letters. Parse digits immediately following the element to determine its count, defaulting to 1 if no digit is present.
Merging Counts and Sorting
After parsing, merge all stacked hash tables into a single global hash table. Sort the elements lexicographically and construct the output string by appending the element name followed by its count if greater than 1.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N \log N) |
| Space | O(N) |
Time complexity is O(N log N) due to sorting the final element counts, and space complexity is O(N) to store stack states and the hash table for all elements.
What Interviewers Usually Probe
- Candidate identifies stack usage for nested parentheses immediately.
- Correctly extracts element names and numeric counts without off-by-one errors.
- Merges counts and produces lexicographical output cleanly.
Common Pitfalls or Variants
Common pitfalls
- Misparsing multi-letter elements or ignoring lowercase letters.
- Failing to apply multipliers to entire nested groups correctly.
- Returning counts of 1 explicitly instead of omitting them in output.
Follow-up variants
- Formulas with deeply nested parentheses to stress stack usage.
- Formulas with long sequences of the same element to test aggregation logic.
- Formulas with missing multipliers to check default count handling.
How GhostInterview Helps
- Highlights stack-based state management for nested formulas.
- Provides element parsing and multiplier extraction guidance specific to this problem.
- Ensures merged counts are output in canonical lexicographical order automatically.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Number of Atoms?
The problem uses stack-based state management to handle nested parentheses and aggregate counts for each atom.
How do I handle multi-letter element names?
Always include lowercase letters following an uppercase initial when identifying an element, ensuring full name capture.
What should I do if an element has no numeric suffix?
Default the count to 1 and omit the number in the final output if the count is exactly one.
How are nested multipliers applied?
When a closing parenthesis is encountered, multiply all contained atom counts by the number following the parentheses before merging to the outer level.
What is the expected output format?
List atoms in lexicographical order, appending counts only if greater than 1, forming the canonical string.
Need direct help with Number of Atoms instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Atoms from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Merge accounts by connecting emails and returning each user's sorted email list using array scanning and hash lookup efficiently.
Open problem page#720 Longest Word in DictionaryFind the longest word in a dictionary that can be built one character at a time from other words in the dictionary.
Open problem page#736 Parse Lisp ExpressionParse Lisp expressions using stack-based state management to evaluate variables and operations.
Open problem page