Number of Atoms - Leetcode 726 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: www.linkedin.com/in/navdeep-singh-3aaa14161/
🐦 Twitter: neetcode1
⭐ BLIND-75 PLAYLIST: kzbin.info/www/bejne/gX3PiXZ8fJqHpKM
Problem Link: leetcode.com/problems/number-of-atoms/
0:00 - Read the problem
1:04 - Chemistry basics
4:51 - Build Intuition
13:06 - Dry Run
22:14 - Coding Explanation
leetcode 726
#neetcode #leetcode #python

[@singletmat5172]

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!

[@tcdesports5673]

The problem with that alternative solution is, it is not that efficient. I wrote that recursive solution itself first, but was like bottom 40 %tile in both speed and memory.

[@vishaalkumaranandan2894]

I really loved the way you started the video

[@mounirkanane8083]

Literally only reason why I watched the whole thing

[@yang5843]

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

[@loke_mc8053]

welcome to the gang yo

[@abhishekraparti5691]

We can't give up yet.

[@pastori2672]

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

[@peakchinmayism]

Hi, can you provide some context onto what you're talking about? How did you relate this to compilers? Some examples would help. Just curious :)) I have that course next semester so looking forward to it.

[@itsabdeeels]

@@peakchinmayism I think he's talking about the parsing part, doing the parsing of a compiler makes it much more easier to do the parsing of this problem.

[@pastori2672]

@@peakchinmayism it is like the thing that reads your code and translates it into either machine code or assembly.. etc, in this problem we deal with string input and return the correct form so its kinda like leetcode is the programmer writing code and you're translating it to the correct form its essentially just that, i recommend you start learning C++ if you haven't already and maybe dig deeper into compilers they are a great way to reinforce your understanding of how the underlying programming language works

[@peakchinmayism]

@@pastori2672 oh I got what you're trying to say. Thank you! I'm well versed in C++ though, don't have any experience with compilers yet. Looking forward to it.

[@BekaMan95]

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.

[@ParodyCSEDept]

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

[@pragadhishraajmp8871]

I got it in 44 lines class Solution { public: string countOfAtoms(string formula) { stack st; map m; int n = formula.size(); int i = 0; while (i < n) { if (formula[i] == '(') { st.push(m); m.clear(); i++; } else if (formula[i] == ')') { int i_start = ++i, multiplicity = 1; while (i < n && isdigit(formula[i])) i++; if (i > i_start) multiplicity = stoi(formula.substr(i_start, i - i_start)); if (!st.empty()) { auto top = st.top(); st.pop(); for (auto &p : m) top[p.first] += p.second * multiplicity; m = top; } } else { int i_start = i++; while (i < n && islower(formula[i])) i++; string name = formula.substr(i_start, i - i_start); int i_start2 = i, multiplicity = 1; while (i < n && isdigit(formula[i])) i++; if (i > i_start2) multiplicity = stoi(formula.substr(i_start2, i - i_start2)); m[name] += multiplicity; } } string result; for (const auto &p : m) { result += p.first; if (p.second > 1) result += to_string(p.second); } return result; } };

[@Gomeroff]

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

[@tusharbhatia5437]

Love the dedication to post daily videos !

[@sum_it_]

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

[@justthefacts1205]

No, it makes sense, I seewhat tou mean it's a great idea!

[@bundiderp5109]

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

[@ew2430]

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

[@kalmyk]

now try recursive solution lol

[@leetcode571]

Being an indian, I read behemoth as "behenchod" 😂😂

[@deltag0ny224]

@@kalmyk I swear the recursive solution is intuitive. Maybe it's because our university started out with recursion in the first semester.😀

[@hemanth052]

how long did u take to solve it by urself ?

[@deadlyecho]

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..

[@jokerjoky3372]

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

[@anishpandey9653]

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

[@daphenomenalz4100]

Knowing Go or Python is a blessing.

[@ashwinashok1361]

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

[@happybaniya]

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

[@JazzBrown-ym8ku]

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.

[@sojwalgosavi4406]

65 lines

[@JazzBrown-ym8ku]

@@sojwalgosavi4406 Impressive my guy, could you maybe link your code if convenient.

[@bhagavan.unique4423]

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

[@shahzodshafizod]

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

[@akarshanjaiswal6330]

The code will fail for "Mg(Uub)2" , we need to do slight change in solution at line 21 and 22 and change it to below while i+1 < len(formula) and formula[i+1].islower(): element += formula[i+1] i+=1

[@gabrielfonseca1642]

Uub is from the old periodic table, all elements have at most two characters now

[@abhishekkumar-fe8lw]

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

[@AniruddhaErande]

Great explanation and the code is very easy to comprehend

[@abhijeetkumar5964]

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.

[@janardannn]

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

[@niteshparihar8435]

hii there , how many question have u solved on leetcode? i started two month ago i solved 70 question , what is roadmap please help me.

[@devnull711]

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

[@prainlopez2734]

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().

[@lazysky1234]

You save my weekend. Thanks my hero.

[@shubhamchouksey9904]

Thankyou for mentioning the Java developers.

[@LemesaElias]

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).

[@gabrielfonseca1642]

if you look at the code, his stack is just a python list, and you can store anything in those. The important thing is to pop and add elements in the correct order.

[@Simran_048]

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

[@vishruthpuli1664]

make 1hr videos and explain all the possible solutions

[@arijaa.9315]

No need

[@woodylucas]

This was a really fun one

[@unanimous8510]

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!

[@beinghappy9223]

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

[@Vancha112]

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

[@suyashgaurav448]

Thanks

[@datastructure_algorithem01]

at least I come up with good question understanding😅

[@manasvidobariya100]

Thank you for the explanation

[@nealp9084]

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(); } } ```

[@isltactics2093]

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

[@greatfate]

traversing backwards makes this slightly simpler

[@andrewkreisher689]

very cool problem,

[@maanas_sehgal]

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

[@freecourseplatformenglish2829]

Python is basically sudo code if you can understand the sudocode then you can code it in any language. Edit - Sorry I did not saw the video and commented. I guess Navdeep need to avoid build-in python functions.

[@maanas_sehgal]

@@freecourseplatformenglish2829 hmm I know how to do in java, planning to switch to python after some time

[@thenameisafsal]

1 hour? no problem let's do it!

[@Komedy1Reels]

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

[@yashmundada2483]

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

[@NeetCodeIO]

I guess the desc is wrong because I can't recall any real chemistry elements with more than two characters

[@tunno4586]

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

[@sayanbiswas2116]

this question was something a hell lot

[@AchintBhat]

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

[@rajrishav]

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

[@YashGupta-ty2hn]

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

[@freecourseplatformenglish2829]

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

[@limsiryuean5040]

Brave person I am, get good I will

[@mohanedomer9081]

i was doing it in js it was 79 lines

[@fieworjohn5697]

At 19:47 N should be 2, not 1

[@fantasticvibes6113]

no 1 hours thanks

[@eshukla15]

i love you man

[@zetianjin5414]

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

[@williamdufault6413]

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()) ] )

[@TenzDelek]

bro is trolling java at this point

[@Rohan-io1yb]

Cpp person here lol

[@StellasAdi18]

Would hope such question never comes in interview.

[@saranshthukral4021]

Upvote for Science👍👍

[@Logeshwar-s7m]

implement 1 hour video

[@betabias]

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

[@Thorium-j3q]

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

[@abhishekkrishna5978]

Longer Video ++

[@codenocode]

I solved this in 50 lines of python code :(

[@raviteja3920]

this looks like a promotional video of python 😂😂😂

[@samarthtandale9121]

I solved it using a queue in a bfs fashion.

[@prashanthkumar0]

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

[@mikehan47]

Hahaha let’s translate that

[@parameshkumar6580]

Stack of HashMaps. Seriously?

[@unstoppablecoder8110]

First view and comment 😂

[@EduarteBDO]

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() } }

[@Benstokes555]

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

[@eshukla15]

shutyo ass

[@yang5843]

Java coders watching this

[@qulinxao]

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

[@mayankpant5376]

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 ??

[@GeetainSaar]

Give me 1% of your property

[@vayunjain9289]

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