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!
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.
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!
@@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]"
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.
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!
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.
@@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).
transitioning to tech is the hardest thing I have ever done. I'd say leetcode is pattern recognition. I want to get better at visualing the code even before coding. This is something Neetcode has been teaching me. Thank you!
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?
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.
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.
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 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?
@@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
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.
C++ optimal solution Runtime: 19 ms, faster than 89.54% of C++ online submissions for Product of Array Except Self. Memory Usage: 23.9 MB, less than 80.30% of C++ online submissions for Product of Array Except Self. class Solution { public: vector productExceptSelf(vector& nums) { auto res = nums; int postfix = 1; for (int i = 1; i < nums.size(); ++i) { res[i] *= res[i - 1]; } for (int i = nums.size() - 1; i > 0; --i) { res[i] = postfix; res[i] *= res[i - 1]; postfix *= nums[i]; } res[0] = postfix; return res; } };
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.
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 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!
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 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
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
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.
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
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
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 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?
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?
the first thing which popped my mind was recursion but it would take n^2 TC. But this soln would've never come to my head.. like how on earth you guys get soo much grey matter to figure this out?
Great explanation! Here is the optimal Java code (Time: O(n), Space: O(1)): class Solution { public int[] productExceptSelf(int[] nums) { int length = nums.length; int[] result = new int[length]; result[0] = 1; for(int i = 1; i < length; i++) { result[i] = result[i - 1] * nums[i - 1]; } int r = 1; for(int i = length - 1; i >= 0; i--) { result[i] = result[i] * r; r *= nums[i]; } return result; } }
@@andrey6064 Good question! Most people agree that the output does not count towards space complexity, hence the output "result" array of size n does not count towards the space complexity :)
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
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 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?
A cheeky solution is to notice that, in the problem constraints, the range of values in each element of the input array is fixed (an integer between -30 to 30, inclusive). So you can create an array of 61 elements to keep track of the number of appearances of the integers between -30 to 30, and then loop over that array (O(1) time because it is an array of fixed size) to compute the product for each element of the returned array.
That’s the reason google hire you. Before watching your videos I thought I am now a python programmer but after watching your videos I realise I am very far and I need to learn a lot.
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.
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.
5:12 - This is where I completely lost you, I've tried understanding this for so long. Maybe software engineering isn't for me, I have no idea how anybody would ever figure this out on the spot.
He's doing the same thing as he showed with the prefix / postfix arrays but instead he's not storing it in separate arrays. Also, pretty much nobody can figure this out on the spot. In a interview, the only way you would have a chance at this beyond the brute force is already being familiar with the approach.
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?
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
I still don't understand why this works so well... Any ideas? Like I see what's happening and I understand it, but I still can't understand why this works so well... It doesn't feel like I could've come up with this on my own.
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?
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, 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.
@@miken1299 You have to count the zeros. If multiple, return all zeros. If exactly 1 zero, return the product of the rest of the array at that index and the rest zeros.
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?
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
Ngl whoever designed the question shouldn't have written " The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer ", this statement made the problem way easier than it is as It is a pretty big hint. You can easily figure that part out just by looking at the constraints(i.e 100000 x 30) will never exceed 32 bit int. At least the follow up question was good.
🚀 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.
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...
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 🤣🤣
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
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
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
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!
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.
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).
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
transitioning to tech is the hardest thing I have ever done. I'd say leetcode is pattern recognition. I want to get better at visualing the code even before coding. This is something Neetcode has been teaching me. Thank you!
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.
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?
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.
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 !!!
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?
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?
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!
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.
C++ optimal solution
Runtime: 19 ms, faster than 89.54% of C++ online submissions for Product of Array Except Self.
Memory Usage: 23.9 MB, less than 80.30% of C++ online submissions for Product of Array Except Self.
class Solution
{
public:
vector productExceptSelf(vector& nums)
{
auto res = nums;
int postfix = 1;
for (int i = 1; i < nums.size(); ++i)
{
res[i] *= res[i - 1];
}
for (int i = nums.size() - 1; i > 0; --i)
{
res[i] = postfix;
res[i] *= res[i - 1];
postfix *= nums[i];
}
res[0] = postfix;
return res;
}
};
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.
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 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!
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.
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 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
Hey there. I just want to say thank you for making these videos!
Thanks!
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
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 🙏
the moment I saw the prefix, postfix on the screen, I got the approach
absolutely brilliant, thanks a ton
The way you drew out the explanation was super clear thank you!
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.
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
honestly didn't even know what the problem was asking me to do. thank you
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
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 best leetcode solution explainer with python on YT. Yet haven't seen one with such quality
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
I came form the website straight to the vid to like it
Had an idea about the prefix and postfix but didn't really know how to implement it. This was helpful.
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 do people even think of this? I couldn't even compete with the division solution because there was a single Zero.
First problem I totally failed to solve myself =( Thank you for your explanation, video made me unstuck finally
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
the first thing which popped my mind was recursion but it would take n^2 TC.
But this soln would've never come to my head.. like how on earth you guys get soo much grey matter to figure this out?
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.
Neetcode is the best, coded the solution with extra space complexity myself now moving to a better space solution.
Great explanation!
Here is the optimal Java code (Time: O(n), Space: O(1)):
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] result = new int[length];
result[0] = 1;
for(int i = 1; i < length; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
int r = 1;
for(int i = length - 1; i >= 0; i--) {
result[i] = result[i] * r;
r *= nums[i];
}
return result;
}
}
How is space O(1) if result is "new int[length]" and used in calculations? Shouldn't it be O(n) too?
@@andrey6064 Good question! Most people agree that the output does not count towards space complexity, hence the output "result" array of size n does not count towards the space complexity :)
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
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.
Wow that's a really clever way to reduce the space complexity
Absolutely loved it! Cant believe that you made it easy as a cake walk.
Thank you!
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)
problems after your explanation become so transparent and understandable. Thank u so much
A cheeky solution is to notice that, in the problem constraints, the range of values in each element of the input array is fixed (an integer between -30 to 30, inclusive). So you can create an array of 61 elements to keep track of the number of appearances of the integers between -30 to 30, and then loop over that array (O(1) time because it is an array of fixed size) to compute the product for each element of the returned array.
could you send the solution ?
what
I understand. I implemented the code.
That’s the reason google hire you. Before watching your videos I thought I am now a python programmer but after watching your videos I realise I am very far and I need to learn a lot.
love your clear explanations, keep doing what you're doing man - you're amazing!!
That optimal solution grows crazy - wow
The local fast food hiring looking real tempting rn cause wtf is this
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.
concept of prefix product and postfix product is amazinggg!!
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.
Im so glad you exist. Thank you kind sir.
5:12 - This is where I completely lost you, I've tried understanding this for so long. Maybe software engineering isn't for me, I have no idea how anybody would ever figure this out on the spot.
He's doing the same thing as he showed with the prefix / postfix arrays but instead he's not storing it in separate arrays.
Also, pretty much nobody can figure this out on the spot. In a interview, the only way you would have a chance at this beyond the brute force is already being familiar with the approach.
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 am glad that I understood by going through this explanation, but afraid I wont remember in real interview
Thank you so much for making these videos! You explain the problem and present the solution very clearly.
This is a way better explanation than AlgoExpert has
Dang, using just one array for this is a neat trick I didn’t see right away 👀
Wow!!! This is another level of genius
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.
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
This process is extremely clear to understand.
I still don't understand why this works so well... Any ideas? Like I see what's happening and I understand it, but I still can't understand why this works so well... It doesn't feel like I could've come up with this on my own.
that was a lot to take in! Really!
How the fuck am I supposed to get this if I saw it for the first time at an interview? Not an expert puzzle solver
Nobody can, the only chance anyone has in an interview is being already familiar with the approach.
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?
It's a cake walk. Love your explanations!!!!
Thank you so much for this video! You are talented at explaining things!
Thanks for the sheet, we love you 3000!
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, 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.
Third time I am trying to figure out this problem, this explanation was the best. I hope I will remember it...
Can't use division? No problem!
Instead of x/n, use x * n ** -1
Handling 0 was annoying, but then I got faster than 97%.
lol this is genius
edit: nevermind you get divide by zero error, it doesnt work :(
@@miken1299 You have to count the zeros. If multiple, return all zeros. If exactly 1 zero, return the product of the rest of the array at that index and the rest zeros.
can't believe i didn't even think to try this first
Commenting twice to help with the algorithm :)
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?
love the way you explain. Easy, crisp and perfect :)
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)?
Ngl whoever designed the question shouldn't have written " The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer ", this statement made the problem way easier than it is as It is a pretty big hint. You can easily figure that part out just by looking at the constraints(i.e 100000 x 30) will never exceed 32 bit int. At least the follow up question was good.
Take a bow! Very helpful explanation.
Is this really the easiest solution to this problem? I don't know the answer but there must be a different, simpler way!
For such problems, I think they first made solution and then they changed it into a problem.
Thank you, this explanation was very clear to me!
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.
What app do you use to make your whiteboards?
I use paint3d
Thanks!