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

@alekkras3487

4 жыл бұрын

great explanation

@kartikchauhan2778

2 жыл бұрын

Thanks

@frankl1

2 жыл бұрын

I love neetcode

Excellent explanation. For anyone curious, the algorithm in question in the O(N) solution is kadane's algorithm

@reyou7

2 ай бұрын

Kadane!!!! If I get into FAANG, I will leave a rose to your tombstone Kadane!

Hey man, i'm a postgrad CS student who didn't do anywhere near enough programming during my spare time in my bachelors. Your algorithms are really helping me think differently, thank you.

@thiswasme5452

2 жыл бұрын

Its never too late

@peteaustin5018

2 жыл бұрын

@@thiswasme5452 If you were curious as to how this helped me, I am now working as a software engineer for a good organisation and I also aced my postgrad academic studies :)

@thiswasme5452

2 жыл бұрын

@@peteaustin5018 Ohh great!! Nice to hear that 😊.

@celeschal

2 жыл бұрын

@@peteaustin5018 Yeee that's awesome, dude!

@djudsod959

2 жыл бұрын

@@peteaustin5018 that's great.

But if all negative results are disregarded, doesn't that exclude the case where all integers of the given array are negative?

@TeamDUSTOfficial

2 жыл бұрын

If all elements are negative integers, the max subarray will just be the maximum integer, because adding any negative value to an integer will make it smaller. And we will get this max integer, because we will reset the subarray every iteration and check for the max value.

@somewheresomeone3959

2 жыл бұрын

@@TeamDUSTOfficial Well but the current sum was set for zero, and it'll be the result after the max function so the maxSub will be zero instead of the first element

@TeamDUSTOfficial

2 жыл бұрын

@@somewheresomeone3959 You're adding the value of n at every iteration in the line `curSum += n` before the comparison so curSum won't be zero

@yeabseratesfayebekele5847

2 жыл бұрын

@@TeamDUSTOfficial tanx man I got it here

@Avighna

Жыл бұрын

Exactly what I was thinking!

great stuff brother, your explanations are so good by themselves, I dont even have to watch you code it up it just makes sense

Just did an interview with Amazon! This was the question. Unfortunately, I was thinking differently! Wish, I had watched this very well.

@SkySentry7

4 ай бұрын

You ethiopian I reckon from your profile. Did you land a job at faang?

@gautamanand6039

Ай бұрын

what role?

Love the way you explain things super easy to follow along

I think the part for whether to keep the prefix is: if (n > n + curSum) curSum = n; else curSum = curSum + n. In human language means if me alone is better than all of us combine, you guys are no use for me.

@sahil_tayade

2 жыл бұрын

This case will only happen if the curSum is negative anyways

@unanimous8510

8 ай бұрын

@@sahil_tayade that particular part I didn't understand in that solution... what if the previous curSum was even less than that and less than zero too...

@BaoziBandit

7 ай бұрын

I agree with this, in the case explained by @NeetCode, if the array is filled with only negative values, then the max would be 0, even if 0 doesn't exist in the array.... So, the check provided by @SumTsuiTechie sounds like a good approach to resolving that.

@jaredgentry406

Ай бұрын

n > n + curSum => n - n > n - n + curSum => 0 > curSum => curSum < 0

These video solutions are changing my life. Thanks Neet!

Of all the explanations on this algorithm, this video is the best. Thanks Man

I find it easier to understand Kadane's algorithm as bottom up DP optimized for constant memory. The max subarray sum starting at index i is nums[i]+max(0,dp[i+1]). In other words, it's the maximum of choosing to keep just nums[i] or include the maximum of elements after it (which may be negative)

One of the best and cleanest solutions, I have ever seen.

I forgot to thank you again for a great explanation. You are my savior!

Thanks for the series. Also Solution for the case where all numbers in array are negatives is returning the max number (which will be least negative number) int max = nums[0]; int curMax = 0; int maxNumber = INT_MIN; for(int i=0;i { curMax = curMax + nums.at(i); if( curMax { maxNumber = std::max(maxNumber, curMax); curMax = 0; } else max = std::max(curMax, max); } return (max < 0) ? maxNumber : max;

I've searched Kadane's Algorithm and solved this problem after understanding first. But I don't know how to explain this, so I've watched your video. I knew this I would learn from your video even after solving a problem without much problems. I learn from your videos how to think about a problem more than how to solve a problem. Negative values don't contribute anything to get the maximum number, that is why it intializes to zero to throw the previous max number which is a negative number. Great, thanks a lot!👍

Great video and explanation! Could you also explain how to solve the max subarray problem with divide and conquer? Thanks in advice!

Hi, what device and software do you use for draw the figures by free hand and use it in your screen recording?

@pekarna

2 жыл бұрын

I hear his mouse clicking, so likely just mouse. And there are many sw for over-the-screen drawing, like gInk.

Thanks, great explanation and good visuals.

Even more concise and easy to understand solution possible: # initialise both variables to negative infinity: maxSub, curSum = float('-inf'), float('-inf') for n in nums: curSum = max(curSum + n, n) maxSub = max(maxSub, curSum) return maxSub

Thank you Sir. I have made a silly mistake in this problem now it's clear.

This is such a simple and effective explanation. Thanks a lot, man :)

Thank you so much for your videos! They've been exceptionally helpful.

love ur tone and voice so much, good for listening the content into my brain

this teaches us the real working of kaden's algo....awesome question!

Does this solution work if the array contains only negative integers?

Thanks for the video. Very happy to find this video

Thanks for the video, it was super helpful

what if i need to print the index values: will it take another loop and it make another o(N) or any other approach rather than loop? could anyone help me???? Thanks in advance

I think you have to first add the total, and then check the condition if total is zero.

breaking up the video into different operation times >>>>>

Does it guarantees that it has positive numbers too? I saw this solution in the solutions of leetcode and I was confused as why it works.

what if the edge case of all negative numbers, is empty sub-array allowed ?

Do you have any ideas about the Leetcode follow-up question for that problem? "Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle." Seems, they've added the follow-up recently

@loopzz5526

Жыл бұрын

kzread.info/dash/bejne/q3Z33LFpdtPZhsY.html divide n conquer, this might help

@sergiofranklin8809

Жыл бұрын

ChatGPT gave this solution for divide and conquer: def maxSubArray(nums): def divide_and_conquer(nums, left, right): if left == right: return nums[left] mid = (left + right) // 2 # Find the maximum sum subarray in the left half left_max = float('-inf') curr_sum = 0 for i in range(mid, left - 1, -1): curr_sum += nums[i] left_max = max(left_max, curr_sum) # Find the maximum sum subarray in the right half right_max = float('-inf') curr_sum = 0 for i in range(mid + 1, right + 1): curr_sum += nums[i] right_max = max(right_max, curr_sum) # Find the maximum sum subarray crossing the middle element cross_max = left_max + right_max # Recursively find the maximum subarray sum in the left and right halves return max(cross_max, divide_and_conquer(nums, left, mid), divide_and_conquer(nums, mid + 1, right)) # Call the divide and conquer function to find the maximum subarray sum return divide_and_conquer(nums, 0, len(nums) - 1) explanation: The idea behind this algorithm is to divide the input array into two halves, and recursively find the maximum subarray sum in the left and right halves. The maximum subarray sum can either lie entirely in the left half, entirely in the right half, or cross the middle element. The maximum subarray sum that crosses the middle element can be found by computing the maximum sum subarray in the left half that ends at the middle element, and the maximum sum subarray in the right half that starts from the middle element. The time complexity of this algorithm is O(n log n), where n is the size of the input array.

@shriharikulkarni3986

10 ай бұрын

Did you get the solution for the follow up?

@MichaelButlerC

9 ай бұрын

I'm also interested as to what this means

@illu1na

9 ай бұрын

@@shriharikulkarni3986check the solution section in the leecode there is this one guy who showed 7 different solutions

In my opinion, this is de best video that I have found about this problem

Why does the runtime is so big when submitting to leetcode? Is this time related to a bunch of robustness tests right?

i tried to code in c++ but failed :( what should be the approach/code for in c++

What about if the test case was an array of all negative integers? Wouldn't we end up returning zero when the actual answer is the least negative of those given integers? Since curSum is initialized to 0 and at no point will our "max(maxSub, curSum)" code return anything other than 0 since it will always be higher than a negative number ?

beautiful explanation as always. Thank you

amazing, could you please make this q with divide and conquer?

but where is the condition to remove the negative values

A solution that works the same but is a bit less clear is def MaxSubArray(nums): for i in range(1,len(nums)): if nums[i-1] > 0: nums[i] += nums[i-1] return max(nums)

Beautifully explained!

If I want to return both subarray and the maximum sum how can i do that

Thanks for the video bro!

what happens if all the values are negative in the array ?

@mohameddaffaallah6243

10 ай бұрын

the curSum will always reset to each negative number in the array and the maxSub will keep the highest number

@mohameddaffaallah6243

10 ай бұрын

add this at the end of the forloop for a clearer understanding print(f"curSum = {curSum} MaxSub = {maxSub}")

One edge case is missing. What if all numbers are negative [-1, -3, -4]. We need to return -1. But this algorithm will return 0.

@AGuilmon

2 жыл бұрын

It won't, the code keeps track of the max sum seen. Inside the loop, it initializes the current sum to 0 if it's negative, then proceeds to add the current number (negative in this case) to the current sum. Then, if the current sum is bigger than the max sum seen, it will set max sum to the current sum (in this case a negative). It will keep track of the smallest negative seen (the smaller a negative the bigger it is compared to other negatives).

very good explanation, Thanks

Wow. This is actually genius.

Thank you, I really understood it. but did we use dynamic programming in this solution?

@CostaKazistov

2 жыл бұрын

This way of solving this problem is known as Kadane's Algorithm. Kadane’s Algorithm is an *iterative dynamic programming* algorithm in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.

Does sorting work on this problem? And Keep adding the numbers till the value decreases?

I dont understand why if current sum is negative then it doesnt contribute anything can you explain more on this issue?

Hi! Thank you for the video, it provided me with a few insights. One question, so this algorithm won't work if the array contains only negative numbers?

@user-mm8fg4gv5s

9 ай бұрын

It doesn't matter, since when you come to nums[p] if the preSum < 0, you set it back to 0, and now current sum is just nums[p], then you use max() to recored the new maxSum, even if all numbers is negative, if nums[p] is the biggest one, you will find and record it in this step

This solution wouldn't work for the case where all numbers in the array are negative, would it?

Hi sir. What if the array is [-1,-2,-3,-4] like this?

@sachinshaji92

2 жыл бұрын

For the code to work in any scenario(All Negative,All Positive,Mix) make this change: for n in nums: if curSum curSum= n

@milkyicy9482

2 жыл бұрын

I guess you can add an if statement if the max number in the array is negative, just output the max number if max(nums)

@smarty7193

2 жыл бұрын

it will work irrespective of input max=-1 sum=0 ----- for loop ----- sum=-1 max =-1 ------ sumsum so max will remain -1 ---- and so on

@yosefco3

2 жыл бұрын

class Solution: def maxSubArray(self, nums: List[int]) -> int: m = nums[0] s = nums[0] for n in nums[1:]: if n > s and s s = n else: s += n m = max(m, s) return m

@yonahgraphics

2 жыл бұрын

It still works

thanks man, big help!

Great Explanation :)

what is the maximum sum is a negative number, the code would only output 0 then

@kurokikazenootoko

3 жыл бұрын

Not really. Assume the array only contains negative numbers. At start maxSub will equal to first element. Then in every iteration we do reset maxSub to zero, but we immediately sum it with next number (a negative too) making it equal to that number. So it will check first element against each next element, each time updating maxSub to the max of two. That's just classic "find max" one-pass algorithm.

@stevefox7418

3 жыл бұрын

In addition to what Сергей said, notice how we are storing the max element in maxSub and then returning that. So in the case of an array containing all negative numbers, it will return the maximum negative number.

@sachinshaji92

2 жыл бұрын

For the code to work in any scenario(All Negative,All Positive,Mix) make this change: for n in nums: if curSum curSum= n

Doesn't resetting curSum to 0 assume that there are values in our array that are >= 0? What if all our values are negative?

i though there is no intuition behind this algo, i just need to memorize it, but you changed my mind

This was the easiest explanation and solution of this problem. Played it at 1.5x and was able to understand

What if the whole array is made of negative numbers? Would this still work?

Smart solution! (This should be a medium question.)

Great explanation but i have one doubt .. There may be an array of all negative numbers and in such scenario , one subarray may sums up to -5 other subarray to -10 so -5 will be the answer. So curSum < 0 may not work in this case. Please correct me if i am wrong.

hey what if the whole array is negative.. will it work??

I don't not fully understand the if (cursum < 0) part. why 0?

@tarsco4235

10 ай бұрын

you'll get a lower answer than the highest max you can get if you don't reset it to 0, and you can't set it higher than zero because your total will be higher than the max sub array. you can get away with "forcing" a current sum of zero because it helps you reach your maximum.

This was very helpful, please make a Divide and conquer solution for this too.

but if we put curSum

Hey, quick question about the linear time solution, would this code blow up given an array of all negative values?

@qqqqoeewqwer

3 жыл бұрын

still work, the max element value of the array will be the answer

@dontdemotivate6575

3 жыл бұрын

@@qqqqoeewqwer I don't think that it will work as my input is [-1] or [-2,-2,-3,-1,-4,-5] because by this code answer will 0

@ThePunlee

3 жыл бұрын

@@dontdemotivate6575 have you tried running the code yet? Answer is not going to be zero, since there is the maxSum variable that stores the answer to your example: [-2,-2,-3,-1,-4,-5].

@ic2800

2 жыл бұрын

it won't. best way to learn this is to run this code and print the part that you are unclear. given all negative number the max() function will return the largest negative number of the array

@sachinshaji92

2 жыл бұрын

For the code to work in any scenario(All Negative,All Positive,Mix) make this change: for n in nums: if curSum curSum= n

hey i have a doubt, when I have coded in python the line i have added was if cursum

@sanjasme

2 жыл бұрын

This will fail when there's an array containing only negative numbers. In this scenario, the result should be the max number in the array, but your solution will return 0

If all the elements are negative then how we get max subArray

Initially, I confidently declared, "I don't even need a pen and paper to solve it in O(n) time." But as I struggled, scratching my head in confusion, I eventually found myself here, seeking assistance and realizing that maybe a pen and paper wouldn't have been such a bad idea after all.

What happens that the all the array is negative?

Would this be considered sliding window?

will this work if all the elements are negative?

Can't you just set the curSum to the current number if maxSub < curSum?

neetcode please return making videos with this keyboard.. I really get relaxed from this. Even if I solved this, I see the typing part! :>

Hi, i was just thinking about it, but if all numbers are negative, wont your answer be returning 0, which is not inside the array?

@mowww20

Жыл бұрын

No, it will return the biggest numbers in the array.

@owenwu7995

Жыл бұрын

@@mowww20 Then why are we setting currentsum to 0 if it's less than 0?

@ashbywoulds

9 ай бұрын

@owenwu7995 Setting currentSum to 0 is to reset where the sub array starts. maxSub is always going to return the bigger of the two sub arrays (current biggest total vs newest total)

What if the maximum is a negative number ?

is it possible the max sum is negative?

Could you please make a video for the leetcode 1335?

why brute force is n^3 ?. It looks with n^2 , we can solve it. Can you explain why ?

@amazing-graceolutomilayo5041

2 жыл бұрын

You want your problems solved with the lowest time complexity and in the video, he achieved n^1

great work

Thanks a lot sir :)

Thanks for the explanation :D What if we wanted to create a subarray of the maximum? so in your example it would output [4, -1, 2, 1]

Can you make a video for 163. Missing Ranges.. Your videos have been succinct and very helpful.

Can you show the DP way of solving this?

They've asked for the divide and conquer approach, can u give that solution ?

high quality content

what about if all elements are negative?

The question says to try 'divide and conquer'?

How to slice that exact subarray???

why are negative values ignored? what if all the elements are negatives? that case you have to find minimum negative number right? somebody answer this.

@rafaelbnn

2 ай бұрын

You're right, if all the elements are negative the answer will be the greatest negative. Lines 7 and 8 clear the curSum everytime so that we don't add up more than one negative number, and then we 'reinitialize' curSum with the current value, and check if it's bigger than the one we have. I agree that this is a pretty neat way to do it. If I had come up with the solution by myself I would never had thought of something so elegant

I think starting current with 0 is wrong. Apparently this is not in the test cases but the array could be [-3, -2, -1] so max sub array would be -1. I say we should compare the current subarray with the current number instead of 0, like so; def maxSubArray(self, nums: List[int]) -> int: maximum = current = nums[0] for i in range(1, len(nums)): current = max(current+nums[i], nums[i]) maximum = max(maximum, current) return maximum

@vinhnghiang1273

Жыл бұрын

I agree

@HanSmellsGood

Жыл бұрын

the answer would still be -1 because after current is set to 0, it still performs += num which for e.g is -1, hence when perform max(max, current), -1 would still be the result

this is like a DP question

I don't think we should remove the negative as we might have an array of negative numbers

@alexkarydis2270

9 ай бұрын

I thought the same and struggled with it that's why I came here. Reality is that from an array of negative numbers you should pick the largest of those numbers as your largest sum. The solution sets the current sum to zero if it's negative but then adds the current number (which is negative) to the current sum (which is zero) and compares it to the largest sum. So the largest number out of those negative numbers gets selected eventually.

what if all the items are negative ?

Why are you making curSum =0, because max sum can be negative also right?

Thanks!!!

Lovely solution but as others have pointed out, this fails the leetcode 53 test suite because that has things like [-2, -1] as test patterns whereas by resetting to 0 constantly it won't work for those.

Will this work if array does not have any +ve number in them ?

@chiamakabrowneyes

2 жыл бұрын

That's a great question. I had to go back at the algorithm to check. I don't know if this is my place to respond, but I don't think that it would work, because it initializes the current sum value to 0.

@sachinshaji92

2 жыл бұрын

For the code to work in any scenario(All Negative,All Positive,Mix) make this change: for n in nums: if curSum curSum= n