Number of Atoms

Number of Atoms

What is this problem about?

The Number of Atoms problem gives you a chemical formula string like "H2O", "Mg(OH)2", or "K4(ON(SO3)2)2". Parse it to compute the total count of each element, accounting for nested parentheses and multipliers. Return the element counts in alphabetical order as a formatted string. This hard Number of Atoms coding problem combines stack-based expression parsing with hash map aggregation.

Why is this asked in interviews?

Apple, Microsoft, Amazon, Google, Bloomberg, and Confluent ask this because formula parsing tests advanced stack usage for nested structures — a pattern found in compilers, expression evaluators, and chemical informatics. The hash table, sorting, string, and stack interview pattern is fully exercised, and handling nested multipliers requires careful stack management.

Algorithmic pattern used

Stack of hash maps. Maintain a stack where each entry is a hash map of element counts for the current "scope" (inside a parenthesis block). Push a new map on '(', pop and merge (with multiplier) on ')'. For each element name + count outside parentheses, add to the current top map. After processing, the final map contains all element counts. Sort alphabetically and format.

Example explanation

Formula: "Mg(OH)2".

• 'M','g': push {Mg:1} to current scope.
• '(': push new scope {}.
• 'O','H': {O:1, H:1} in top scope.
• ')': pop with multiplier 2. Multiply: {O:2,H:2}. Merge into parent: {Mg:1,O:2,H:2}. Result: "H2MgO2".

Formula: "K4(ON(SO3)2)2". Nested parsing: inner "(SO3)2" → {S:2,O:6}. Merge with O:1, N:1 → {O:3,N:1,S:2}. Multiply by 2 → {O:6,N:2,S:4}. Add K:4 → {K:4,O:6,N:2,S:4}. Sorted: "K4N2O6S4".

Common mistakes candidates make

• Not handling multi-character element names (capital letter + optional lowercase).
• Not handling implicit count of 1 (e.g., 'H' means H:1, not H:0).
• Forgetting to multiply the inner map counts when popping from the stack.
• Sorting elements numerically instead of alphabetically.

Interview preparation tip

Formula parsing with nested groups is a stack problem. The key insight: each '(' pushes a new scope; each ')' pops it and multiplies before merging into the parent scope. Practice writing the parser in three phases: (1) element name extraction, (2) count parsing, (3) parenthesis handling with stack. Test with deeply nested formulas. This parsing pattern generalizes to JSON parsing, arithmetic expression evaluation, and HTML/XML parsing.