# Number of Atoms

• Approach #2: Stack [Accepted] has a bug.
line 13 should be int iStart = ++i, count = 1;
line 15 should be int multiplicity = i > iStart ? Integer.parseInt(formula.substring(iStart, i)) : 1;

• @jul599 Thanks, corrected

• It's an interesting problem, but I don't think we have O(N) solution here.

All the solutions described above are O(N^2) and not O(N). In all of them we need to merge a internal formula into surrounding one, and thus if we have an input where the number of atoms is equal to number of nested formulas -
like A(B(C(D(E(F(G)2)2)2)2)2)2, then on every step the number of atoms to merge will increment - like 1, 2, 3, 4.. and therefore the total time is quadratic.

Here's the code that generate 1m input and apparently doesn't complete in a reasonable time:

T = ('a','b','c', 'd', 'e', 'f', 'g')
S = ""

for c1 in T:
for c2 in T:
for c3 in T:
for c4 in T:
for c5 in T:
for c6 in T:
for c7 in T:
S += c1.upper() + c2 + c3 + c4 + c5 + c6 + c7 + "("

S += "H20"
for i in range(0, len(T) ** len(T)):
S += ")2"

print("Number of atoms: " + str(len(S) / 10))

R = Solution().countOfAtoms(S)

print("Done: " + str(len(R)))
print("Result: " + R)

• @rassokhin Thanks. I corrected the article.

• Is not it O(N) solution complexity. Sketch: going in backwards order, e.g. get )3 push 3 to stack, multiplier = 3, get )2, push 2 to stack, multiplier: 3 * 2 = 6,
get O, use current multiplier O6, get (, pop 2 from stack, multiplier = 6 / 2 = 3
And so on. So O(N).

• I don't think O(N^2) is a tight upper bound. The tighter bound would be O(BN) since each token will be looked at at most O(B) times, where B is the number of bracketed expressions.

For example,

1. A(B(C(D(E(F3)4)5)6)7) --> Here, B = O(N), so O(N^2)
2. A(B(CDEFGHIJ)3)2 --> Here, N >> B, and we parse, each element O(B) times, so O(BN)

• Really great solutions! The following is the "missing" regular expression solution in Java :-)

``````import java.util.regex.*;

class Solution {
public String countOfAtoms(String formula) {
final Stack<Map<String, Integer>> stack = new Stack<>();
stack.push(new TreeMap<>());
final Pattern pattern = Pattern.compile("([A-Z][a-z]*)(\\d*)|(\\()|(\\))(\\d*)");
final Matcher matcher = pattern.matcher(formula);
while (matcher.find()) {
final String match = matcher.group();
if (match.equals("(")) {
stack.push(new TreeMap<>());
} else if (match.startsWith(")")) {
final Map<String, Integer> top = stack.pop();
final int multiple = match.length() > 1 ? Integer.parseInt(match.substring(1, match.length())) : 1;
for (final String name : top.keySet()) {
stack.peek().put(name, stack.peek().getOrDefault(name, 0) + top.get(name) * multiple);
}
} else {
int i = 1;
while (i < match.length() && Character.isLowerCase(match.charAt(i))) {
i++;
}
final String name = match.substring(0, i);
final int count = i < match.length() ? Integer.parseInt(match.substring(i, match.length())) : 1;
stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count);
}
}
final StringBuilder sb = new StringBuilder();
for (final String name : stack.peek().keySet()) {
sb.append(name);
final int count = stack.peek().get(name);
if (count > 1) {
sb.append(String.valueOf(count));
}
}
return sb.toString();
}
}
``````

• This can be solved in O(N log N) time and O(D + E) space where N is the number of characters, E is the number of elements, and D is the parenthesis depth. Without the requirement to sort the results, it could be solved in O(N) time.

• @Vroo How would you solve it on `O(D+E)` time? Do you have a sketch of your solution or an idea explaining the same?

• @dribvurhd I said O(D+E) space, not time. O(D+E) time is not possible since it may be that D+E << N. Yes, I wrote the code. It scans the string just twice: once to tokenize and once to count. I posted my comment because I was surprised to see all accepted answers using O(N^2) time.

• @Vroo Yes, you're right! `O(N)` w/o the sorting requirement with 2-passes should be possible.

• NONE of program gives right output may be logic help you but not give right solution ,

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.