วีดีโอ

You have to know what 3 pointer is useful for as opposed to 2 pointer. You can do all sliding window problems with 3 pointers, just usually the third one is redundant and doesn't give any extra information. So once you get how the third one helps, you can start asking yourself do I need it when you do the problems or do 2 give me all the info I need.

@@Alpha-Code Thanks! I will try to delve in into how the third pointer is redundant in most cases but useful in this one. I just have one more question though and this is sth that I have been stuck when dealing with this problem - why is res += (min(lastMin, lastMax) - start + 1)? I don’t quite understand how come sth like (r-l+1) could be the number of subarray to add. How come in this formula we can find the number of subarray that fulfill the condition of the fixed bound? Sorry if this seems a little bit confusing, but I am quite lost about how this formula actually applies. Is there a mathematical way to think about this? And possibly how to apply this in other questions (e.g the scenario)?

@@victor-fo9zf (min(lastMin, lastMax) - l + 1) is used cause you have to include lastMin and lastMax in all valid arrays so you take the min as this is the smallest array that includes both. Then anything that starts from there to start is a valid subarray if they end with r. And r - l + 1 is cause the number of arrays between 2 indices is r - l + 1.

You're supposed to combine (add or subtract) fractions. Ex: 1/3 + 1/3 = 2/3

Yeah I can spend more time on that sure. Thought this one was pretty clear just add fractions and simplify answer. But I'll spend more time on problem descriptions in the future no worries.

for that one you look for all characters that match starting one so abaa matches which would go down to aba then that goes down to ab for 0 cost. I explained something similar in the updated video for this problem.

@@Alpha-Code You're absolutely right! Thank you. The reason I couldn't figure it out was that I was building the decision tree incorrectly. If anyone else has the same question I did, try building a decision tree using a simple example.

in line 27, it's recursing to the next character from the front. From i, j to i+1, j where i is front and j is end. Can do backwards or forwards should be the same so forwards just seems more intuitive if it doesn't matter.

@@Alpha-Code I meant, the line 27 will be executed to the end of the string when i and j are same so you actually split the string from at the end of it. Am I wrong?

@@MehmetDemir-xi3yy You can split from front or end but in this case it splits from front, you can log i and j and see for yourself though.

@@Alpha-Code for input "abcabc" when you add this line below to line 30, "System.out.println(s.substring(i, k+1));" you will get output as cabc bcab abca so you are doing from backward to forward

@@MehmetDemir-xi3yy Put that line at the top of the dp and just print i and j. Here's what I got for "abcabc" but either way result should be same imgur.com/IBOM5hR

@@vishaalkumaranandan2894 th-cam.com/video/uAraW9iGmRQ/w-d-xo.htmlsi=ML0XFaIiQeUmB7jf new one with dark mode

Yeah I mostly write the code live. This one wasn't too long so probably could have done it. For the long ones, I prefer to write it ahead of time so the videos aren't like 30+ min.

The idea is in our function we are never calculating Bob's score. On Bob's turn we are simply returning the minimum for Alice given all the moves Bob can make. And on Alice's turn we are returning the maximum for Alice given all the moves that she can make. The function returns Alice's score given they both play optimally without calculating Bob's score at all, because the less points Alice gets the more Bob gets. So we can just focus on 1 score. So for example 2 you are referring to, the optimal play is Alice takes pile 1, Bob takes pile 2, Alice takes pile 3, Bob takes piles 4 and 5, and Alice takes pile 6. Alice's score is 1 + 3 + 100 from that = 104.

@@Alpha-Code thank bro got it

You should do easier dp problems until you can create your own solutions then once you can do easier ones yourself consistently try slowly increasing difficulty. Start with some really basic ones where you have some basic choices to make like go down or right or something. Then go to mediums then go to hards.

excalidraw

@@Alpha-Code Thank you!

Haven't done contests this week. If I do them later on during the week, I'll post them.

Sound is fine for me is there anything in particular I can improve?

You have to recognize what is the same between 2 boxes that are next to each other. That's usually the key to these tricky DP problems, try to think of which dimension you can simplify in some way after coming up with the brute force dp solution. You have to go through every square so it has to be the checking the whole row for every box that has to be simplified Then try to figure out how that's possible. You can try coding up the easy DP solution then look at it and see how you are calculating each thing and the similarities. Might help to actually do a dry run of that just like I did in the picture and then spot the similar values and find a way to avoid recalculations.

Thanks

@@Alpha-Code when you go about hard problems do you just immediately recognize what algorithms to use and then work out the details or does it take a while to think of it

@@CheeseFest- Depends on the difficulty. Some are too hard to figure it out right away, like some LeetCode contest problems are solved in 15-20 min by the winner so they would take me an hour+ probably. Some hards are closer to a medium. Looking at the constraints right away helps to eliminate things though, then you can think what is usable from what is left. Like for this problem you can see that you need nlogn or better so can eliminate n^2 solutions right away. Then also recognizing patterns you've seen before helps, like this type of problem is one I've seen before where you can't calculate all the values but you can binary search. I've done this one before which is the same idea leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/ and a few others like it.

subbed !

Glad to hear it. If I miss anything or there's some improvement that cant be made, just let me know.

It had to be a square to keep the same connections for one. Can't have 2x2 because of the example I showed here th-cam.com/video/8Rgz15cpTts/w-d-xo.html . 3x3 is the smallest that lets you connect everything by not going diagonally. Maybe 2x2 is doable with more checks I guess but you'd have to go diagonally and have more checks. And I think anything bigger than 3x3 also works, just 3x3 is the smallest.

Same here 😅

​@@fairoossahfeerulwasihf1139 we only store the result which is row * col and everything else is constant space but result doesn't count for space complexity since we always need it.

Thanks, glad you liked it.

It's basically just you always move x steps in a straight line where x is increasing by 1 every 2 times you change direction. And you are out of bounds a lot so just record only when you are in bounds. And directions go in a right -> down -> left -> up -> right loop. Maybe try doing some of the earlier spiral matrix problems first if you don't get this one.