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

No video

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

Рет қаралды 105,625

4 жыл бұрын

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow Me on X/Twitter - x.com/nickwhitereal
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/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

Пікірлер: 127

@jelliott1458 4 жыл бұрын

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

@leomonz 4 жыл бұрын

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 3 жыл бұрын

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

@SakshamArmstrong123 3 жыл бұрын

@@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 3 жыл бұрын

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

@miramar-103 3 жыл бұрын

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

@grootz2820 4 жыл бұрын

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

@edwardnewgate2198 4 жыл бұрын

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

@RakaChowdhuryUK 10 ай бұрын

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

@BrentSnider 4 жыл бұрын

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

@louismontes6632 2 жыл бұрын

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!

@fcsie 3 жыл бұрын

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

@Sandboxcode 3 жыл бұрын

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

@nullnull8685 4 жыл бұрын

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

@shadowthehedgehog2727 2 жыл бұрын

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.

@kickhuggy 3 жыл бұрын

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 2 жыл бұрын

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

@suharajsalim4549 4 жыл бұрын

I am seriously addicted to his videos!

@svdfxd 4 жыл бұрын

As usual, great explanation.

@leezhenjian7451 7 ай бұрын

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

@lilyh4573 2 жыл бұрын

Thanks Nick! Boy I did hate this question

@omgharajuku 7 ай бұрын

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

@samandarboymurodov8941 Жыл бұрын

Thank you, Nick. It is a great explanation!

@tharunprabakaran 4 жыл бұрын

You are awesome, Thanks alot !

@kaiserkonok Жыл бұрын

Awesome Explanation. Thank you so much🔥

@robinlam5038 5 ай бұрын

This example is so good and clear!!

@ezekieledak 3 жыл бұрын

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?

@thedanglingpointer8411 4 жыл бұрын

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 2 жыл бұрын

Same question..

@ploratran 3 жыл бұрын

very well explained. Thank you!

@mr.plua123 9 ай бұрын

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

@calp8395 2 жыл бұрын

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

@arthurmastropietro5261 11 ай бұрын

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?

@bisujin1685 4 жыл бұрын

thumbs up before watching the video

@jocavuleta 4 жыл бұрын

Great explanation, appreciate it!

@abhishekpolicepatil2829 4 жыл бұрын

Beautiful explanation!

@nikoman71326 17 сағат бұрын

thank you for great visual!

@gamesandstuff4188 Жыл бұрын

We need more guys like you

@skumakerguitar8708 2 жыл бұрын

what space complexity for this ?

@rebechkah Жыл бұрын

This was the interview question i had for the amazon internship

@usa5450 Жыл бұрын

When?

@monkeytrollhunter 4 жыл бұрын

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

@Karthik__S_554 Жыл бұрын

excellent!!! thank u bruh

@huansir1922 2 жыл бұрын

easy to understand , thanks

@mysterygirl191 3 жыл бұрын

amazing explanation

@vivekgr3001 4 жыл бұрын

very nice explanation:)

@NickKravitz 4 жыл бұрын

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 4 жыл бұрын

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

@JM_utube 4 жыл бұрын

@@solaimanjawad5015 it's a little optimization

@diegotrujillo6284 20 күн бұрын

You're a GOD Nick

@internick_ Ай бұрын

Best explanation

@aakritirastogi1660 4 жыл бұрын

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

@shrirambalaji2109 2 жыл бұрын

thank you Nick

@sehajpreetsingh4177 2 жыл бұрын

That is a clever solution.

@GrassLover9 4 ай бұрын

good explanation

@ByteMock 4 жыл бұрын

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

@yuvrajdarekar3494 3 жыл бұрын

Thanks man🤩

@ZEE-fs6hv 4 жыл бұрын

thanks man more problems

@ritesh4165 4 жыл бұрын

u rock man!

@justworkfine321 3 жыл бұрын

what time complexity is when it done with division?

@sherlockstark1706 2 жыл бұрын

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?

@rishabhrajpathak8347 2 жыл бұрын

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

@shubhamtiwari6660 4 жыл бұрын

Clean solution dude. Thanks!!!!

@SYD_Technologies 4 жыл бұрын

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

@verushannaidoo9450 3 жыл бұрын

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

@bldbld18 3 жыл бұрын

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

@t.saisrujan9456 2 жыл бұрын

thanks man

@lifeofme3172 3 жыл бұрын

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

@chaoschao9432 4 жыл бұрын

thanks, great job!

@Hyperian 3 жыл бұрын

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

@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

@The2Coolest2 2 жыл бұрын

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

@Kidkromechan 2 жыл бұрын

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.

@cybersecurity2812 3 жыл бұрын

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

@justworkfine321 3 жыл бұрын

can you explain in awwapp?

@parambharti7095 3 жыл бұрын

Awesome.

@codeelsewhere1688 4 жыл бұрын

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

@RHCPhooligan 4 жыл бұрын

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

@juanmoscoso0 3 жыл бұрын

@@RHCPhooligan there are no zeros

@RHCPhooligan 3 жыл бұрын

@@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 3 жыл бұрын

@@RHCPhooligan they are testing your problem solving

@lovipilowu9766 9 ай бұрын

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

@harshitha3867 3 жыл бұрын

Awesome

@zarinb2278 3 жыл бұрын

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

@dennisllopis2478 3 жыл бұрын

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 3 жыл бұрын

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

@hali1989 4 жыл бұрын

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 4 жыл бұрын

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 4 жыл бұрын

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 4 жыл бұрын

Watch the video I just told you to watch

@hali1989 4 жыл бұрын

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 4 жыл бұрын

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

@minciNashu 2 жыл бұрын

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

@fahimemroz9141 4 жыл бұрын

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

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

@saeedentezari3776 4 жыл бұрын

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

@omarathon5922 4 жыл бұрын

Uses division.

@saeedentezari3776 4 жыл бұрын

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

@ashishkhuraishy 4 жыл бұрын

Its says in the note

@Yeager098 4 жыл бұрын

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

@cybersecurity2812 3 жыл бұрын

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)