Number of Atoms — Solution in Python, Java & C++
Number of Atoms solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on strings and hash table.
Number of Atoms is a hard coding problem on strings, hash table and sorting, asked in Amazon, Google and Apple interviews.
- Difficulty: Hard
- Topics: Strings, Hash Table, Sorting, Stack
- Asked at: Amazon, Google, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A chemical formula is built from these pieces:
- An atom name: one uppercase letter followed by zero or more lowercase letters, such as
H,MgorZn. - An optional count right after an atom: a number of at least 2 (a count of 1 is never written).
H2Ohas two hydrogen atoms and one oxygen atom. - Formulas can be concatenated (
H2O2He3Mg4) or wrapped in parentheses with an optional count that multiplies everything inside ((H2O2)3).
Return the number of atoms of each element as a string: the element names in sorted (lexicographic, by character code) order, each followed by its count if that count is more than 1.
Example 1
Input: formula = "C6H12O6"
Output: C6H12O6
Example 2
Input: formula = "Fe2(SO4)3"
Output: Fe2O12S3
Explanation: The group SO4 is tripled: 3 sulfur and 12 oxygen atoms.
Example 3
Input: formula = "(NH4)3PO4"
Output: H12N3O4P
Constraints
1 <= formula.length <= 1000formula consists of English letters, digits, '(' and ')'formula is always validEvery count in the answer fits in a 32-bit integer
Hints for Number of Atoms
Hint 1
A count after
)multiplies every atom inside that group, and groups can nest.Hint 2
Reading the formula from right to left, you see each multiplier before the atoms it applies to.
Hint 3
Scan right to left with a stack of multipliers: digits build a pending number;
)pushestop × number;(pops; an uppercase letter ends an atom name — addtop × numberto its count. Sort the names at the end.
How to solve Number of Atoms
Scan the formula backwards. Then every count is met before what it multiplies, so a stack of cumulative multipliers gives each atom's factor directly — no recursion needed.
Approach
- Keep a stack of multipliers starting with
[1], a pending numbernum(built digit by digit from the right), and a map from atom name to count. - Digit: prepend it to
num. ): pushtop × (num or 1)and clearnum.(: pop.- Uppercase letter at
i: the atom name runs fromithrough the lowercase letters after it. Addtop × (num or 1)to its count and clearnum. Lowercase letters themselves are skipped — they are read with their uppercase letter. - Sort the names and write each with its count when the count exceeds 1.
Why it works
Right to left, an atom's own count is the number just read, and the groups enclosing it are exactly those whose ) has been seen but whose ( has not — the ones on the stack. Each stack entry already holds the product of all enclosing group counts, so the top is the total multiplier.
Complexity
- Time —
O(n + k log k) for k distinct atoms - Space —
O(n)
Pitfalls
- Counts can have several digits — when scanning backwards, build them with a place value, not by appending.
- A missing count means 1, both for atoms and for groups.
- Sort by character code:
Ccomes beforeCa, and every uppercase letter before every lowercase one.
Reference solution
Python
def countOfAtoms(formula: str) -> str:
n = len(formula)
counts = {}
mult = [1]
num = 0
place = 1
for i in range(n - 1, -1, -1):
c = formula[i]
if c.isdigit():
num += (ord(c) - 48) * place
place *= 10
elif c == ')':
mult.append(mult[-1] * (num if place > 1 else 1))
num, place = 0, 1
elif c == '(':
mult.pop()
elif c.isupper():
j = i + 1
while j < n and formula[j].islower():
j += 1
name = formula[i:j]
counts[name] = counts.get(name, 0) + mult[-1] * (num if place > 1 else 1)
num, place = 0, 1
return ''.join(name + (str(counts[name]) if counts[name] > 1 else '') for name in sorted(counts))Java
public static String countOfAtoms(String formula) {
int n = formula.length();
TreeMap<String, Long> counts = new TreeMap<>();
long[] mult = new long[n + 2];
int top = 0;
mult[top++] = 1;
long num = 0, place = 1;
for (int i = n - 1; i >= 0; i--) {
char c = formula.charAt(i);
if (c >= '0' && c <= '9') {
num += (c - '0') * place;
place *= 10;
} else if (c == ')') {
mult[top] = mult[top - 1] * (place > 1 ? num : 1);
top++;
num = 0;
place = 1;
} else if (c == '(') {
top--;
} else if (c >= 'A' && c <= 'Z') {
int j = i + 1;
while (j < n && formula.charAt(j) >= 'a' && formula.charAt(j) <= 'z') j++;
String name = formula.substring(i, j);
counts.merge(name, mult[top - 1] * (place > 1 ? num : 1), Long::sum);
num = 0;
place = 1;
}
}
StringBuilder sb = new StringBuilder();
for (Map.Entry<String, Long> e : counts.entrySet()) {
sb.append(e.getKey());
if (e.getValue() > 1) sb.append(e.getValue());
}
return sb.toString();
}C++
string countOfAtoms(string formula) {
int n = formula.size();
map<string, long long> counts;
vector<long long> mult(1, 1);
long long num = 0, place = 1;
for (int i = n - 1; i >= 0; i--) {
char c = formula[i];
if (c >= '0' && c <= '9') {
num += (c - '0') * place;
place *= 10;
} else if (c == ')') {
mult.push_back(mult.back() * (place > 1 ? num : 1));
num = 0;
place = 1;
} else if (c == '(') {
mult.pop_back();
} else if (c >= 'A' && c <= 'Z') {
int j = i + 1;
while (j < n && formula[j] >= 'a' && formula[j] <= 'z') j++;
counts[formula.substr(i, j - i)] += mult.back() * (place > 1 ? num : 1);
num = 0;
place = 1;
}
}
string out;
for (auto& e : counts) {
out += e.first;
if (e.second > 1) out += to_string(e.second);
}
return out;
}JavaScript
var countOfAtoms = function(formula) {
var n = formula.length;
var counts = new Map();
var mult = [1];
var num = 0, place = 1;
for (var i = n - 1; i >= 0; i--) {
var c = formula[i];
if (c >= "0" && c <= "9") {
num += (c.charCodeAt(0) - 48) * place;
place *= 10;
} else if (c === ")") {
mult.push(mult[mult.length - 1] * (place > 1 ? num : 1));
num = 0;
place = 1;
} else if (c === "(") {
mult.pop();
} else if (c >= "A" && c <= "Z") {
var j = i + 1;
while (j < n && formula[j] >= "a" && formula[j] <= "z") j++;
var name = formula.slice(i, j);
var add = mult[mult.length - 1] * (place > 1 ? num : 1);
counts.set(name, (counts.get(name) || 0) + add);
num = 0;
place = 1;
}
}
var names = Array.from(counts.keys()).sort();
var out = "";
for (var k = 0; k < names.length; k++) {
var cnt = counts.get(names[k]);
out += names[k] + (cnt > 1 ? String(cnt) : "");
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets