LeetCode Challenge Day 3 - Max Subarray

Max Subarray and Kadane's algorithm. You should already know this if you prepare for coding interviews. Make sure to check out an alternative solution at 7:05 though!
Leetcode holds a 30-day Challenge in April with a new coding interview problem appearing each day. I'm participating and will upload a video for each day just after the deadline at midnight PST. Participate here leetcode.com/explore/featured...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming

[@Errichto]

Today is Google Code Jam qualification round! codingcompetitions.withgoogle.com/codejam Also, I should have just used a=max(x,a+x).

[@iitnakanpur..]

@Errichto congrats you got 2nd in qualification round, And iam still try to find bug in my first problem😅😅😅

[@rahulbhatia1313]

😂😂😂

[@iitnakanpur..]

@@wanderer1603 this is not the way of doing any competition, so please try it your own, and if you still stuck then I can help you

[@FoodieKing]

@@iitnakanpur.. I am done with the the first problem of codejam

[@iitnakanpur..]

@@FoodieKing bro it's awkward to say but IAM still stuck at first problem , my code is just failing in last test case don't know why, Can you help

[@ritiktwopointo2691]

Errichto, I dont know if anyone has noticed but you have got an unknown side of a good sense of humor. Also, thank you so very much for helping hundreds of thousands of guys out there. Keep up the good work

[@cobrandrewg9995]

* gets 2 nd place in codejam qualifiers* "Ok that was boring, let's make a KZbin video now"

[@gamarayburst1258]

lol, it's just qualifiers. Wait till final where our gennedy boi will be first and this boi will be 2nd.

[@iitnakanpur..]

@@gamarayburst1258 but I didn't see gennady in qualification round. Is it not participating

[@Errichto]

@@iitnakanpur.. It was 3am in Russia and Belarus when the competition started. It's healthier to sleep and then participate during a day ;)

[@iitnakanpur..]

@@Errichto oh that's the reason, although gennady is not participating it is not possible since he is winning from last 6 years😂😂

[@almuhimen8023]

@@iitnakanpur.. Gennedy is already in the final

[@pratikchandraIC]

who didn't know about Kadane's algorithm ? ✋ (me)

[@chitranshsaxena59]

so, not a single person, lol

[@Tanvir-xw8rc]

I didn't know also

[@sauravpaul4131]

So you are married or committed? 🤣 Cz every single person know it

[@camenraidercc6625]

Don't stop with this series I'm learning so much!!!

[@subarukun8001]

3:17 the question that comes on my mind while I solve new problems.

[@TwitchCronos100]

me on every problem

[@jitendraraghuwanshi1365]

always

[@AidenBai]

damn, that fingercrack really got me

[@FromTheMountain]

I got this exact problem as a homework question recently, spent hours on it until I finally came up with this algorithm. Little did I know, it was one of the most well known programming interview questions...

[@rickyleung9312]

Makes me smile when I see the missing “int a = 0” after the amazing quick modification to handle the negative numbers.

[@Shounak2411]

Dude, great videos. I like that you mess up sometimes. It helps me, as a viewer who doesn't participate in competitions, to keep in mind that it is not necessary to get the code correct in the first try . You try and figure out what is wrong and correct it. And when you get it right, it's great. So thanks and best of luck for your future.

[@Errichto]

Thanks :)

[@rockyjoe3817]

Amazing Errichto Just Amazing . One of the best things is to learn how smart people think when solving problems!!!!!!

[@jimwoodward7293]

"In this episode of Errichto complains ...." -- these videos are great!! This basically boils down to a typing exercise for you!

[@lovvyparhar393]

If you don't know the algorithm then read the book mentioned by Errichto in the beginner cp video, it is great! We can alternately keep the first element in the ans and then use loop from i = 1 to n and apply the kadane's algorithm, it will also work.

[@rockyjoe3817]

Ah do you know the name of the book?

[@lovvyparhar393]

@@rockyjoe3817 Competitive Programming Handbook by A Laaksonen

[@rockyjoe3817]

@@lovvyparhar393 THANKS :DDDDD

[@aayushlamichhane]

i laughed too hard when he said "am i stupid or something"

[@flyingcanopy5611]

Your explanation is so effortless . Easy to understand ..

[@codearabawy]

Thanks, Errichto! That was an informative video for me.

[@walthertrgovac6087]

Please continue to explain how to do the tasks and what you did because that is why we are watching. If I knew what Kadane's algorithm is, I wouldn't be here lol

[@junghoryu850]

I solved three problems in google Code Jam so far and I saw you as top two! You are so good!

[@FoodieKing]

Please connect wid me...

[@videocorner3305]

Bro is Codejam submission is over It's showing me an option to submit the solution Im confused Can u please confirm this

[@colios137]

@@videocorner3305 no codejam is not over u can submit your code!

[@junghoryu850]

@@FoodieKing Sorry I went to sleep afterwards... I'm from Toronto so the time zone difference

[@starllama2149]

@@junghoryu850 don't give away your location so freely man

[@imml97]

Well you are a genius, and I can certainly say so as I've never seen someone code it twice and under 20s and then saying "Well the problem statement is". 🙌

[@sarahb5340]

This is like the speedcubers who plan the entire solution before making their first move.

[@olayinkaanifowose5099]

first time seeing this, proud of myself that i was able to come up with the alternative prefix sum algorithm within minutes. Never heard of kadane's algorithm before.

[@shubhamk840]

It's great to see errichto getting more confident video by video.

[@siddvideos]

Thanks @Errichto, excellent explanation.

[@vaibhavsingh3550]

Please explain codejam qualifying problems also especially the last two once. It would be really helpful.

[@stonecoldcold2941]

Awesome Man , keep up the good work!

[@Aditya-us5gj]

Hey Errichto, In the last line question it was written that if you know O(n) solution then try to target divide and conquer strategy. Whereas if I'm not wrong, kadane's algorithm falls in DP category. Can you suggest any divide and conquer strategy for the same question ?

[@Errichto]

Divide&Conquer boils down to finding the best interval that passes through the middle of a sequence. Go from the middle to the left and find the biggest sum (of suffix of left half), same when going from the middle to the right (biggest sum of prefix of right half), and add those two numbers.

[@erikawwad7653]

Thanks for educating me, the single person!!

[@ascyrax8507]

u rock Kamil!!!!Big fan of yours.

[@CREATORSPVTLTD]

can someone help me out in the Parenting Partnering Returns question, Explanations or Hints or Tricks would be great : (

[@sum5619]

Dang it errichto, I was hoping you could've explained the follow up question for divide and conquer. I did it before but coming back to it I lost all understanding of what I did...

[@siddharth_singh9]

@Errichto do you think solving the indicium program using magic square algorithm is correct ??

[@arinroday302]

You really do have a good sense of humour

[@shashankdubey983]

erichto Is there any way that while finding all the subsequences of an array,we can seprate all subarrays from subsequences at the same time??

[@almuhimen8023]

Thats gonna take way lot time and gice you a TLE

[@akashdubey8341]

Sir will you please make video tutorials of hackerearth circuit problems.

[@anashashim]

Could you make a video about HashCode and how can a team prepare for it?

[@diveshchowdary2124]

will you make a video which will explain your template for cpp

[@pulakmalhotra5816]

What is the divide and conquer approach as mentioned in the problem statement?

[@silverzero9524]

i clicked this video for exactly that :(

[@_Ani_]

"Measure myself" - instantly corrects xD

[@_Ani_]

Day 4 solution : class Solution { public: void moveZeroes(vector& nums) { int c=0; for (int i = 0; i < nums.size() ; i++) if (nums[i] != 0) swap(nums[c++], nums[i]); } };

[@ramaranneh]

Hi... can anyone explain me the different between the first line he wrote a =max(0,a+x) and the two lines he wrote instead a+=x; a=max(a,0); thanks in advance

[@abhishek_k_jha]

Will you post explained solution of code jam tomorrow??

[@DiAd188]

why do I have adrenaline rush before you start hahahhahahah :'D

[@i_vikassharma]

could you please tell which timer program are you using to track the time in this video?

[@tanishqupadhayay1350]

I am that single person who hasn't heard about this algo / So thanks Errichto! keep this up

[@munkh-odganzorigt7497]

him: hello my fellow programmers me: hello god

[@davidjojic6772]

I started reading Competitive Programmer's Handbook and and i got stuck when Backtracking came, after that came some a lot of difficult chapters that i did not understand. Do i continue reading the book if i dont understand. I started doing task from Codeforces. PS. I love your videos

[@Errichto]

Maybe practice some problems now and get better understanding of them. Once you are good at easy problems, move on to harder topics. Imagine just reading a big math book without solving many problems. You will be lost in the middle without a good grasp of what happened earlier.

[@prakash_77]

I think Erricto said to maintain balance reading the book and practicing, not merely reading the book and/or implementing. Getting stuck is normal. Don't move forward. Maybe practice some problems on Backtracking itself.

[@shashanktiwari4442]

Pls also post the video of codejam qualification after it ends thx

[@christianantonyquero6642]

Is there any tutorial on how Errichto cracks his hands?

[@rakesht.j664]

Hey man can u make a video how to think and solve these kinds of problems.......

[@chauhan1999]

What's the name of that Timer app? Is it Google timer if yes how did you pin it because I can open it only in one tab in windows.

[@osamaataullah3723]

I stuck in codejam 3rd problem can any1 help plz?

[@shreyanshsingh2627]

0:02 -- You haven't trained enough for CP today if you hands don't crack like that when you leave the keyboard

[@jameshello38]

Errichto is getting better every video. May be he implemented neural network.

[@brianhuang9257]

What is the divide and conquer solution?

[@prasoonsingh533]

Brian Huang in this we will use divide and conquer approach By dividing the array in two equal halves

[@hacker-7214]

you are a code jam champion. it took me whole day to solve 2 problems and i got stuck on problem 3. the overlapping interval. i gave up lol. im now 20k in the leaderboard :( XD

[@satviknema8629]

This guy stood second in Google code jam today. GG

[@md.romizulislam7416]

wat a start :')

[@UdayKiran-mw4cr]

Which software are you using for the timer(The one which is under your picture in video) ? I would like to try my timings

[@PravinMali]

What is the timer app or extension that you used in the video?

[@Errichto]

I googled stopwatch and it was there. Some google/chrome tool.

[@tkctko]

I didn't know there are a couple of solutions. I knew only divide and conquer approach.

[@UnfunnyXavier]

I saw similar problem but a bit more to it, it was like you have to find maximum subarray but the array element are treated as circular i.e if array is [ 7,-1,2,-11,4,7,-1] then the maximum sum is 18 from i=4 to i=2 can you help in that case plz

[@shashwatkhanna6036]

Let's say we have an array [1,2,3] Make another array [1,2,3,1,2,3] and then solve it like you normally would. There's probably a better way, but this seems like the simplest. Or you could run a loop from 0 to 2n and access the array as a[i%n]

[@UnfunnyXavier]

@@shashwatkhanna6036 but the answer of your example will be 12 while max sum from orignal array was 6

[@samgal9205]

@@UnfunnyXavier In addition to finding internal max subarray like here, you can find two max sums while being pinned to left and right most elements. You can do that in two passes, one forward and one reverse. Then you take max of internal or left+right

[@twrskshm]

If its an empty array, the for loop will not be entered and the function will return the value of INT_MIN

[@BarkaDog]

It cannot be an empty array it's clearly written in the question

[@vikashkumandan]

I also followed the same logic as kadane’s algo without knowing it but my code was 25 lines long .. not 5 and i took time about 15-20 mins to complete my code and submit 😂 do you have any tips on how we can reduce lines of code or steps to follow to keep reducing our code to be much readable

[@Errichto]

idk, see for repeated parts and extract them?

[@vikashkumandan]

Yaa i will check now and remove as much as possible by me 😊

[@jenniefine9456]

You are the only one CP KZbinr which i like 🥰

[@askaraskar1472]

Like smash before watching!

[@syeda.k.2934]

difficult to watch on small screen, pls increase resolution or zoom in.

[@sahilsharma2952]

Errichto Do you have a discord server?

[@TheJack2HD]

Google jam video when contest is over plz :D

[@sufyan2317]

And yes congo !!!!!!!!!!!! 2nd place in code jam ... i managed to solve first 4 ...feeling exhausted😂😂

[@prakash_77]

Were they easy?

[@sufyan2317]

@@prakash_77 first 3 were easy!!!!!!

[@Anto-xh5vn]

I am that one person who doesn't know kadane's algorithm :D Thanks tor explaining

[@limakbear7029]

Kadane's Algorithm 😀

[@Anto-xh5vn]

@@limakbear7029 ooh thanks for correcting me mate

[@mr.mystiks9968]

I was hoping the alternative solution would be a divide and conquer recursive solution :(

[@r0l3ex20]

When you are typing you hold your fingers in "Home Row Position"?

[@akashdubey8341]

i think everybody does that!!!!!!!!

[@Errichto]

I don't know what that is. Do I keep fingers on second row of keyboard (ASDFJKL:)? Yes

[@shresthmishra9329]

hahahahahahhahahaa nice start.i wonder how many retakes you took for that

[@saurabhmittal2145]

Hi Errichto in this problem there is follow up that we can do it in O(log(n)) but you have done it in O(n) which tell us more efficient solution.

[@Errichto]

The follow-up is slower O(n*log(n)) approach. You can't do anything faster than O(n) because you need to go through the whole array at least once to know the sum of possibly all elements.

[@saurabhmittal2145]

@@Errichtook Thank you so much sir.

[@danylopolishchuk1748]

That finger cracking .That shit scares me

[@kevintlu]

"Am I stupid or something", oh boy

[@danielsegura1568]

where are you from? you sound like my ex from serbia , easter european? just curious

[@rakeshhotker4762]

Thanks

[@mahdi7d1rostami]

The sound in the beginning...! Was it real?

[@Errichto]

Yes, it was :>

[@travissun6753]

kzbin.info/www/bejne/q57XaKdnlL1riMU When you explain the algorithm, what drawing board software are you using?

[@Yogesh-bp4vv]

😍When you are beginner, how much time you take to solve problem because now i take 20-30min or sometimes 1hr to solve a problem please aanswer.

[@Errichto]

Depends on how difficult problems you're solving... can be 3 minutes, can be 3 hours.

[@Yogesh-bp4vv]

@@Errichtoso it means you also take 3hour to solve a problem sometimes. I thought I was the only one. Who takes sometime 2-3 hours to solve a problem. Thank you😍

[@electromorphous9567]

They still have a month. They're starting off with easy problems which will get hard towards the end.

[@Errichto]

I'm not complaining about the difficulty. The style of problems is bad, they are bad for beginners.

[@almuhimen8023]

I solved it faster than you. How? I solved it yesterday!🤣

[@abdelrahmanadel8998]

😂😂

[@kakatuaOfficial]

Off Topic: I solved the first problem in Codejam 2020 in exactly 1 hour. The same time than Errichto... for all the problems.

[@shahanahmed952]

That's impressive! How long have you been coding?

[@kakatuaOfficial]

@@shahanahmed952 you should read the hidden comment. Errichto solved all the problems in 1 hour.

[@shahanahmed952]

@@kakatuaOfficial Lmao did not notice that,Thanks mate.😅🤣

[@BianLee]

Great video but could u put face cam bottom left corner so we can read question better?

[@Errichto]

Damn, sorry about that. I will be more careful next time.

[@gamarayburst1258]

*How one can achieve speed like you in logic building? It seems you have a gift from God.*

[@alexwindy3]

He has been doing this for years and years...its like driving a car, he knows the streets by now.

[@Errichto]

Practice.

[@Phsoco]

I think his process before even looking at the question gives you some insight there. He has done so many of these type of questions that he was predicting what it would be, so when the question appeared on the screen all he needed was a few key words and could immediately start typing. After doing a lot of practice you can take a cursory glance at a question and know what they are going to ask. This applies to everything, not just coding.

[@parthbhatia341]

Is leetcode enough for interviews or do i have to do competetive programming.

[@Errichto]

You don't have to do CP for coding interviews. Leetcode is enough.

[@Mrwiseguy101690]

When you can't answer a hard leetcode problem in -5 seconds: 3:17

[@FitnessChaos]

ayoooo what the fuck in the beginning lmfaooo

[@tsatsralt9112]

you are the beST!

[@anupamnerbheram7464]

Just by watching him doing Codding my IQ shoots up twice before.

[@andrewfischer-garbutt2867]

I did this problem without knowing the algorithm in the video. My solution took more than 100 lines of code.

[@Errichto]

And this is why I said this is not a problem. Easy for half of people (because they know it), very hard for others.

[@hacker-7214]

lmaooooo

[@limakbear7029]

7:05 for me :p

[@pyak6761]

i didnt kno kadanes algorithm. but thats like my entire interviewing life. fffff

[@sahil3735]

Hello sir, can you suggest how is CLRS introduction to algorithm book.

[@amanpratapsingh1243]

Bible

[@sahil3735]

@@amanpratapsingh1243 have you used it?

[@Aditya-us5gj]

Well said Aman.

[@Aditya-us5gj]

Yes Sahil ! It is bible. Will test every corner of your brain. If you complete that book properly, then you can say you've mastered DS and Algorithms along with high knowledge of mathematics.

[@manavmohata1240]

You need good math skills to go through that book

[@missilemahmood]

10:52 Did he just say "daal bhat"? 🤣 He must have learned it from some Bangladeshi friend of his.

[@limakbear7029]

See caption., it's done, but

[@LiangyueLi]

Thanks Errichto, could you use python for the demo? just wondering.

[@Errichto]

so far solutions are quite basic and I think everything is understandable for any programmer. I don't want to use Python because I risk doing something wrong and teaching you something incorrect.

[@LiangyueLi]

@@Errichto Thanks Errichto, that makes sense. But if I want to participate in competitive programming like you mentioned in the other video, I should learn C++, right?

[@richardj.rustleshyman2026]

Zzzzzzzzzzzzz I was trying this without looking at the solution and after hours of smashing my head, I ended up with a triple-nested for loop method that wasn't even working properly Fml

[@Gregory.Pacheco]

This solution beats 95% of the other solutions: max_current, max_global = a[0], a[0] for i in range(1, len(a)): max_current = max(a[i], max_current + a[i]) max_global = max(max_current, max_global) return max_global

[@srivatsanraghavan5996]

PLEASE MAKE A DAY IN LIFE. YOU WIL GET A MILLION VIEW

[@saibhargavaramu5749]

me all this time .. ka-da-ne