Product of Array Except Self - Leetcode 238 - Python
HTML-код
- Опубликовано: 28 июн 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/products...
0:00 - Read the problem
2:09 - Drawing Explanation
9:47 - Coding Explanation
leetcode 238
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#product #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. 
Наука
🚀 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
Sometimes you skip through the time complexity explanation. With division, how would it be o(n) ... You need to multiply all elements and THEN loop through ...oh I see
It's o(n + n) which is o(n)
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
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
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.
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
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?
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
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.
This problem was extremely difficult for me to understand, thank you for explaining so clearly!
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.
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?
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
Thank you so much for making these videos! You explain the problem and present the solution very clearly.
I have never been able to get this right until I saw this explanation. You seriously rock !!
love the way you explain. Easy, crisp and perfect :)
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?
love your clear explanations, keep doing what you're doing man - you're amazing!!
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 !!!
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.
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 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
problems after your explanation become so transparent and understandable. Thank u so much
This process is extremely clear to understand.
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!
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
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?
Thanks for the sheet, we love you 3000!
Im so glad you exist. Thank you kind sir.
These kind of problems make me feel stupid. Thanks for the breakdown, this made sense!
Super helpful, Thank You!
Nice and clear. Plx keep up the good work!
What do you use for your note/drawling program? Color switching seems slick
concept of prefix product and postfix product is amazinggg!!
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 moment I saw the prefix, postfix on the screen, I got the approach
absolutely brilliant, thanks a ton
honestly didn't even know what the problem was asking me to do. thank you
Amazing concise explanation. Thanks bro
It's a cake walk. Love your explanations!!!!
Great Explanation
Third time I am trying to figure out this problem, this explanation was the best. I hope I will remember it...
Thanks a lot for your great content! It allows me to gain insights immediately to the problem via your clear explanations.
First problem I totally failed to solve myself =( Thank you for your explanation, video made me unstuck finally
Take a bow! Very helpful explanation.
awesome explanation dude!
Keep doing man, your content is amazing!! Love from India ❤️💜
Just asking can you use a sliding window for this
Wow that's a really clever way to reduce the space complexity
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.
Thank you so much for this video! You are talented at explaining things!
Wow!!! This is another level of genius
Great video and explanation
what textbook would you recommend for someone trying to better their understanding of Data Structures and Algorithms?
that was a lot to take in! Really!
Neetcode is the best, coded the solution with extra space complexity myself now moving to a better space solution.
What a great explanation!
Thank you soooooooooo muchhhhhh ..
My guy you have helped me a lotttttt
I am glad that I understood by going through this explanation, but afraid I wont remember in real interview
Good Explanation!! Thanks!
the best leetcode solution explainer with python on YT. Yet haven't seen one with such quality
Thank you, also easy to write and readable.
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.
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.
Wonderfully explained really appreciate the work !
Excelent approach!
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?
Thank you for your solution. But I don't quite understand in the second loop why it needs to iterate to -1, not 0? Thank you so much in advance!
How do you make your videos? I'm really enjoying the content!
Very nice explaination!!
That optimal solution grows crazy - wow
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.
I had a doubt regarding the division operator solution, for the second test Case when one of the element is 0, The product of all elements will become 0, how do we handle it?
Hey can you please share that blind 75 excel sheet of yours. would be really helpful
This is very good man, i really hope I get good at Dsa one day
My initial thought was to find the product of the array and divide that product by the values in the positions
Ill never get into an entry level pos. I could not even figure out prefix postfix solution let alone with only using 1 array.
Great video. Can we do res[i] *= prefix in line 7? since we are multiplying only by 1 anyway.
Neetcode is well-suited name for this channel as how neatly and clearly you explain the intuition. Thanks
It is questions like this which makes learning dsa even more exciting. I know a lot of folks might be thinking am I crazy to say that but I see learning dsa as a cool skill which I can flex upon those who haven't just practiced enough. Yes "practiced enough" coz eventually anybody who has practiced consistently months over months would be at this level of thought. Sounds crazy right?
thank you so much!
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’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.
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.
Thank you so much for the visualization, tried to code it up myself before watching your solution and it worked like a charm. for anyone still wanting to try for themself just skip to the start of drawing and look at it.
Does it not break if there is a zero in the middle of the given array?
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
Good stuff.
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 RUclips 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.
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 so much
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.
You’re damn good Sir! I am in good hands…
Thank you for the video