Number of Atoms solution and explanation
Google
9 more videos on this problem
Number of Atoms | Made Easy | Full Dry Run | Leetcode 726 | Google | codestorywithMIKcodestorywithMIK · 38:07 · 13K views
Number of Atoms - Leetcode 726 - PythonNeetCodeIO · 32:33 · 12K views
726. Number of Atoms | Stack | Pre-processing | O(nlogn) time | 2 Approaches @codeWithAryanBhaiAryan Mittal · 32:05 · 5K views
LeetCode 726. Number of AtomsHappy Coding · 32:30 · 5K views
Google Coding Interview Question | Leetcode 726 | Number of AtomsWorkWithGoogler · 11:22 · 2K views
726. Number of Atoms (Leetcode Hard)Programming Live with Larry · 47:38 · 1K views
726 number of atomsJimmy Wang · 4:50 · 785 views
726. Number of Atoms Leetcode Editorial || Hard Problem || Stack || Best Explanation || #coding#potdSrajan Agrawal · 39:09 · 496 views
Number of Atoms (LeetCode 726) (Hard) (Stack, Map, Sorting)CodeWithARB · 42:01 · 358 views
LeetCode 726 - Number of Atoms - JavaAlpha-Code · 20:44 · 211 views
The problem
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.
from collections import defaultdict
def count_of_atoms(formula: str) -> str:
def parse_formula(index):
count = defaultdict(int)
while index < len(formula):
if formula[index] == '(':
sub_count, index = parse_formula(index + 1)
multiplier = 1
start = index
while index < len(formula) and formula[index].isdigit():
index += 1
if index > start:
multiplier = int(formula[start:index])
for atom in sub_count:
count[atom] += sub_count[atom] * multiplier
elif formula[index] == ')':
return count, index + 1
else:
i = index
index += 1
while index < len(formula) and formula[index].islower():
index += 1
atom = formula[i:index]
start = index
while index < len(formula) and formula[index].isdigit():
index += 1
multiplicity = int(formula[start:index] or 1)
count[atom] += multiplicity
return count, index
total_count, _ = parse_formula(0)
sorted_atoms = sorted(total_count.keys())
return ''.join([f"{atom}{total_count[atom] if total_count[atom] > 1 else ''}" for atom in sorted_atoms])import java.util.*;
public class Solution {
public String countOfAtoms(String formula) {
Map<String, Integer> map = parseFormula(formula, new int[]{0});
StringBuilder res = new StringBuilder();
for (String name : map.keySet()) {
res.append(name);
int count = map.get(name);
if (count > 1) res.append(count);
}
return res.toString();
}
private Map<String, Integer> parseFormula(String formula, int[] index) {
Map<String, Integer> count = new TreeMap<>();
while (index[0] < formula.length()) {
char current = formula.charAt(index[0]);
if (current == '(') {
index[0]++;
Map<String, Integer> subMap = parseFormula(formula, index);
int multiplier = 1, start = index[0];
while (index[0] < formula.length() && Character.isDigit(formula.charAt(index[0]))) {
index[0]++;
}
if (start < index[0]) {
multiplier = Integer.parseInt(formula.substring(start, index[0]));
}
for (String key : subMap.keySet()) {
count.put(key, count.getOrDefault(key, 0) + subMap.get(key) * multiplier);
}
} else if (current == ')') {
index[0]++;
return count;
} else {
int start = index[0]++;
while (index[0] < formula.length() && Character.isLowerCase(formula.charAt(index[0]))) {
index[0]++;
}
String name = formula.substring(start, index[0]);
start = index[0];
while (index[0] < formula.length() && Character.isDigit(formula.charAt(index[0]))) {
index[0]++;
}
int multiplicity = (start < index[0]) ? Integer.parseInt(formula.substring(start, index[0])) : 1;
count.put(name, count.getOrDefault(name, 0) + multiplicity);
}
}
return count;
}
}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.
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.
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
string countOfAtoms(string formula) {
stack<map<string, int>> stk;
map<string, int> current_map;
int i = 0;
while (i < formula.length()) {
if (formula[i] == '(') {
stk.push(current_map);
current_map.clear();
i++;
} else if (formula[i] == ')') {
i++;
int start = i, multiplicity = 1;
while (i < formula.length() && isdigit(formula[i])) i++;
if (start < i) multiplicity = stoi(formula.substr(start, i - start));
if (!stk.empty()) {
map<string, int> temp_map = current_map;
current_map = stk.top();
stk.pop();
for (auto &pair : temp_map) {
current_map[pair.first] += pair.second * multiplicity;
}
}
} else {
int start = i++;
while (i < formula.length() && islower(formula[i])) i++;
string atom = formula.substr(start, i - start);
start = i;
while (i < formula.length() && isdigit(formula[i])) i++;
int multiplicity = (start < i) ? stoi(formula.substr(start, i - start)) : 1;
current_map[atom] += multiplicity;
}
}
string result;
for (auto &pair : current_map) {
result += pair.first + (pair.second > 1 ? to_string(pair.second) : "");
}
return result;
}
int main() {
string formula = "Mg(OH)2";
cout << countOfAtoms(formula) << endl;
return 0;
}function countOfAtoms(formula) {
let i = 0;
const stack = [{}];
while (i < formula.length) {
if (formula[i] === '(') {
stack.push({});
i++;
} else if (formula[i] === ')') {
i++;
let start = i, multiplier = 1;
while (i < formula.length && !isNaN(parseInt(formula[i]))) {
i++;
}
if (start < i) {
multiplier = parseInt(formula.substring(start, i));
}
const top = stack.pop();
const currentMap = stack[stack.length - 1];
for (let atom in top) {
currentMap[atom] = (currentMap[atom] || 0) + top[atom] * multiplier;
}
} else {
let start = i++;
while (i < formula.length && formula[i] >= 'a' && formula[i] <= 'z') {
i++;
}
const atom = formula.substring(start, i);
start = i;
while (i < formula.length && formula[i] >= '0' && formula[i] <= '9') {
i++;
}
const multiplicity = start < i ? parseInt(formula.substring(start, i)) : 1;
const currentMap = stack[stack.length - 1];
currentMap[atom] = (currentMap[atom] || 0) + multiplicity;
}
}
const result = [];
const finalMap = stack.pop();
Object.keys(finalMap).sort().forEach(atom => {
result.push(atom + (finalMap[atom] > 1 ? finalMap[atom] : ''));
});
return result.join('');
}
console.log(countOfAtoms('K4(ON(SO3)2)2'));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.
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
function countOfAtoms(formula: string): string {
const getCount = (formula: string, factor = 1) => {
const n = formula.length;
const cnt: Record<string, number> = {};
const s: string[] = [];
let [atom, c] = ['', 0];
for (let i = 0; i <= n; i++) {
if (formula[i] === '(') {
const stk: string[] = ['('];
let j = i;
while (stk.length) {
j++;
if (formula[j] === '(') stk.push('(');
else if (formula[j] === ')') stk.pop();
}
const molecule = formula.slice(i + 1, j);
const nextFactor: string[] = [];
while (isDigit(formula[++j])) {
nextFactor.push(formula[j]);
}
const nextC = getCount(molecule, +nextFactor.join('') || 1);
for (const [atom, c] of Object.entries(nextC)) {
cnt[atom] = (cnt[atom] ?? 0) + c * factor;
}
i = j - 1;
continue;
}
if (s.length && (!formula[i] || isUpper(formula[i]))) {
[atom, c] = getAtom(s);
c *= factor;
cnt[atom] = (cnt[atom] ?? 0) + c;
s.length = 0;
}
s.push(formula[i]);
}
return cnt;
};
return Object.entries(getCount(formula))
.sort(([a], [b]) => a.localeCompare(b))
.map(([a, b]) => (b > 1 ? a + b : a))
.join('');
}
const regex = {
atom: /(\D+)(\d+)?/,
isUpper: /[A-Z]+/,
};
const getAtom = (s: string[]): [string, number] => {
const [_, atom, c] = regex.atom.exec(s.join(''))!;
return [atom, c ? +c : 1];
};
const isDigit = (ch: string) => !Number.isNaN(Number.parseInt(ch));
const isUpper = (ch: string) => regex.isUpper.test(ch);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 | – |
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 |
Frequently asked questions
Is Number of Atoms easy or hard?
Number of Atoms is classified as a Hard problem because it combines string parsing, nested scope handling, and correct multiplier propagation. Implementing a robust parser with stacks or recursion requires careful edge-case handling and attention to detail.
How to solve Number of Atoms in O(n)?
The parsing stage itself runs in O(n) by scanning the string once and using a stack to track nested groups. Each atom name and count is processed exactly once. The only non-linear step is sorting the final atom names for output, which adds O(k log k) time.
Number of Atoms Python or Java solution?
Both Python and Java solutions typically use a stack of hash maps. Python implementations often use collections.Counter or defaultdict, while Java versions use HashMap with a Stack or Deque. The algorithmic structure remains identical across languages.
What is the best approach for Number of Atoms?
The most reliable approach uses a stack to parse the formula and track nested groups. Each stack frame stores a hash map of atom counts. When a closing parenthesis appears, the map is multiplied by the following number and merged into the previous scope. This handles deeply nested formulas while keeping the parsing logic linear.
What data structure is used in Number of Atoms?
The core data structures are a stack and a hash table. The stack manages nested parentheses scopes, while the hash table stores atom frequency counts for each scope. Sorting is applied at the end to produce atoms in lexicographic order.
What is the time complexity of Number of Atoms?
Parsing the formula takes O(n) time because each character is processed once. After collecting atom counts, the unique atom names must be sorted lexicographically, which costs O(k log k) where k is the number of distinct atoms. The overall complexity is O(n + k log k) with O(n) space.
Is Number of Atoms asked at Google, Amazon, or Meta?
Parsing problems with nested structures frequently appear in interviews at companies like Google, Amazon, and Meta. Number of Atoms specifically tests string parsing, stack usage, and hash map aggregation, which are common patterns in backend and systems interviews.