🚀 neetcode.io/ - A better way to prepare for Coding Interviews

@vusumuzindhlovu

2 жыл бұрын

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

@devstuff2576

2 жыл бұрын

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)

@thamaraiselvan8940

Жыл бұрын

isn't the memory complexity O(n).since u create a whole new list

@grandemcfloofin8376

Жыл бұрын

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

@shadan5487

Жыл бұрын

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

@luiggymacias5735

4 ай бұрын

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

@khalidhussien6764

4 ай бұрын

yeah, this is what we call a "crackhead" problem. 'Cuz no way you can come up with THAT solution unless you're a crackhead.

@killpointx

4 ай бұрын

@@luiggymacias5735*I did!* but this one is better! Keep coding

@sinnohperson8813

4 ай бұрын

nah i did come up with something similar , so its definitely intuitive enough but i took a lot of time but thats me

@nawzyah

3 ай бұрын

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

@hashtagaroma7778

Жыл бұрын

wow this made it click for me. thanks bro

@SebInsua

Жыл бұрын

Thanks for this. I never thought about writing it out as tiny equations but that makes it a lot clearer.

@viraje7940

Жыл бұрын

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!

@HarshitaSingh-bn1kp

Жыл бұрын

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

@andylinkOFFICIAL

2 жыл бұрын

No one just simply stumbles across this solution. It must have taken days for someone to figure this out.

@ncba

2 жыл бұрын

@@andylinkOFFICIAL we need that in 30mins during your interview

@mangalegends

2 жыл бұрын

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

@classified022

2 жыл бұрын

@@mangalegends A lot of people that came up with these algorithms took entire Phds to come up with them

@symbol767

2 жыл бұрын

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

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

@lcppproductions7910

Жыл бұрын

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.

@SuperGojeto

Жыл бұрын

Yeah totally agree. I hate this culture every company is trying to take this approach nowadays .

@drench1580

Жыл бұрын

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

@leeroymlg4692

Жыл бұрын

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.

@AlFredo-sx2yy

Жыл бұрын

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

@vladimirstrigunov7412

2 жыл бұрын

Fun fact - Neet's last name is Code

@montgomeryscottbrea2614

2 жыл бұрын

I literally had the same thought yesterday.

@onlyforwork8774

2 жыл бұрын

did you get your first paycheck

@montgomeryscottbrea2614

2 жыл бұрын

@@onlyforwork8774 not quite 😂😂😂

@wiley7327

Жыл бұрын

@@montgomeryscottbrea2614 🤣🤣

Absolute legend, this problem almost shouldn't be medium, the logic of doing this without division is mind bending without your explanation

@holo23

2 жыл бұрын

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.

@sanjeevsinha-in

2 жыл бұрын

Seriously, how one can come up with this approach in interview when facing this problem for the first time? this does not help.

@scythazz

2 жыл бұрын

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

@frozeninretro

Жыл бұрын

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

@zappy9880

2 ай бұрын

I tried with repeated subtraction but somehow it still figures it out. I guess LeetCode has a custom compiler or something.

@thehomiebearfifa3528

2 ай бұрын

lmao

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.

@jaspindersingh3097

2 жыл бұрын

Update: thanks to this guy. I got the job.

@varunshrivastava2706

2 жыл бұрын

@@jaspindersingh3097 Congratulations Man, In which company?

@ParryHotter73

Жыл бұрын

Yeah this, I used to start code right away and often get least optimal or inaccurate solution

@sahilgarg94

Жыл бұрын

@@jaspindersingh3097 congratulations.......

@nexolec109

Жыл бұрын

congrats

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.

@sola2943

2 ай бұрын

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.

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.

@luiggymacias5735

4 ай бұрын

and what is his first language?

Don't think I want a job anymore 🤣

@samuelpickering8557

Жыл бұрын

Did you get a software engineering job?

@luiggymacias5735

4 ай бұрын

did you get the job?

@oii0712

4 ай бұрын

No bro just gave up after looking at the solution​@@luiggymacias5735

@ahmedsafwat3488

3 ай бұрын

Did you get the job ?

@azka9075

2 ай бұрын

Have you gotten the job?

Thank you so much for making these videos! You explain the problem and present the solution very clearly.

This problem was extremely difficult for me to understand, thank you for explaining so clearly!

love the way you explain. Easy, crisp and perfect :)

How can I like a video multiple times? This is extremely well-explained, man! Thank you for creating this video. You are an inspiration!

@socaseinpoint

6 ай бұрын

Just press

Not using the extra memory really impacts the code's readability. Unless there is serious performance requirement, write readable code not clever code.

@fahadfreid1996

Жыл бұрын

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.

@user-xk2zy3ng1o

Жыл бұрын

Yes, but readability is not a concern during the interviews

@jean4j_

Жыл бұрын

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

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.

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!

@icychains24

2 жыл бұрын

By brute force do you mean an O(n^2) solution with nested loops?

@_Ahmed_15

2 жыл бұрын

Amazon lets you move on using brute force? Did you get an offer?

@HassaanALal

2 жыл бұрын

.

@Call-me-Avi

2 жыл бұрын

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

@nameless2850

2 жыл бұрын

@@Call-me-Avi still, the brute force for this is way too easy no? Like way too easy !!!

love your clear explanations, keep doing what you're doing man - you're amazing!!

I have never been able to get this right until I saw this explanation. You seriously rock !!

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.

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 🙏

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

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

@jerryteps

2 жыл бұрын

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

@dera_ng

2 жыл бұрын

@@jerryteps I tried doing this, it's messy.

@DrDemolition

2 жыл бұрын

@@dera_ng Can confirm, most of your time will be spent tackling those edge cases.

@ericshen1277

Жыл бұрын

Actually this constraint stops us from trying a buggy solution.

@light63478

Жыл бұрын

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

Absolutely loved it! Cant believe that you made it easy as a cake walk. Thank you!

Hey there. I just want to say thank you for making these videos!

@NeetCode

2 жыл бұрын

Thanks!

This process is extremely clear to understand.

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.

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.

@palatonian9618

3 ай бұрын

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?

Nice and clear. Plx keep up the good work!

Thanks for the sheet, we love you 3000!

What do you use for your note/drawling program? Color switching seems slick

Super helpful, Thank You!

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?

@julioagueros

3 ай бұрын

I think he just said the problem states it would not count

Im so glad you exist. Thank you kind sir.

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.

These kind of problems make me feel stupid. Thanks for the breakdown, this made sense!

Third time I am trying to figure out this problem, this explanation was the best. I hope I will remember it...

the moment I saw the prefix, postfix on the screen, I got the approach absolutely brilliant, thanks a ton

Amazing concise explanation. Thanks bro

It's a cake walk. Love your explanations!!!!

Take a bow! Very helpful explanation.

concept of prefix product and postfix product is amazinggg!!

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?

@guavavodka

11 ай бұрын

Because the output array doesn't count towards the limit (per the instructions). its basically cheating

What a great explanation!

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.

Great video and explanation

Good Explanation!! Thanks!

Thanks a lot for your great content! It allows me to gain insights immediately to the problem via your clear explanations.

honestly didn't even know what the problem was asking me to do. thank you

Thank you so much for this video! You are talented at explaining things!

Great Explanation

Just asking can you use a sliding window for this

awesome explanation dude!

Keep doing man, your content is amazing!! Love from India ❤️💜

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.

Thank you soooooooooo muchhhhhh .. My guy you have helped me a lotttttt

Wow that's a really clever way to reduce the space complexity

Wow!!! This is another level of genius

I am glad that I understood by going through this explanation, but afraid I wont remember in real interview

Neetcode is the best, coded the solution with extra space complexity myself now moving to a better space solution.

what textbook would you recommend for someone trying to better their understanding of Data Structures and Algorithms?

Very nice explaination!!

Excelent approach!

Wonderfully explained really appreciate the work !

Thank you, also easy to write and readable.

First problem I totally failed to solve myself =( Thank you for your explanation, video made me unstuck finally

That optimal solution grows crazy - wow

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 ?

@mastone5949

2 жыл бұрын

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.

@SnipeSniperNEW

2 жыл бұрын

@@mastone5949 thank you for clarifying, do you have any recommendation where I can learn more about big o analysis ?

@mastone5949

2 жыл бұрын

@@SnipeSniperNEW Top few results on KZread 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.

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?

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 res.append(left * right) return res this is the unoptimized code which he was talking about

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?

Does it not break if there is a zero in the middle of the given array?

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.

the best leetcode solution explainer with python on YT. Yet haven't seen one with such quality

Hey can you please share that blind 75 excel sheet of yours. would be really helpful

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.

This is very good man, i really hope I get good at Dsa one day

that was a lot to take in! Really!

thank you so much!

What app do you use to make your whiteboards?

@NeetCode

2 жыл бұрын

I use paint3d

@billvivino

2 жыл бұрын

Thanks!

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.

@meirbnb

Жыл бұрын

could you send the solution ?

@nexolec109

Жыл бұрын

what

Good stuff.

C++ code :- vector productExceptSelf(vector& nums) { vector ans(nums.size()); int prefix = 1, postfix = 1; for(int i=0; i=0; i--) { ans[i] = ans[i] * postfix; postfix = nums[i] * postfix; } return ans; }

Thank you for the video

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

@CoinBahd

4 ай бұрын

Space complexity is O(1) because the problem specified the result array does not count towards the space complexity. Kinda stupid

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.

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!

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.

@meirbnb

Жыл бұрын

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.

@NihongoWakannai

Жыл бұрын

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?

My initial thought was to find the product of the array and divide that product by the values in the positions

thank you so much

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.

what a legend!

This is a way better explanation than AlgoExpert has

can some explain why the space was not O(n) even though the result array was made

Your explanation is too good. Thanks God I found this channel

Neetcode is well-suited name for this channel as how neatly and clearly you explain the intuition. Thanks