How do you solve Number of Atoms on LeetCode?

Number of Atoms (LeetCode #726) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding how to handle nested structures (like parentheses) is crucial for parsing complex formulas.

What is the brute force solution for Number of Atoms?

The brute force approach for Number of Atoms is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves parsing the formula character by character, identifying elements, their counts, and handling parentheses recursively. This method is straightforward but can be inefficient due to repeated parsing. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Atoms?

Number of Atoms uses the following concepts: Hash Table, String, Stack, Sorting. The recommended patterns to study are: Stack, Hash Map.

What are the interview tips for Number of Atoms?

Always clarify the input format and constraints before diving into the solution. Think aloud during the interview to show your thought process and help the interviewer guide you. Practice writing clean and efficient code; focus on readability and maintainability.

What are common mistakes when solving Number of Atoms?

Forgetting to handle the case where a multiplier follows a closing parenthesis. Not properly managing the scope of atom counts when dealing with nested parentheses.

#726

Number of Atoms

Hard

Hash TableStringStackSortingStackHash Map

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution improves efficiency by using a stack to handle nested parentheses and directly counting atoms in a single pass. This reduces the need for repeated parsing and allows for a more straightforward implementation.

⚙️

Algorithm

5 steps

1Step 1: Initialize a stack to manage counts and a dictionary for atom counts.
2Step 2: Loop through each character in the formula. If an uppercase letter is found, extract the full atom name and check for a following digit to determine its count.
3Step 3: If a '(' is encountered, push the current atom count dictionary onto the stack and start a new one.
4Step 4: If a ')' is encountered, pop the top dictionary from the stack and multiply its counts by any digit that follows.
5Step 5: After parsing, sort the dictionary keys and format the output string based on the counts.

solution.py33 lines

1# Full working Python code
2from collections import defaultdict
3
4def countOfAtoms(formula):
5    stack = [defaultdict(int)]
6    i = 0
7    while i < len(formula):
8        if formula[i] == '(':  # Start of a new group
9            stack.append(defaultdict(int))
10            i += 1
11        elif formula[i] == ')':  # End of a group
12            i += 1
13            multiplier = 0
14            while i < len(formula) and formula[i].isdigit():
15                multiplier = multiplier * 10 + int(formula[i])
16                i += 1
17            multiplier = multiplier or 1
18            top = stack.pop()
19            for atom, c in top.items():
20                stack[-1][atom] += c * multiplier
21        else:
22            j = i + 1
23            while j < len(formula) and formula[j].islower():
24                j += 1
25            atom = formula[i:j]
26            i = j
27            multiplier = 0
28            while i < len(formula) and formula[i].isdigit():
29                multiplier = multiplier * 10 + int(formula[i])
30                i += 1
31            multiplier = multiplier or 1
32            stack[-1][atom] += multiplier
33    return ''.join(f'{atom}{count if count > 1 else ''}' for atom, count in sorted(stack[0].items()))

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once, and the space complexity is O(n) due to the stack and the atom count dictionary.

1Understanding how to handle nested structures (like parentheses) is crucial for parsing complex formulas.
2Using a stack can greatly simplify the management of nested counts and ensure correct multiplication.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.