Number of Atoms - Leetcode 726 - Python 

As a java coder, I'm joining the python bandwagon

I really loved the way you started the video

I would love a 1 hr video to go over alternative solutions or going through how you think in a thorough way or certain patterns you noticed that could be applied to other problems. More information always helps :) thank you!

Major respect to those spending their Saturday night solving this behemoth.

I did using C++ 134 lines of code phew!

ngl having some sort of experience with compilers made this a LOT easier to come up with and understand

We are waiting for an hour-long analysis of the problem))

Yeah Neetcode I use to be a Java dude, but as you said I've joined python church like a year ago... seems like I miss Java but I also have a good run with python so far. 🙏Thanks for all the effort you've given to series of these priceless videos.

Hey nice approach. But I think if we traverse from the end of the formula it will be easier just keep a stack of the numbers and a value of the multiplied numbers till now . I'm sorry Im bad at explaining over comments

Knowing Go or Python is a blessing.

Love the dedication to post daily videos !

Kinda proud to be able to solve this by myself, especially in Java... Even though it took over an hour.

Easier approach, the one I had in mind is to use a stack to track the multiplication factor whenever you step into a pair of brackets and when you step out, simply divide. The way to know the value you are going to multiply with, either pre-process the input to figure out the values and hash each bracket index to its value, or you could start backwards where you have the value before processing the inner string, I prefer the first one eaiser to code although more space but we already paying that... anyway this was much easier than the stack of hashmaps, thought of sharing it..

Thanks

I really appreciate your hard work and dedication to solve problems for us. Thanks a lot Sir...🤗🤗🤗

how long did u take to solve it by urself ?

I thought of this approach and tried to make it work using a stack and a dictionary for about an hour, but I never knew you could store dictionaries in a stack (I know it's basic stuff). I thought it was ridiculous( I still do).

class Solution: #TC:O(n^2) #SC:O(n) # Stack of hashmaps def countOfAtoms(self, formula: str) -> str: stack = [defaultdict(int)] i = 0 while i < len(formula): if formula[i] == '(': stack.append(defaultdict(int)) elif formula[i] == ')': curr_map = stack.pop() prev_map = stack[-1] count = "" cnt = 1 while i+1

I had around 110 lines using C++ (brackets matching to create a stack of multipliers) admittedly there was some whitespace of course but it was a slog and it took me around an hour so not sure how this could be done in an interview setting.

Traversing the formula backward takes O(N). Then sort the built array and collect elements joining adjacent the same ones. Sorting takes O(n log n) time

The java solution isn't that bad! Here's a 66 line solution similar to yours. ``` class Solution { public String countOfAtoms(String formula) { Stack stack = new Stack(); stack.push(new HashMap()); int i = 0; int n = formula.length(); while (i < n) { if (formula.charAt(i) == '(') { stack.push(new HashMap()); i++; continue; } if (formula.charAt(i) == ')') { i++; int count = 0; while (i < n && Character.isDigit(formula.charAt(i))) { count *= 10; count += (formula.charAt(i) - '0'); i++; } count = Math.max(count, 1); Map map = stack.pop(); Map prevMap = stack.peek(); for (String s : map.keySet()) { prevMap.put(s, prevMap.getOrDefault(s, 0) + (map.get(s) * count)); } continue; } StringBuilder sb = new StringBuilder(); sb.append(formula.charAt(i)); i++; while (i < n && Character.isLowerCase(formula.charAt(i))) { sb.append(formula.charAt(i)); i++; } int count = 0; while (i < n && Character.isDigit(formula.charAt(i))) { count *= 10; count += (formula.charAt(i) - '0'); i++; } String name = sb.toString(); count = Math.max(count, 1); Map map = stack.peek(); map.put(name, map.getOrDefault(name, 0) + count); } Map map = stack.peek(); List keys = new ArrayList(map.keySet()); Collections.sort(keys); StringBuilder sb = new StringBuilder(); for (String key : keys) { sb.append(key); int count = map.get(key); if (count > 1) { sb.append(count); } } return sb.toString(); } } ```

Very nice explanation. Thanks for simplifying the complex hard problem and making it clear and simple.

Thank you so much. Watched this video and implemented in C++ on my own and got accepted

You save my weekend. Thanks my hero.

make 1hr videos and explain all the possible solutions

Great explanation and the code is very easy to comprehend

I don't mind if it is half hr or one hr or 2 hr video just for a single question. I would just love to grasp every bit of it.

Took about 60 lines to write in JavaScript. Here are my lessons: JavaScript has Regular Expressions. checking characters are even easier than Python. (as you know how to write it) Never use square brackets in JavaScript Map, always use get() and set().

Don't u think it would easy using a recursive method which keeps iterating from the Back of the String??

Thankyou for mentioning the Java developers.

lets convert input "Mg(OH)2" to ['Mg', '(', 'O', 'H', ')', '2'] , it will be easy to code and get the output class Solution: def preProcess(self,formula): fm = [] for f in formula: if f.islower() or (f.isdigit() and fm[-1].isdigit()): fm[-1]+=f else: fm.append(f) return fm def countOfAtoms(self, formula: str) -> str: hm = dict() formula = [""]+self.preProcess(formula)[::-1]+[""] d = 1 n = len(formula) stack = [] for i in range(1,n): f = formula[i] pf = formula[i-1] if f.isdigit(): d = d * int(f) elif f == ')': stack.append(pf) elif f == '(': x = stack.pop() if x.isdigit(): d = d//int(x) else: hm[f] = hm.get(f,0) + d if pf.isdigit(): d = d//int(pf) ans = list(hm.items()) ans.sort() final = "" for f,n in ans: if n == 1: final += f else: final += f + str(n) return final

poured a cup of tea, opened proble,, 37 mins of thinking & coding, done, tea cold

Thank you for the explanation

I tried the same way but i dont manage code like you do. You have a way of simplifying thr algorithm and coding.

I am Java person! thank you for the video :)

This was a really fun one

traversing backwards makes this slightly simpler

very cool problem,

That was really hard to code and follow even though after your explanation that solution kind of makes sense. I wouldn't image who could do that in a real interview in under 45 mins if that was a new problem for that person. Hmm, I wonder if I want to get a job at google I should solve these problems easily? P.S. In TS I've got 67 lines of code vs your 38 - omg!

Really frustrating in Cpp as well, problem seems to be lengthiest, but no simple solution found, logically not tough

At 19:47 N should be 2, not 1

i was doing it in js it was 79 lines

Brave person I am, get good I will

at least I come up with good question understanding😅

G.O.A.T!! 🙌🏻🙌🏻🙌🏻🙌🏻

it took me 2 hours to code this mammoth solution without seeing any solution

1 hour? no problem let's do it!

Keep the max 30 minutes Solutions but add bonus solutions at the end.

Cpp person here lol

implement 1 hour video

no 1 hours thanks

Longer Video ++

A lengthy code without stack of map class Solution: def countOfAtoms(self, formula: str) -> str: stack = [] i, n = 0, len(formula) while i < n: if formula[i] == ")": num = "" while i + 1 < n and formula[i + 1].isnumeric(): num += formula[i + 1] i += 1 num = int(num) if num else 1 arr = [] while stack[-1] != "(": if stack[-1].isnumeric(): new_frequency = num * int(stack.pop()) arr.append(str(new_frequency)) else: arr.append(stack.pop()) stack.pop() arr.reverse() stack.extend(arr) elif formula[i].isupper(): element, frequency = formula[i], "" while i + 1 < n and formula[i + 1].islower(): element += formula[i + 1] i += 1 while i + 1 < n and formula[i + 1].isnumeric(): frequency += formula[i + 1] i += 1 stack.append(element) stack.append(frequency if frequency else "1") else: stack.append(formula[i]) i += 1 freq_map = Counter() for i in range(0, len(stack), 2): freq_map[stack[i]] += int(stack[i + 1]) ans = "" for c in sorted(freq_map.keys()): if freq_map[c] == 1: ans += c else: ans += c + str(freq_map[c]) return ans

Hmm looks like I'm skipping this one, but it seems this does get easier after really understanding what the problem actually asks.

this question was something a hell lot

Java solution in 50 lines class Solution { public String countOfAtoms(String formula) { int n=formula.length(); Stack stc=new Stack(); Map sMap=new TreeMap(); stc.push(sMap); for(int i=0;i

Python solution - 28 lines: class Solution: def countOfAtoms(self, formula: str) -> str: atoms, element = defaultdict(int), deque() count, stack = deque(), ["1"] for character in reversed(formula): if character.isnumeric(): count.appendleft(character) elif character == ")": count.appendleft("0") stack.append(max(1, int("".join(count))) * int(stack[-1])) count.clear() elif character == "(": stack.pop() count.clear() elif character.islower(): element.appendleft(character) else: element.appendleft(character) count.appendleft("0") atoms["".join(element)] += max(1, int("".join(count))) * int(stack[-1]) element.clear() count.clear() return "".join( [ f"{element}{count}" if count > 1 else element for element, count in sorted(atoms.items()) ] )

I love solving problems, but today I am questioning my existence and I want to quit

Isn't this incorrect. The problem specifically states that there will be "zero or more lowercase characters"... Considering only two is against the problem description

I did this solution in rust. Before watching this, 110 lines of code and it's the O^2 solution. pub struct Solution; #[derive(Debug)] struct Atom { quantity: i32, symbol: String, } #[derive(Debug)] enum FormulaPiece { Atom(Atom), OpenParenthesis, CloseParenthesis(i32), } use std::collections::HashMap; use FormulaPiece::*; impl Solution { pub fn count_of_atoms(formula: String) -> String { let mut new_formula: Vec = vec![]; let mut prev_nums: Vec = vec![]; let mut prev_letters: Vec = vec![]; fn insert_atom( new_formula: &mut Vec, prev_nums: &mut Vec, prev_letters: &mut Vec, ) { if prev_letters.len() > 0 { let symbol: String = prev_letters.iter().collect(); let quantity = if prev_nums.len() == 0 { 1 } else { prev_nums.iter().fold(0, |prev, cur| prev * 10 + cur) }; new_formula.push(Atom(Atom { quantity, symbol })); prev_letters.clear(); prev_nums.clear(); } if prev_nums.len() > 0 { if let Some(CloseParenthesis(_)) = new_formula.last() { new_formula.pop(); new_formula.push(CloseParenthesis( prev_nums.iter().fold(0, |prev, cur| prev * 10 + cur), )); prev_nums.clear(); } } } for c in formula.chars() { match c { '(' => { insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters); new_formula.push(OpenParenthesis); } ')' => { insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters); new_formula.push(CloseParenthesis(1)); } '0'..='9' => prev_nums.push(c.to_digit(10).unwrap() as i32), 'A'..='Z' => { //if it's uppercase then I know that it's a new thing. insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters); prev_letters.push(c); } 'a'..='z' => prev_letters.push(c), _ => panic!("Should not happen"), } } insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters); let mut stack: Vec = vec![]; for form in new_formula { if let CloseParenthesis(num) = form { let mut new_stack = vec![]; while let Some(f) = stack.pop() { match f { OpenParenthesis => break, FormulaPiece::Atom(Atom { quantity, symbol }) => { new_stack.push(Atom(Atom { quantity: quantity * num, symbol, })) } _ => panic!("should not happen"), } } stack.extend(new_stack.into_iter()); } else { stack.push(form); } } let mut map: HashMap = HashMap::new(); for atm in stack { if let Atom(Atom { quantity, symbol }) = atm { *map.entry(symbol).or_insert(0) += quantity; } } let mut tup_elements: Vec = map.into_iter().collect(); tup_elements.sort_unstable(); tup_elements .into_iter() .map(|(mut key, qtd)| { if qtd > 1 { key.push_str(qtd.to_string().as_str()); } key }) .collect() } }

At 28:47, do I hear the hindi word "Accha"🤔

i love you man

if this question comes in your interview that means they don't want to hire you

Would hope such question never comes in interview.

bro is trolling java at this point

Upvote for Science👍👍

who's here after solving this question looking for an alternate approach

Solved it on my own. To much logic is required that makes it hard otherwise it is a medium STACK Problem.

this looks like a promotional video of python 😂😂😂

bro I am using Java, and I am understand most of the codes, but if there is a part I cannot understand, I will just call chatgpt to translate lol

28: class Solution: def countOfAtoms(self, f: str) -> str: s,l,p=[],len(f:='('+f+')'),0 while p

I solved it using a queue in a bfs fashion.

Hahaha let’s translate that

Java person here, neetcode should I switch to python? Where can I learn this?😊

Stack of HashMaps. Seriously?

I solved this in 50 lines of python code :(

Java coders watching this

First view and comment 😂

Give me 1% of your property

hello bro plz try to keep the solutions within 20 mins plz so that our concentration levels are high through out

wtf!! i did not solved the question yet but approach to solve this question is very simple. why the fuck this video is 33min long. what am i missing ??

class Solution { public: string countOfAtoms(string s) { int multiplier = 1; stack st1; map mpp; int n = s.size(); string t = ""; for(int i=n-1;i>=0;i--){ if(s[i] ='0'){ while(s[i]='0'){ t = s[i] + t; i--; } i++; int m = stoi(t); multiplier*=m; st1.push(m); } else if(s[i] == ')'){ t = ""; } else if(s[i] == '('){ if(!st1.empty()){ multiplier/=st1.top(); st1.pop(); } } else{ int m = 0; string p = ""; if(t == ""){ m=1; } if(s[i]='A'){ p+=s[i]; }else{ p = s[i-1]; p+=s[i]; i--; } mpp[p]+=multiplier; if(t!=""){ if(!st1.empty()){ multiplier/=st1.top(); st1.pop(); } } t=""; } } string ans = ""; for(auto it: mpp){ if(it.second!=0){ ans+=it.first; if(it.second > 1){ ans+=to_string(it.second); } } } //cout