please help , is it okay to use inbuilt functions, for example i used the math.product() like this import math from functools import reduce def product(nums: list[int]): prod=list() for idx,num in enumerate(nums): mux = nums.copy() mux[idx] =1 prod.append(math.prod(mux)) #print(mux) #prod = [num*x for x in prod] return prod
@@thamaraiselvan8940 Technically it is but according to Leetcode, it is not for this problem. Refer to this line from the problem description on Leetcode: "Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)"
This problem is insane. After going through the explanation and the code initially I still didn't get it. I can't imagine coming up with this on the spot in an interview.
thank god im not the only one, i feel bad when i cannot come up with a solution, but seen other humans struggle make me feel better, im not a genius and i have to accept it
For ones, who did not understand how prefix-postfix works, lets change 1, 2, 3, 4 positions to symbols like a, b, c, d, so multiplying will be: prefix: -> | a | a*b | a*b*c | a*b*c*d | postfix:
thank you. I only understood the operation and not the principle, but through your abstract explanation, I just understood enough to punch myself in the thigh 5 times!
@@andylinkOFFICIAL Looks like you're correct. After a quick read on the history of Kadane's algorithm (used to solve the maximum subarray problem), I'm inclined to think that a lot of the people that came up with these solutions were very intelligent professors in math or computer science and had a lot of time to come up with them (for the most part), and they were also improving on each other's design. From wikipedia: "The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images.[5] Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers. A brute-force algorithm for the two-dimensional problem runs in O(n6) time; because this was prohibitively slow, Grenander proposed the one-dimensional problem to gain insight into its structure. Grenander derived an algorithm that solves the one-dimensional problem in O(n2) time,[note 1] improving the brute force running time of O(n3). When Michael Shamos heard about the problem, he overnight devised an O(n log n) divide-and-conquer algorithm for it. Soon after, Shamos described the one-dimensional problem and its history at a Carnegie Mellon University seminar attended by Jay Kadane, who designed within a minute an O(n)-time algorithm,[5][6][7] which is as fast as possible.[note 2] In 1982, David Gries obtained the same O(n)-time algorithm by applying Dijkstra's "standard strategy";[8] in 1989, Richard Bird derived it by purely algebraic manipulation of the brute-force algorithm using the Bird-Meertens formalism.[9]"
Quality is just unparalleled, the way you break down things is god-sent neet. First paycheck I get at a top company, I'll be sending things your way. Truly thank you neet!
there's literally no way anyone would ever come up with this algorithm on their own without seeing this exact problem before lol. these are the kinds of leetcode problems that are completely pointless to ask a candidate; you either see them solve some solution they memorized, or they give you n^2, neither really tell you anything about their ability
For this problem, I was able to come up with the general idea for the solution in about 20 minutes, and then another 20 minutes or so to code it w/o seeing the problem before. I was running into problems with submitting without getting time limit exceeded because I did the suffixes first and was pushing to the front of a vector (which is an O(n) operation), but I'm guessing that wouldn't be a huge deal during an actual interview. I do agree however that the intuition for most medium to hard LeetCode problems (and even some easy's tbh) is really hard to come by without doing A LOT of them and getting a feel for the different patterns and strategies you can apply. What I've found in general for the difficulty tags is that they usually describe how far of a logic gap there is between the problem you're given and the solution, rather than how hard it is to code. Some problems labeled hard are actually relatively easy to code if you know the solution ahead of time, but coming up with it is a different story because of how many leaps in logic you have to go through to arrive there. I will say however that during interviews what they're usually looking for is how you approach a new problem and how you go through and communicate your thought process. A lot of the times they can tell if you've seen a problem before if you jump immediately to the solution without clear logic, and for some interviewers they actually see it as a waste of time if you obviously have seen the problem before since it's supposed to be new. Sometimes, they can even have a number of questions to ask you if you've seen it before. My biggest issue with these questions is that they're more about solving math problems (i.e. Computer Science) than actual software engineering. The main reason that they are asked is because it's a standardized way to test algorithmic thinking for people coming from a variety of backgrounds without requiring candidates to have advanced industry knowledge.
that's what I'm saying. I'm going through these leetcode walkthroughs to learn fundamentals and techniques on how to solve leetcode problems on my own . But this one left me feeling like I learned nothing from it besides memorizing the solution.
@@zappy9880 No, you just exeeded the allowed compute time because doing what you did the complexity is mutiplied by n (the number of elements in the array). So basically you end up with complecity in the order of O(n**2).
I tried to understand the problem the way you taught and finally solve it on my own. I was able to produce the exact same code as you did, because the explanation was so detailed. I think moving forward, I need to spend a lot more time studying the logic before coding anything. I have an interview coming up and this insight will definately help me.
You have to be super genius to have the intuition to come up with these kind of solutions first time in an interview. Unless there is a reliable systematic way to determine the problem space of the optimal solution you got to memorise the pattern. wtf.
@@sanjeevsinha-in You will only be able to come up with the optimal solution by having already done the question.. That's why you are doing leetcode right? HAHA.
@@sanjeevsinha-in You won't be able to. What I've seen is that interviewers give you hints, so that sort of helps in arriving at atleast a working solution. As for the optimal solution, again, if they give hints, it shouldn't be extremely difficult, atleast from my experience. However, I do agree that this problem is ridiculously frustrating.
After solving 30 blind 75 problems I was able to draw and come up with a solution that is logically the same as preFix + postFix but with different names, and not as clean as yours. The key is to draw in paint or figma, and representing problems graphically, a thing I've learned watching your vids. Ty so much!
Not using the extra memory really impacts the code's readability. Unless there is serious performance requirement, write readable code not clever code.
Pretty much all of Leetcode's problems' solutions are an antithesis to how you SHOULD be writing software in an enterprise app, where readability and test-ability is far more important than saving a minute amount of memory or CPU cycles.
@@fahadfreid1996 That's true. Interesting question though... How important is clean code (variable naming, small functions and unit testing, etc) for such type of tech interviews?
One important thing that lacks in this explanation, is the familiarity with the concept of "Prefix/Postfix Sum". I watched this solution without knowing that hence I was stuck but after knowing it I understood this.
This comment helped me. I didn't know this was a recognized computer term, I thought it was a math term. There doesn't seem to be a lot of videos on youtube about it but knowing that it's a CS term, I was able to look it up (the terms are prefix sum array and postfix sum array) and now I understand the principle of the solution.
@@sola2943 It's not a math term, you can talk about prefix strings and postfix strings too. If you think of prefix as 2 words, 'pre' and 'fix', you'll see that 'pre' means before and 'fix' applies to the fixed point in the sequence you're mentioning. Thus, prefix means "the stuff before your fixed point". For postfix, you can think of it as 'post' and 'fix' and thus postfix means "the stuff after your fixed point". For a real math term, look up prefix/postfix notation.
Shouldn't feel dumb, people spent days coming up with this the first time. To expect anyone to magically intuit the solution in a fixed 30 min interview is simply impossible.
I had my Amazon interview yesterday and was asked this question, I did the brute force solution and cleared the interview, but this solution is genius!
@@_Ahmed_15 just coming up with a solution is good enough on the spot. Your thought process and how you go about analyzing the problem matters more. You won't be solving these kind of problems in a company. they just wanna check if you can understand the problem well and come up with a solution.
I admire your ability to explain the solutions so well! Finding the solution at all is half the battle, the other half is being able to explain it well to the interviewers, especially when English is not your first language.
@@dera_ng not really, just use two boolean variables to check if array contains one zero or multiple zeroes, and then use an if else condition to answer accordingly
I had difficulty understanding the explanation. But it turns out that I didn't know how the postfix and prefix traversals worked. Understanding them helped me understand your explanation better.
Thank you for this comment, I have been scanning comments to get a better understanding of the logic. I get how the code works after seeing the video but I still don't understand the logic and you have given me a much needed clue. If you see this, was there a resource that helped you understand traversals better?
why does the result array not count for the space complexity? In my opinion the solution is still in O(n) because of the result array. O(1) is only possible if we use the input array and manipulate it, but thats not possible here. Or do I miss something?
I didn't understand why the final method of O(1) space complexity? I thought the space complexity will also be O(n)? as we're storing "n" number of values where "n" is the size of the first array?
Just started to solve leetcode problems. I told myself that I won't look at the solution until I solve it because I developed a bad habit to look at the solution too early. Took a pen and a paper. After an hour I was ready to give up. But then somehow I came up with the solution. It seemed impossible at the beginning and so simple at the end.
I followed through with the explanation, then the day after recollected the steps and coded out the answer... However, this makes me feel uneasy as I don't know if I ACTUALLY learned anything or just memorized your solution. I spent an hour thinking through the problem and couldn't find another way to solve it that didn't take the division approach. Since I couldn't get to your solution on my own, I question if this means I lack the mental capacity to solve a problem I've never seen before during an interview. When you started, did you just do Leetcode problems until you remembered the patterns and were then able to use information that you've picked up along the way as tools to solve new problems or is there another approach I should take such as reading Introduction to Algorithms by Cormen, Rivest, and Stein? I'm currently using the Blind 75 problem set on your personal site. Thanks for the great content!
There is no way someone can come up with this solution in 30 mins. But we do these problems to brush up on programming and get familiar with the type of problems that are asked. So if you see a problem during an interview you can cross out 10 different techniques in your head. At least you will be able to produce a bruteforce solution or second best. Of course you are not required to come up with these clever solutions. The interviewer just wants to know that you can write code, and talk about it. And this is the most standardized way there is yet. But...if you are that Einstein of coding then these questions give you the opportunity to show off and stand out.
I was also thinking in this direction of prefix and postfix. But at starting and ending you assumed to put 1. I was not able to assume this case. By your explanation it got crystal clear. Thank You so much
Why would this be O(1) space? If the resultant array will be the length of the input array nums, wouldn't that be O(N) space since the size of the data structure grows linearly based on input?
This was a particularily hard problem to wrap my head around. I came up with the following solution (similar but different). It was more intuitive for me. Hope this helps someone. You got this!! Intuition/Key Idea: The key observation here is that you can split the problem into two parts: Left Product: The product of all elements to the left of the current element. Right Product: The product of all elements to the right of the current element. By multiplying these two products, you get the desired value for each position in the result array. def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) output_array = [1]*n # calculate the left product left = 1 for i in range(n): output_array[i]=left left = left*nums[i] # calculate the right product right=1 for i in range(n-1, -1,-1): output_array[i]*=right right*=nums[i] return output_array
I never would have gotten that, that's actually wild, I don't get tripped up by the hard questions on leetcode but the medium weird ones like this lol.
Given `nums = [a, b, c, d]` Then answer or the resulting list would be `[b*c*d, a*c*d, a*b*d, a*b*c]` The left_pass, after left to right iteration gives `[1, a, a*b, a*b*c]` The right_pass, after right to left iteration gives `[b*c*d, c*d, d, 1]` Product of left_pass[i] and right_pass[i] would give us the above result. So the cumulative product does make sense in this way.
Hi. Yes it is but according to the Leetcode question, there's a point at the bottom that states that the Output Array is not being counted as extra memory space
So my question is as follows: In the working explanation, we multiply for the values at the prefix and postfix positions (i-1) and (i+1) and store them in i. How come while coding it up, the range of the for loop isn't changing to accomodate those shifted products?
Same algorithm instead of prefix = 1 for product, use prefix of 0 for sum replace * with + then you'll get sum of array except self, especially when subtraction op is isn't allowed. Also, somewhat a base for kadane's algo for maximum sum subarray, if just keep doing the prefix part.
I found the code to be more informative and easier to understand compared to the diagrams. The code provides a clearer and more precise explanation of the problem imo!
O(n) solution if there are two 0's then all cells are 0's if there is one zero just calculate product of all cells except that cells and put rest of the cells as 0 if there are no 0's get product of alls cells and just divide by that number in the respective cell iteratively
This is the first one that I got stuck on. What do you recommend when getting stuck on the problem? Doing the problem over and over again? Or understand the solution and move on to the next without checking it off? Or moving on the next and checking it off?
I think it's a really stupid question because of the limitations they place on the problem. The calculate the product for all nums and use division for each index is such a straightforward and simple solution which you are not allowed to use for some reason. Like I can't imagine that you would be writing software and you come up with something that is efficient, easy to understand and intuitive and then say forget about that we're gonna write a more complicated solution.
That's an excellent explanation. However, I'm still missing the point: why do postfix and prefix work? What is the math behind that? I feel that a vital part is skipped.
The goal is to get the product of all the elements except at the position we are in. Are you confused on how the prefix * the postfix = product of every element except this one?
product = 1 prefix = [] for num_val in nums: product = product * num_val prefix.append(product) product = 1 postfix = [] for i in range(len(nums) - 1, -1, -1): product = product * nums[i] postfix.insert(0, product) res=[] for i in range(len(nums)): left = prefix[i-1] if i - 1 >= 0 else 1 right = postfix[i+1] if i + 1 < len(nums) else 1 res.append(left * right) return res this is the unoptimized code which he was talking about
The restriction on division operation is also put in place to avoid the 'Division by Zero' error as some elements in the array could contain the integer 0. Just wanted to add that here.
those edges cases could be handled separately, that was what I did at least, as there are only 3 cases: 1) when there is more than 1 zeros, 2) when there is exactly 1 zero, 3) when there is no zero in the array.
You can handle that edge case. I think they restrict division because this problem can be generalized to other operations and the operation being used may not have a good inverse?
How is this question a Medium? There's no way someone can figure out the optimal answer in an interview without hints. This should be Hard. Especially because this question is a Ninja question in Elements of Programming interviews
I don't get why this still counts as O(1) when you really created res[]. I was expecting in-place swapping to satisfy O(1) memory space. Can someone explain it to me?
I think this solution may be easier to read if you stored the postfix in the results and computed the prefix as you walk the result, instead of reverse incrementing the results to accumulate the postfix with the length - 1 check.
One loop: O(n) Another loop: O(n) Total -> O(2n). We remove the constant 2, so we have O(n). If the loops were nested, then yes, this would be O(n^2). In this case, we only ever traverse a given array twice. An array of a thousand elements is only two traversals. If loops were nested, then we would make one extra traversal for every element in the array. An array of a thousand elements is a thousand extra traversals.
@@SnipeSniperNEW Top few results on TH-cam are enough unless you want to get deep into details. In that case, there are whole books on the topic. Most job interviews will just ask you to quickly assess time and space complexity in simplified form.
dumb question... So, doing two loops still counts as O(n) because O(2n) -> O(n) ?? I really spent a lot of time trying to think a way to use a single loop before watching the video and I ended up with a solution but still using both arrays :)))))
you can do it with a single loop but you end up needing conditional logic which is slower tbh. either that or you use arrays with 1 extra element in size and then shorten them somehow, which, again, would give you no benefit above using 2 loops.
This is what I love about python, you can solve leetcode problems in 10 lines of code class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: N = len(nums) res= [1]*N prod_pre, prod_post = 1,1 for i in range(N): res[i] *= prod_pre res[N-1-i] *= prod_post prod_pre *= nums[i] prod_post *= nums[N-1-i] return res
You can reverse engineer it from the given information. The product of everything but not itself. -> So the product of all elements but not this element -> Why do we access those elements? -> Two kinds of elements that make up the product -> one before this nth element, ones after this element -> keep track of them and multiply
You could say this is O(2n) since you are looping over n twice. But in big O notation, O(Xn) reduces to O(n). As long as X is countable i.e. not n or log n). In general, you don't increase the magnitude of the time complexity unless you nest a loop somewhere.
Oh man, Amazon asked me this question in an interview and even though I was miraculously able to reach the solution in 20 minutes (although using the two extra arrays), I still wasn't hired because I 'had to think too much' and wasn't able to explain my train of thought very clearly... rough
Thanks, man, you are great. I love listening to your solutions and trying to implement them myself before going through your walkthrough. The value is unparallel.
When calculating the prefix and postfix array values, you can omit the value in the array itself, so that in the final iteration of the loop you can avoid the slightly confusing way of doing prefix[i-1] * postfix[i+1] and instead just do prefix[i] * postfix[i]; Also initialize both the first and last values of the preflix and postfix arrays with 1 respectively and then do something like this: for (let i=1; i=0; i--) { postfixArray[i] = postfixArray[i + 1] * nums[i+1]; } for (let i=0; i
![[UNCUT] “บอสณวัฒน์” ลากไส้!! ใครหนุนหลัง "แม่ตั๊ก ป๋าเบียร์" I คนดังนั่งเคลียร์ I 30 ก.ย. 67](http://i.ytimg.com/vi/QlD7mU2KKRk/mqdefault.jpg)
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
please help , is it okay to use inbuilt functions, for example i used the math.product() like this
import math
from functools import reduce
def product(nums: list[int]):
prod=list()
for idx,num in enumerate(nums):
mux = nums.copy()
mux[idx] =1
prod.append(math.prod(mux))
#print(mux)
#prod = [num*x for x in prod]
return prod
isn't the memory complexity O(n).since u create a whole new list
@@thamaraiselvan8940 Technically it is but according to Leetcode, it is not for this problem. Refer to this line from the problem description on Leetcode:
"Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)"
@@vusumuzindhlovu yo never do that, the interviewers do not like that kinda thing man
I found a way to solve it using recursion going only once over the array . I make changes on the nums array itself not storing the res array.
This problem is insane. After going through the explanation and the code initially I still didn't get it. I can't imagine coming up with this on the spot in an interview.
thank god im not the only one, i feel bad when i cannot come up with a solution, but seen other humans struggle make me feel better, im not a genius and i have to accept it
yeah, this is what we call a "crackhead" problem. 'Cuz no way you can come up with THAT solution unless you're a crackhead.
@@luiggymacias5735*I did!* but this one is better! Keep coding
nah i did come up with something similar , so its definitely intuitive enough but i took a lot of time but thats me
@@sinnohperson8813 I'm sure you've seen this pattern before or something similar. There's just no way
For ones, who did not understand how prefix-postfix works, lets change 1, 2, 3, 4 positions to symbols like a, b, c, d, so multiplying will be:
prefix:
->
| a | a*b | a*b*c | a*b*c*d |
postfix:
wow this made it click for me. thanks bro
Thanks for this. I never thought about writing it out as tiny equations but that makes it a lot clearer.
prefix:
| 1 | a | a * b | a * b * c |
postfix:
|b * c * d | c * d | d | 1 |
thank you. I only understood the operation and not the principle, but through your abstract explanation, I just understood enough to punch myself in the thigh 5 times!
@@viraje7940 I guess even for postfix we start with 1 at the end.
Bro how do people manage to figure out these solutions?
You're some geniuses
No one just simply stumbles across this solution. It must have taken days for someone to figure this out.
@@andylinkOFFICIAL we need that in 30mins during your
interview
@@andylinkOFFICIAL Looks like you're correct. After a quick read on the history of Kadane's algorithm (used to solve the maximum subarray problem), I'm inclined to think that a lot of the people that came up with these solutions were very intelligent professors in math or computer science and had a lot of time to come up with them (for the most part), and they were also improving on each other's design.
From wikipedia:
"The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images.[5]
Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers. A brute-force algorithm for the two-dimensional problem runs in O(n6) time; because this was prohibitively slow, Grenander proposed the one-dimensional problem to gain insight into its structure. Grenander derived an algorithm that solves the one-dimensional problem in O(n2) time,[note 1] improving the brute force running time of O(n3). When Michael Shamos heard about the problem, he overnight devised an O(n log n) divide-and-conquer algorithm for it. Soon after, Shamos described the one-dimensional problem and its history at a Carnegie Mellon University seminar attended by Jay Kadane, who designed within a minute an O(n)-time algorithm,[5][6][7] which is as fast as possible.[note 2] In 1982, David Gries obtained the same O(n)-time algorithm by applying Dijkstra's "standard strategy";[8] in 1989, Richard Bird derived it by purely algebraic manipulation of the brute-force algorithm using the Bird-Meertens formalism.[9]"
@@mangalegends A lot of people that came up with these algorithms took entire Phds to come up with them
4 months later I just came back to this problem and managed to actually solve it on my own without looking at the solution. Woo
Quality is just unparalleled, the way you break down things is god-sent neet. First paycheck I get at a top company, I'll be sending things your way. Truly thank you neet!
Fun fact - Neet's last name is Code
I literally had the same thought yesterday.
did you get your first paycheck
@@onlyforwork8774 not quite 😂😂😂
@@montgomeryscottbrea2614 🤣🤣
there's literally no way anyone would ever come up with this algorithm on their own without seeing this exact problem before lol. these are the kinds of leetcode problems that are completely pointless to ask a candidate; you either see them solve some solution they memorized, or they give you n^2, neither really tell you anything about their ability
For this problem, I was able to come up with the general idea for the solution in about 20 minutes, and then another 20 minutes or so to code it w/o seeing the problem before. I was running into problems with submitting without getting time limit exceeded because I did the suffixes first and was pushing to the front of a vector (which is an O(n) operation), but I'm guessing that wouldn't be a huge deal during an actual interview. I do agree however that the intuition for most medium to hard LeetCode problems (and even some easy's tbh) is really hard to come by without doing A LOT of them and getting a feel for the different patterns and strategies you can apply. What I've found in general for the difficulty tags is that they usually describe how far of a logic gap there is between the problem you're given and the solution, rather than how hard it is to code. Some problems labeled hard are actually relatively easy to code if you know the solution ahead of time, but coming up with it is a different story because of how many leaps in logic you have to go through to arrive there.
I will say however that during interviews what they're usually looking for is how you approach a new problem and how you go through and communicate your thought process. A lot of the times they can tell if you've seen a problem before if you jump immediately to the solution without clear logic, and for some interviewers they actually see it as a waste of time if you obviously have seen the problem before since it's supposed to be new. Sometimes, they can even have a number of questions to ask you if you've seen it before.
My biggest issue with these questions is that they're more about solving math problems (i.e. Computer Science) than actual software engineering. The main reason that they are asked is because it's a standardized way to test algorithmic thinking for people coming from a variety of backgrounds without requiring candidates to have advanced industry knowledge.
Yeah totally agree. I hate this culture every company is trying to take this approach nowadays .
I solved this a different way in linear time but you your right no one is coming up with this solution on their own in 30minutes
that's what I'm saying. I'm going through these leetcode walkthroughs to learn fundamentals and techniques on how to solve leetcode problems on my own . But this one left me feeling like I learned nothing from it besides memorizing the solution.
@@lcppproductions7910 your time would be an issue because 40 mins for 1 problem is already 90% of the interview time for just 1 problem...
Absolute legend, this problem almost shouldn't be medium, the logic of doing this without division is mind bending without your explanation
I think this is what a medium should be
Hard problems in leetcode have hidden mindbreak tags on them
Interviewer: BTW you can't use the division operator.
Me : Uses pow(num,-1).
Interviewer:😲
I tried with repeated subtraction but somehow it still figures it out. I guess LeetCode has a custom compiler or something.
lmao
Haha... :P
@@zappy9880 No, you just exeeded the allowed compute time because doing what you did the complexity is mutiplied by n (the number of elements in the array). So basically you end up with complecity in the order of O(n**2).
I tried to understand the problem the way you taught and finally solve it on my own. I was able to produce the exact same code as you did, because the explanation was so detailed. I think moving forward, I need to spend a lot more time studying the logic before coding anything. I have an interview coming up and this insight will definately help me.
Update: thanks to this guy. I got the job.
@@jaspindersingh3097 Congratulations Man, In which company?
Yeah this, I used to start code right away and often get least optimal or inaccurate solution
@@jaspindersingh3097 congratulations.......
congrats
You have to be super genius to have the intuition to come up with these kind of solutions first time in an interview. Unless there is a reliable systematic way to determine the problem space of the optimal solution you got to memorise the pattern. wtf.
Seriously, how one can come up with this approach in interview when facing this problem for the first time? this does not help.
@@sanjeevsinha-in You will only be able to come up with the optimal solution by having already done the question.. That's why you are doing leetcode right? HAHA.
@@sanjeevsinha-in You won't be able to. What I've seen is that interviewers give you hints, so that sort of helps in arriving at atleast a working solution. As for the optimal solution, again, if they give hints, it shouldn't be extremely difficult, atleast from my experience. However, I do agree that this problem is ridiculously frustrating.
After solving 30 blind 75 problems I was able to draw and come up with a solution that is logically the same as preFix + postFix but with different names, and not as clean as yours. The key is to draw in paint or figma, and representing problems graphically, a thing I've learned watching your vids. Ty so much!
Don't think I want a job anymore 🤣
Did you get a software engineering job?
did you get the job?
No bro just gave up after looking at the solution@@luiggymacias5735
Did you get the job ?
Have you gotten the job?
How can I like a video multiple times? This is extremely well-explained, man! Thank you for creating this video. You are an inspiration!
Just press
Not using the extra memory really impacts the code's readability. Unless there is serious performance requirement, write readable code not clever code.
Pretty much all of Leetcode's problems' solutions are an antithesis to how you SHOULD be writing software in an enterprise app, where readability and test-ability is far more important than saving a minute amount of memory or CPU cycles.
Yes, but readability is not a concern during the interviews
@@fahadfreid1996 That's true. Interesting question though... How important is clean code (variable naming, small functions and unit testing, etc) for such type of tech interviews?
@@炒粿条-b1d not true.
One important thing that lacks in this explanation, is the familiarity with the concept of "Prefix/Postfix Sum". I watched this solution without knowing that hence I was stuck but after knowing it I understood this.
This comment helped me. I didn't know this was a recognized computer term, I thought it was a math term. There doesn't seem to be a lot of videos on youtube about it but knowing that it's a CS term, I was able to look it up (the terms are prefix sum array and postfix sum array) and now I understand the principle of the solution.
@@sola2943 It's not a math term, you can talk about prefix strings and postfix strings too. If you think of prefix as 2 words, 'pre' and 'fix', you'll see that 'pre' means before and 'fix' applies to the fixed point in the sequence you're mentioning. Thus, prefix means "the stuff before your fixed point". For postfix, you can think of it as 'post' and 'fix' and thus postfix means "the stuff after your fixed point".
For a real math term, look up prefix/postfix notation.
idk y i struggled so much with this one. i spent like 4 hours trying to think of the the linear solution. i really felt dumb and not cut out for this.
Shouldn't feel dumb, people spent days coming up with this the first time. To expect anyone to magically intuit the solution in a fixed 30 min interview is simply impossible.
I had my Amazon interview yesterday and was asked this question, I did the brute force solution and cleared the interview, but this solution is genius!
By brute force do you mean an O(n^2) solution with nested loops?
Amazon lets you move on using brute force? Did you get an offer?
.
@@_Ahmed_15 just coming up with a solution is good enough on the spot. Your thought process and how you go about analyzing the problem matters more. You won't be solving these kind of problems in a company. they just wanna check if you can understand the problem well and come up with a solution.
@@Call-me-Avi still, the brute force for this is way too easy no? Like way too easy !!!
I admire your ability to explain the solutions so well! Finding the solution at all is half the battle, the other half is being able to explain it well to the interviewers, especially when English is not your first language.
and what is his first language?
The reason you can’t do it with a divide is the second test case in the problem and a minor issue called a DIV0 error
I think we can still write a version with division, its just there will be several if statement to deal with 0s in the array :)
@@jerryteps I tried doing this, it's messy.
@@dera_ng Can confirm, most of your time will be spent tackling those edge cases.
Actually this constraint stops us from trying a buggy solution.
@@dera_ng not really, just use two boolean variables to check if array contains one zero or multiple zeroes,
and then use an if else condition to answer accordingly
This problem was extremely difficult for me to understand, thank you for explaining so clearly!
Hey there. I just want to say thank you for making these videos!
Thanks!
I had difficulty understanding the explanation. But it turns out that I didn't know how the postfix and prefix traversals worked. Understanding them helped me understand your explanation better.
Thank you for this comment, I have been scanning comments to get a better understanding of the logic. I get how the code works after seeing the video but I still don't understand the logic and you have given me a much needed clue. If you see this, was there a resource that helped you understand traversals better?
why does the result array not count for the space complexity? In my opinion the solution is still in O(n) because of the result array. O(1) is only possible if we use the input array and manipulate it, but thats not possible here. Or do I miss something?
I think he just said the problem states it would not count
I didn't understand why the final method of O(1) space complexity? I thought the space complexity will also be O(n)? as we're storing "n" number of values where "n" is the size of the first array?
Because the output array doesn't count towards the limit (per the instructions). its basically cheating
same here, I thought space complexity should be O(n)
Just started to solve leetcode problems. I told myself that I won't look at the solution until I solve it because I developed a bad habit to look at the solution too early.
Took a pen and a paper. After an hour I was ready to give up. But then somehow I came up with the solution. It seemed impossible at the beginning and so simple at the end.
I followed through with the explanation, then the day after recollected the steps and coded out the answer... However, this makes me feel uneasy as I don't know if I ACTUALLY learned anything or just memorized your solution. I spent an hour thinking through the problem and couldn't find another way to solve it that didn't take the division approach.
Since I couldn't get to your solution on my own, I question if this means I lack the mental capacity to solve a problem I've never seen before during an interview.
When you started, did you just do Leetcode problems until you remembered the patterns and were then able to use information that you've picked up along the way as tools to solve new problems or is there another approach I should take such as reading Introduction to Algorithms by Cormen, Rivest, and Stein?
I'm currently using the Blind 75 problem set on your personal site. Thanks for the great content!
There is no way someone can come up with this solution in 30 mins. But we do these problems to brush up on programming and get familiar with the type of problems that are asked. So if you see a problem during an interview you can cross out 10 different techniques in your head.
At least you will be able to produce a bruteforce solution or second best.
Of course you are not required to come up with these clever solutions. The interviewer just wants to know that you can write code, and talk about it. And this is the most standardized way there is yet. But...if you are that Einstein of coding then these questions give you the opportunity to show off and stand out.
I was also thinking in this direction of prefix and postfix. But at starting and ending you assumed to put 1. I was not able to assume this case. By your explanation it got crystal clear. Thank You so much
These kind of problems make me feel stupid. Thanks for the breakdown, this made sense!
I have never been able to get this right until I saw this explanation. You seriously rock !!
I came form the website straight to the vid to like it
Why would this be O(1) space? If the resultant array will be the length of the input array nums, wouldn't that be O(N) space since the size of the data structure grows linearly based on input?
Thats what im thinking. Shocked at how below this comment is
@@dhruv1906 That's because the problem says "The output array does not count as extra space for space complexity analysis."
This was a particularily hard problem to wrap my head around. I came up with the following solution (similar but different). It was more intuitive for me. Hope this helps someone. You got this!!
Intuition/Key Idea:
The key observation here is that you can split the problem into two parts:
Left Product: The product of all elements to the left of the current element.
Right Product: The product of all elements to the right of the current element.
By multiplying these two products, you get the desired value for each position in the result array.
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
output_array = [1]*n
# calculate the left product
left = 1
for i in range(n):
output_array[i]=left
left = left*nums[i]
# calculate the right product
right=1
for i in range(n-1, -1,-1):
output_array[i]*=right
right*=nums[i]
return output_array
Thankyou, can you tell me how is this time complexity O(n), we are making two passes over the array so shouldnt it be O(n^2)?
@@jasnoorsandhu1235 The first pass is O(n), the second is also O(n). O(n+n)=O(2n) is still O(n).
@@AmicusAtheniensis thanks for answering the question.
I never would have gotten that, that's actually wild, I don't get tripped up by the hard questions on leetcode but the medium weird ones like this lol.
The way you drew out the explanation was super clear thank you!
I don't get it. Why the space is still O(1)? If we increase the numbers, we needs more memory to store our answers. So it should be O(n). Why wrong
Space complexity is O(1) because the problem specified the result array does not count towards the space complexity. Kinda stupid
Given `nums = [a, b, c, d]`
Then answer or the resulting list would be `[b*c*d, a*c*d, a*b*d, a*b*c]`
The left_pass, after left to right iteration gives `[1, a, a*b, a*b*c]`
The right_pass, after right to left iteration gives `[b*c*d, c*d, d, 1]`
Product of left_pass[i] and right_pass[i] would give us the above result. So the cumulative product does make sense in this way.
The way you explain the problems is so much easier to understand than some of the official LeetCode videos. Thanks so much for being articulate 🙏
I now feel DSA is just about brain muscle memory and you can have your best brain muscle memory by seeing and solving more such problems.
honestly didn't even know what the problem was asking me to do. thank you
the best leetcode solution explainer with python on YT. Yet haven't seen one with such quality
that was a lot to take in! Really!
Absolutely loved it! Cant believe that you made it easy as a cake walk.
Thank you!
Isn't this big O of n space complexity not 1? Since if we have n elements, we'd need an array of nth element to store the result?
Hi. Yes it is but according to the Leetcode question, there's a point at the bottom that states that the Output Array is not being counted as extra memory space
@@sharleen2091 So if the bottom doesn't say that, would it still be O(n)?
First problem I totally failed to solve myself =( Thank you for your explanation, video made me unstuck finally
Is this really the easiest solution to this problem? I don't know the answer but there must be a different, simpler way!
concept of prefix product and postfix product is amazinggg!!
Super helpful, Thank You!
Im so glad you exist. Thank you kind sir.
problems after your explanation become so transparent and understandable. Thank u so much
So my question is as follows: In the working explanation, we multiply for the values at the prefix and postfix positions (i-1) and (i+1) and store them in i. How come while coding it up, the range of the for loop isn't changing to accomodate those shifted products?
the moment I saw the prefix, postfix on the screen, I got the approach
absolutely brilliant, thanks a ton
Dang, using just one array for this is a neat trick I didn’t see right away 👀
Same algorithm instead of prefix = 1 for product, use prefix of 0 for sum
replace * with +
then you'll get sum of array except self, especially when subtraction op is isn't allowed.
Also, somewhat a base for kadane's algo for maximum sum subarray, if just keep doing the prefix part.
Just asking can you use a sliding window for this
I found the code to be more informative and easier to understand compared to the diagrams. The code provides a clearer and more precise explanation of the problem imo!
O(n) solution
if there are two 0's then all cells are 0's
if there is one zero just calculate product of all cells except that cells and put rest of the cells as 0
if there are no 0's get product of alls cells and just divide by that number in the respective cell iteratively
The local fast food hiring looking real tempting rn cause wtf is this
This is the first one that I got stuck on. What do you recommend when getting stuck on the problem? Doing the problem over and over again? Or understand the solution and move on to the next without checking it off? Or moving on the next and checking it off?
Great Explanation
Ill never get into an entry level pos. I could not even figure out prefix postfix solution let alone with only using 1 array.
I think it's a really stupid question because of the limitations they place on the problem. The calculate the product for all nums and use division for each index is such a straightforward and simple solution which you are not allowed to use for some reason. Like I can't imagine that you would be writing software and you come up with something that is efficient, easy to understand and intuitive and then say forget about that we're gonna write a more complicated solution.
Thank you so much for making these videos! You explain the problem and present the solution very clearly.
That's an excellent explanation. However, I'm still missing the point: why do postfix and prefix work? What is the math behind that? I feel that a vital part is skipped.
The goal is to get the product of all the elements except at the position we are in. Are you confused on how the prefix * the postfix = product of every element except this one?
love your clear explanations, keep doing what you're doing man - you're amazing!!
product = 1
prefix = []
for num_val in nums:
product = product * num_val
prefix.append(product)
product = 1
postfix = []
for i in range(len(nums) - 1, -1, -1):
product = product * nums[i]
postfix.insert(0, product)
res=[]
for i in range(len(nums)):
left = prefix[i-1] if i - 1 >= 0 else 1
right = postfix[i+1] if i + 1 < len(nums) else 1
res.append(left * right)
return res
this is the unoptimized code which he was talking about
can some explain why the space was not O(n) even though the result array was made
That optimal solution grows crazy - wow
The restriction on division operation is also put in place to avoid the 'Division by Zero' error as some elements in the array could contain the integer 0. Just wanted to add that here.
those edges cases could be handled separately, that was what I did at least, as there are only 3 cases: 1) when there is more than 1 zeros, 2) when there is exactly 1 zero, 3) when there is no zero in the array.
You can handle that edge case. I think they restrict division because this problem can be generalized to other operations and the operation being used may not have a good inverse?
Thank you, this explanation was very clear to me!
I am glad that I understood by going through this explanation, but afraid I wont remember in real interview
How is this question a Medium? There's no way someone can figure out the optimal answer in an interview without hints. This should be Hard. Especially because this question is a Ninja question in Elements of Programming interviews
Thanks for the sheet, we love you 3000!
Neetcode is the best, coded the solution with extra space complexity myself now moving to a better space solution.
It's a cake walk. Love your explanations!!!!
You’re damn good Sir! I am in good hands…
Wow that's a really clever way to reduce the space complexity
I don't get why this still counts as O(1) when you really created res[]. I was expecting in-place swapping to satisfy O(1) memory space. Can someone explain it to me?
I think this solution may be easier to read if you stored the postfix in the results and computed the prefix as you walk the result, instead of reverse incrementing the results to accumulate the postfix with the length - 1 check.
help me understand, isn't the time complexity here a o(n*n) since we going over the array twice once in order and other in reverse ?
One loop: O(n) Another loop: O(n) Total -> O(2n). We remove the constant 2, so we have O(n). If the loops were nested, then yes, this would be O(n^2).
In this case, we only ever traverse a given array twice. An array of a thousand elements is only two traversals.
If loops were nested, then we would make one extra traversal for every element in the array. An array of a thousand elements is a thousand extra traversals.
@@mastone5949 thank you for clarifying, do you have any recommendation where I can learn more about big o analysis ?
@@SnipeSniperNEW Top few results on TH-cam are enough unless you want to get deep into details. In that case, there are whole books on the topic. Most job interviews will just ask you to quickly assess time and space complexity in simplified form.
Thank you soooooooooo muchhhhhh ..
My guy you have helped me a lotttttt
dumb question... So, doing two loops still counts as O(n) because O(2n) -> O(n) ?? I really spent a lot of time trying to think a way to use a single loop before watching the video and I ended up with a solution but still using both arrays :)))))
you can do it with a single loop but you end up needing conditional logic which is slower tbh. either that or you use arrays with 1 extra element in size and then shorten them somehow, which, again, would give you no benefit above using 2 loops.
Thank you so much for this video! You are talented at explaining things!
This process is extremely clear to understand.
Wow!!! This is another level of genius
This is what I love about python, you can solve leetcode problems in 10 lines of code
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
N = len(nums)
res= [1]*N
prod_pre, prod_post = 1,1
for i in range(N):
res[i] *= prod_pre
res[N-1-i] *= prod_post
prod_pre *= nums[i]
prod_post *= nums[N-1-i]
return res
how do you get the logic???
You can reverse engineer it from the given information.
The product of everything but not itself.
-> So the product of all elements but not this element
-> Why do we access those elements?
-> Two kinds of elements that make up the product -> one before this nth element, ones after this element
-> keep track of them and multiply
Thanks a lot for your great content! It allows me to gain insights immediately to the problem via your clear explanations.
How do people even think of this? I couldn't even compete with the division solution because there was a single Zero.
love the way you explain. Easy, crisp and perfect :)
Commenting twice to help with the algorithm :)
How is it O(n) if its passing through the nums array twice and 2 for loops are being used? Can anyone explain?
You could say this is O(2n) since you are looping over n twice. But in big O notation, O(Xn) reduces to O(n). As long as X is countable i.e. not n or log n). In general, you don't increase the magnitude of the time complexity unless you nest a loop somewhere.
@@Soarex Very insightful, thanks
This is a way better explanation than AlgoExpert has
What pattern would this be called, if any
what textbook would you recommend for someone trying to better their understanding of Data Structures and Algorithms?
Tried solving this one and was literally timing out of the solution window. I would have never thought of this had I not looked at solutions.
Why is it O(1) isn't O(n), we are actually doing computation base on the number of length we have tho
This is very good man, i really hope I get good at Dsa one day
Oh man, Amazon asked me this question in an interview and even though I was miraculously able to reach the solution in 20 minutes (although using the two extra arrays), I still wasn't hired because I 'had to think too much' and wasn't able to explain my train of thought very clearly... rough
Thanks, man, you are great. I love listening to your solutions and trying to implement them myself before going through your walkthrough. The value is unparallel.
When calculating the prefix and postfix array values, you can omit the value in the array itself, so that in the final iteration of the loop you can avoid the slightly confusing way of doing prefix[i-1] * postfix[i+1] and instead just do prefix[i] * postfix[i]; Also initialize both the first and last values of the preflix and postfix arrays with 1 respectively and then do something like this:
for (let i=1; i=0; i--) {
postfixArray[i] = postfixArray[i + 1] * nums[i+1];
}
for (let i=0; i
this function for a javascript? ¡
@@SHUUUSTER yeah
Thanks for this solution, it easy to understand
Noticed that too