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!
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.
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; } };
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.
@@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.
@@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
@@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.
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
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..
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).
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
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().
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
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!
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
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
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.
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 ??