Number of Atoms

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.

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.