LeetCode 238. Product of Array Except Self (Solution Explained)
ฝัง
- เผยแพร่เมื่อ 22 ส.ค. 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
How the hell are you supposed to figure this out without knowing the “ah-ha” trick?
It is more like math. Have to exercise more look at more problems and solutions. SO that is right coding interview is not easy. a lot trick questions
Do loads of problems, your brain will start thinking like that
@@shrimatkapoor2200 that's still like learning all the "ah-ha" tricks until you have learnt sufficiently enough to solve the current scope of problems. It essentially isn't "thinking like that" but "applying like that".
i hate that the answer is just 'practice more' on basically math puzzles, but it's the least worst answer.
likely you will not - and is why this style of tech interview is so fundamentally broken ...
Whenever I need to find a solution to any Leetcode problem I look into your channel first. None other explains like you do! Claps claps 👏👏
Hey thanks for mentioning the difficulty in the thumbnail itself- keep up the great work!
Thanks a lot! The transition from 2 arrays to 1 becomes really intuitive.
I get it, but I don't get how you're supposed to figure this out in a 30 min interview and I've done a few of these. I don't think the person who came up with this problem did it in 30 mins, do they just expect people to have done all these problems before?
Possibly, they would give the hint but, I think they want you to think in the direction for saving space rather than knowing the trick to solve it. I can't speak for every recruiter though XD
you're not supposed to figure this out in 30 mins. The people who came up with this algorithm were computer scientists that did it over years of research papers and improving each other's work. Just as any interview question, this once was a recently created algorithm, which eventually became common knowledge and now interviewers expect you to know all of this stuff as if we were all 69 thousand times smarter than the people that came up with these algorithms.
Quick update, right after this post I ended up getting lucky and joining fang lol. Extra emphasis on LUCKY
@@kickhuggy you think working for fang is being "lucky"?
@@AlFredo-sx2yy i meant I got lucky on the interview, but yeah I get paid half a mil to work remote, doing what I love and traveling. Could be worse
This was a really excellent explanation. I went through it a couple times but the code was just intuitive after the explanation! Your videos really help a lot man. Thanks!
Great video! Love that you solved it first with the extra space and then simplified, much easier to follow.
Really loved this explanation. Thanks. Man what a bummer, leetcode's Solution is locked unless you're Premium atm. Good thing this video is out there
ive watched several videos of this problem and yours has the best explanation by far. Thanks!
I am seriously addicted to his videos!
Thanks Nick! Boy I did hate this question
I just solved this today, but wow you really made it click for me when you said pretty much everything to the left of x times everything to the right of x. NOW it makes sense. Thank you Nick.
Thanks nick. as a beginner this question really fried me. it is nice to have a clean explanation.
Thank you for the first solution! Made SO much more sense than the leetcode answers..
I got this problem as a take home interview. One detail you didn't mention is checking for zeros. Once you hit a zero, that's the only element that needs to be calculated. Once you hit two zeros the problem is over and you return all zeros.
Why would you need to 'check' for zeroes? Zeroes automatically sort themselves out given you're doing the multiplication right.
@@solaimanjawad5015 it's a little optimization
Thank you! I was always confused about this problem but now I get it
As usual, great explanation.
Great video.
I have a query - if we haven't seen such category of problem what is the likelihood of coming up with the most optimal solution in 30-35 mins.
I have solved around 70-80 problems in leetcode, and occasionally there are such questions which stump me. Now I have seen this, so a variety of this should be easy!
Does this mean we have to solve a huge numbers of problem, and hope that the problems asked at FAANG interview is a variety of what I have seen before ?
Same question..
great video! i have a question: you said that would be very easy to do this using division. Ok, for the first case [1,2,3,4] it works. But for the second case [-1,1,0,-3,3] how would you solve this using the division method?
This was the interview question i had for the amazon internship
When?
This example is so good and clear!!
thumbs up before watching the video
Thank you, Nick. It is a great explanation!
is there a textbook you might recommend for someone wanting to improve their understanding of Data Structures and Algorithms?
thank you for great visual!
We need more guys like you
How long does it take you to understand this problem and how many practices to grasp it well ? also as of now can you still do this in under 30mins?
Great explanation on the solution but I was looking for why the product from both directions equals the result we are after.
I can think of a bruteforce way but this would be n^2 which would be stupid. Thank you
Awesome Explanation. Thank you so much🔥
You are awesome, Thanks alot !
You're a GOD Nick
No division - oh sure obviously just get right and left product arrays, multiply them and that's it, so easy and intuitive.
How the f*ck to come up to that during the interview, there is no any math as well as intuition around wtf...
seriously!!
very well explained. Thank you!
what time complexity is when it done with division?
I think - 2n i.e. O(n) you loop once to find the entire product and then you loop again to find individual answer by dividing itself from entire product
division is slightly slower than multiplication on the processor, but that doesnt really matter. The main reason they hint you not to divide is because of the number 0. Just think about this: What is something divided by 0?
2:20 also if the array contains 0 then it will give error, as you cannot divide a number by 0.
Am i right????
The second solution blew my mind! Loved it. Thanks!
Beautiful explanation!
Great explanation, appreciate it!
easy to understand , thanks
what space complexity for this ?
why is this O(n)?
there are multiple loops (one foroward and one backward), even though they are not nested.
If multiple not-nested loops are stil O(n), then why is this solution better than looping N times and generating the product?
nested loops are N^2 and separate loops are O(N) watch the video I made on time complexity in my technical interview study guide playlist
Nick White I know that. But if seperated loops are O(n) then what is the difference between looping twice back and forth and looping N times for each index?
Watch the video I just told you to watch
Nick White I watched it. There is no answer there for what is the difference between N for loops and 2 for loops regarding their running time. If there is no difference then whay the back and forth loop solution is better than just looping for each element?
@@hali1989 Doing left right you get 2n ~ n. Looping n times for each index is n^2. It looks small in this size of array. Hence it could be fine but as the array grows its evident its going to be bad. Remember, however big the constant is it does not matter much. it could be 2*n or 100*n, it would still be O(n) in terms of time complexity.
Best explanation
So there's 3 loops in this solution, albeit not nested loops. Why is it that this will be faster than just having a double for-loop? I know there will be an activation record for each inner for loop iteration but the double forloop solution processes less numbers than this 3 loop solution.
nested for loop has a time complexity of n^2 but if the are not nested then it is 2n which is O(n)
@@yassirsoukaki4111 thanks I understood it after a while
thank you Nick
good explanation
Solving the space complexity was a bit hard. But we'll explained
Clean solution dude.
Thanks!!!!
Please can u tell me why he declared
int[ ] array _name= new int[ ];
What is the use of new and declaration of it
@@SYD_Technologies It declares the array on the heap. You can google about dynamic allocation vs static allocation
amazing explanation
That is a clever solution.
Here is another solution I put together quick, same output, no division and uses the *= operator
public class Demo {
public static void main(String[] args) {
int products[] = {1, 2, 3, 4};
int total[] = new int[4];
int ct = products.length;
for (int i = 0; i < 4; i++) {
int r = 1;
for (int x = 0; x < ct; x++) {
if (x != i) {
r *= products[x];
}
}
total[i] = r; }
for (int t = 0; t < 4; t++) {
System.out.println(total[t]);
}
}
}
the solution requires O(n) complexity too
Thanks man🤩
Great idea for a question, we will ask this one soon!
excellent!!!
thank u bruh
very nice explanation:)
still don't get how that works after the explanation lol
I feel like I would never come to this conclusion on my own despite being a programmer :(
u rock man!
Wow, who would think about reversing the damn array and creating another array for it then multiplying it together to get the answer hahahahaha
Genius stuff here but good to see that this kind of problem can be tackled this way.
thanks man
Hey Nick, love your videos, thanks for them!!! Just one question though, isn't your first solution O(n^2) time complexity?
The time complexity is linear. The for loops are not nested and multiple for loops doesn't make it O(n^2). If the test cases were very large than you might see an issue on performance. In this case: O(3n) or O(n + n + n) for the 3 loops is just O(n).
@@dennisllopis2478 thanks for the response! That makes a ton of sense!!
thanks man more problems
thanks, great job!
Awesome.
Had a solution but it fails the last test cause takes too long. :(
So what happens when you get asked this question and you already know the answer?
you act like you're coming up with the solution like a genius. Propose the naive nested loops approach, and say "but that would be too slow as it would be O(N^2)" and then propose whichever solution you think you'll have enough time to code.
@@AlFredo-sx2yy right.. but there's no 'whichever' solution, because this solution remains ingrained in my head; I see this problem and automatically I know, do a forward loop and then a reversed loop. Some of these problems have a cookie cutter answer and it would be awkward to dance around it.
@@minciNashu with "whichever solution you prefer" i meant either of the 2 approaches shown in this video: either use the 2 arrays approach or the single array and auxiliary variable approach.
I did not mean you should create some sort of invented answer...
You can work for as long as you want and invent a new answer but that makes no sense, if you already know the best answer that was engineered over years by people before you then why try to make one up on the spot? your job is on the line so...
how about
let ans = log(sum of all expect current num) - log (current num)
return antilog(ans)
That is just division with more steps dude...... log(x) - log(y) = log(x/y)... also doesn't work with zeroes
@@RHCPhooligan there are no zeros
@@juanmoscoso0 you’re right but that shows how stupid these problems are. What kind of real world matrix problem exists where there are no zeros ?
@@RHCPhooligan they are testing your problem solving
My solution but with JS
function productExceptSelf(nums) {
const output = [];
for (num of nums) output.push(
output.filter(number => number !== num)
.reduce((a, v) => a * v)
);
return output;
}
Awesome
can you explain in awwapp?
Bro this question was such bullshit. I spent so much time trying to figure out how to ONLY use `nums` to store the intermediate result............ and now we are just saying that creating just 1 extra array doesn't count as extra space. wow.
Python:
array = [1, 2, 3, 4]
productOfAll = functools.reduce(lambda prod, i: prod * i, array)
output = list(map(lambda i: productOfAll / i, array))
Uses division.
@@omarathon5922 Did the question mention not to use division?
Its says in the note
won't work if we have 0's in the list
Python without division
products = [1,2,3,4]
box = []
for i, v in enumerate(products):
r = 1
for y in range(len(products)):
if (y != i):
r *= products[y]
box.append(r)
for i in box:
print(i)
cant use division?
*uses negative number exponent*
surprised Pikachu face.