LeetCode 238. Product of Array Except Self (Solution Explained)

[@jelliott1458]

How the hell are you supposed to figure this out without knowing the “ah-ha” trick?

[@leomonz]

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

[@shrimatkapoor2200]

Do loads of problems, your brain will start thinking like that

[@SakshamArmstrong123]

@@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".

[@Hyperian]

i hate that the answer is just 'practice more' on basically math puzzles, but it's the least worst answer.

[@miramar-103]

likely you will not - and is why this style of tech interview is so fundamentally broken ...

[@RakaChowdhuryUK]

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 👏👏

[@edwardnewgate2198]

Hey thanks for mentioning the difficulty in the thumbnail itself- keep up the great work!

[@kickhuggy]

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?

[@sherlockstark1706]

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

[@AlFredo-sx2yy]

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.

[@kickhuggy]

Quick update, right after this post I ended up getting lucky and joining fang lol. Extra emphasis on LUCKY

[@AlFredo-sx2yy]

@@kickhuggy you think working for fang is being "lucky"?

[@kickhuggy]

@@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

[@grootz2820]

Thanks a lot! The transition from 2 arrays to 1 becomes really intuitive.

[@louismontes6632]

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!

[@BrentSnider]

Great video! Love that you solved it first with the extra space and then simplified, much easier to follow.

[@HakuzaPK]

For anyone still confused, remember that any index on either the left or right side is the product of all elements leading up to that point, thus excluding that given element from the product. For example, the second element, 5, has a left side product of 4 (which is just 4 times 1, excluding 5) and a right side product of 16 (which is just 8 times 2 time 1 and 1 again, excluding 5 once again). So when you find the product of both these numbers (4 and 16) you get the product of the entire array except the number that corresponds to that index since both the left and right side of that index excludes the index itself. This is the reason why it works, pretty simple once you figure it out. Once you get this pattern it makes solving problems similar to it much easier. Sorry if my writing sucks or has redundancies, it helps me to learn by explaining so this helps both of us :).

[@NickKravitz]

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.

[@solaimanjawad5015]

Why would you need to 'check' for zeroes? Zeroes automatically sort themselves out given you're doing the multiplication right.

[@JM_utube]

@@solaimanjawad5015 it's a little optimization

[@Historyiswatching]

Thanks Nick! Boy I did hate this question

[@Sandboxcode]

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

[@shadowthehedgehog2727]

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.

[@suharajsalim4549]

I am seriously addicted to his videos!

[@fcsie]

ive watched several videos of this problem and yours has the best explanation by far. Thanks!

[@leezhenjian7451]

Thanks nick. as a beginner this question really fried me. it is nice to have a clean explanation.

[@nullnull8685]

Thank you for the first solution! Made SO much more sense than the leetcode answers..

[@thedanglingpointer8411]

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 ?

[@sanskarkaazi3830]

Same question..

[@justworkfine321]

what time complexity is when it done with division?

[@sherlockstark1706]

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

[@AlFredo-sx2yy]

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?

[@mr.plua123]

is there a textbook you might recommend for someone wanting to improve their understanding of Data Structures and Algorithms?

[@svdfxd]

As usual, great explanation.

[@rebechkah]

This was the interview question i had for the amazon internship

[@usa5450]

When?

[@omgharajuku]

Thank you! I was always confused about this problem but now I get it

[@gamesandstuff4188]

We need more guys like you

[@calp8395]

Great explanation on the solution but I was looking for why the product from both directions equals the result we are after.

[@robinlam5038]

This example is so good and clear!!

[@monkeytrollhunter]

I can think of a bruteforce way but this would be n^2 which would be stupid. Thank you

[@ezekieledak]

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?

[@bldbld18]

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...

[@mikejj781]

seriously!!

[@arthurmastropietro5261]

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?

[@Frknuzny]

//Should have read the description better. Divison operater can't be used!!! // int product = 1; // int zeroCounter = 0; // for (int i : nums) { // if (i == 0) { // zeroCounter++; // } else { // product = product * i; // } // } // for(int i = 0; i < nums.length; i++){ // if(zeroCounter >= 2){ // productArry[i] = 0; // } // else if(nums[i] == 0 && zeroCounter == 1){ // productArry[i] = product; // } // else if(zeroCounter == 1){ // productArry[i] = 0; // } // else { // productArry[i] = product/nums[i]; // } // } // return productArry;

[@rishabhrajpathak8347]

2:20 also if the array contains 0 then it will give error, as you cannot divide a number by 0. Am i right????

[@hali1989]

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?

[@NickWhite]

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

[@hali1989]

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?

[@NickWhite]

Watch the video I just told you to watch

[@hali1989]

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?

[@grunze]

@@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.

[@AreYouExperienced0]

is java still good in 2024?

[@uanbu6539]

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.

[@yassirsoukaki4111]

nested for loop has a time complexity of n^2 but if the are not nested then it is 2n which is O(n)

[@uanbu6539]

@@yassirsoukaki4111 thanks I understood it after a while

[@bisujin1685]

thumbs up before watching the video

[@samandarboymurodov8941]

Thank you, Nick. It is a great explanation!

[@skumakerguitar8708]

what space complexity for this ?

[@cybersecurity2812]

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]); } } }

[@wojtekrosiak5691]

the solution requires O(n) complexity too

[@minciNashu]

So what happens when you get asked this question and you already know the answer?

[@AlFredo-sx2yy]

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.

[@minciNashu]

@@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.

[@AlFredo-sx2yy]

@@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...

[@aakritirastogi1660]

The second solution blew my mind! Loved it. Thanks!

[@diegotrujillo6284]

You're a GOD Nick

[@tharunprabakaran]

You are awesome, Thanks alot !

[@nikoman71326]

thank you for great visual!

[@lifeofme3172]

Solving the space complexity was a bit hard. But we'll explained

[@ploratran]

very well explained. Thank you!

[@codeelsewhere]

how about let ans = log(sum of all expect current num) - log (current num) return antilog(ans)

[@RHCPhooligan]

That is just division with more steps dude...... log(x) - log(y) = log(x/y)... also doesn't work with zeroes

[@juanmoscoso0]

@@RHCPhooligan there are no zeros

[@RHCPhooligan]

@@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 ?

[@juanmoscoso0]

@@RHCPhooligan they are testing your problem solving

[@The2Coolest2]

Had a solution but it fails the last test cause takes too long. :(

[@abhishekpolicepatil2829]

Beautiful explanation!

[@Hyperian]

still don't get how that works after the explanation lol

[@lovipilowu9766]

I feel like I would never come to this conclusion on my own despite being a programmer :(

[@shubhamtiwari6660]

Clean solution dude. Thanks!!!!

[@SYD_Technologies]

Please can u tell me why he declared int[ ] array _name= new int[ ]; What is the use of new and declaration of it

[@verushannaidoo9450]

@@SYD_Technologies It declares the array on the heap. You can google about dynamic allocation vs static allocation

[@jocavuleta]

Great explanation, appreciate it!

[@sehajpreetsingh4177]

That is a clever solution.

[@ByteMock]

Great idea for a question, we will ask this one soon!

[@Kidkromechan]

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.

[@huansir1922]

easy to understand , thanks

[@mysterygirl191]

amazing explanation

[@shrirambalaji2109]

thank you Nick

[@GrassLover9]

good explanation

[@internick_]

Best explanation

[@fahimemroz9141]

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; }

[@yuvrajdarekar3494]

Thanks man🤩

[@zarinb2278]

Hey Nick, love your videos, thanks for them!!! Just one question though, isn't your first solution O(n^2) time complexity?

[@dennisllopis2478]

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).

[@zarinb2278]

@@dennisllopis2478 thanks for the response! That makes a ton of sense!!

[@vivekgr3001]

very nice explanation:)

[@justworkfine321]

can you explain in awwapp?

[@ritesh4165]

u rock man!

[@ZEE-fs6hv]

thanks man more problems

[@PumpkinEatSpice]

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.

[@chaoschao9432]

thanks, great job!

[@t.saisrujan9456]

thanks man

[@saeedentezari3776]

Python: array = [1, 2, 3, 4] productOfAll = functools.reduce(lambda prod, i: prod * i, array) output = list(map(lambda i: productOfAll / i, array))

[@omarathon5922]

Uses division.

[@saeedentezari3776]

@@omarathon5922 Did the question mention not to use division?

[@ashishkhuraishy]

Its says in the note

[@Yeager098]

won't work if we have 0's in the list

[@cybersecurity2812]

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)

[@parambharti7095]

Awesome.

[@harshitha3867]

Awesome

[@__-kd8oz]

cant use division? *uses negative number exponent* surprised Pikachu face.

[@kaiserkonok]

Awesome Explanation. Thank you so much🔥

[@Karthik__S_554]

excellent!!! thank u bruh