Maximum Score of a Good Subarray - Leetcode 1793 - Python

[@plsgivemecat]

4:23
"Does it really matter how big this boy is, if we have a small value here - It really doesn't"
Thank you Neetcode for assuring me that size doesn't matter :')

[@ianpeng7518]

Wow you make the hard problem to the medium level :O

[@gmh14]

lol I was trying to do a sliding window with a recursive decision tree with transitions slide, expand, shrink which I even tabulated but it was leading to TLE after 33 test cases

[@the_witcherr275]

Thanks a lot Navdeep for this great explanation👍

[@jonaskhanwald566]

Just added -inf to avoid the left and right pointers going out of bound
a.append(-inf)
a.insert(0,-inf)
l = r = k+1
res = leftMin = rightMin = a[k+1]
for i in range(len(a)):
rightMin = min(rightMin,a[r+1])
leftMin = min(leftMin,a[l-1])
if rightMin > leftMin:
r+=1
res = max(res,rightMin*(r-l+1))
else:
l-=1
res = max(res,leftMin*(r-l+1))
return res

[@space_ace7710]

Thanks

[@devkumar9889]

We can start from end also , for finding minimum we can use segment tree now

[@MP-ny3ep]

Thank you . Another great explanation as always!

[@bikkisneha8090]

Why are we checking for left > right (line 10) ? How does it matter how big the number is ?

[@dingus2332]

Why my same approach Implementation Gave TLE ?
l = r = k

while l >=0 and r nums[r+1]:
l -= 1
else :
r += 1

return res

[@dingus2332]

Ok I am dumb , I used , min function in cur_score , thats why it gave TLE , huh

[@S3aw0lf]

@dingus2332 🤣we all become dumb while coding sometimes i feel

[@dingus2332]

@@S3aw0lf Yeah man , specially in hard problems . Its like I have a skill to come up with best approach and executing it with least efficient way

[@S3aw0lf]

@@dingus2332 can relate 🤧

[@wanfuse]

what itf 1 was like 1 less than k? and second 1 from left was the same? I assume its because you might not return the optimal value ( the greedy value instead?)

[@divyagracie]

Java code:
class Solution {
public int maximumScore(int[] nums, int k) {
//start at k
int l = k;
int r = k;
int curMin = nums[k]; //length 1 subarray that contains index k
int res = curMin;

while(l > 0 || r < nums.length - 1) { //since we go -1 on l and + 1 on right.
int left = l > 0 ? nums[l - 1] : 0; //0 since nums contains +ves only
int right = r < nums.length - 1? nums[r + 1] : 0;
//pick larger element
if(left > right) {
l --;
curMin = Math.min(curMin, left);
} else {
r ++;
curMin = Math.min(curMin, right);
}
res = Math.max(res, curMin * (r - l + 1));
}
return res;
}
}

[@wrishavbhattacharyya5216]

i have an interview coming up and i was upsolving it after 45 mins of beating my head . And when he said its a "medium problem btw " , my heart sank :(

[@tuandino6990]

I used monotonic stack for this problem

[@ameyakale6334]

At 4:26 you mentioned that our bottleneck is always going to be the minimum value. Can you please explain this to me? I am having a hard time understanding it.

[@NeetCodeIO]

Mainly because we calculate the score using the minimum value in the subarray.

[@kareemadesola6522]

Thanks for doing it early on

[@DEEPAKKUMAR-xe2vb]

Kindly post sunday leetcode contest solution also, It would be helpful. BTW thanks a lot.

[@pastori2672]

does recursion work here ?

[@cinimodmil]

Damn.. you made it look so easy..

[@rheemk1980]

HI NEETCODE HOW ARE YOU I HOPE YOU ARE WELL

[@vixguy]

I solved this completely on my own! I'm proud :)

[@zzzzzzzjsjyue2175]

it should be an easy lol

[@vixguy]

@@zzzzzzzjsjyue2175 are you trying to bring me down?

[@zzzzzzzjsjyue2175]

@@vixguy nah mb

[@vixguy]

@@zzzzzzzjsjyue2175

[@akshaymulgund4947]

Tears in my eyes navdeep

[@zzzzzzzjsjyue2175]

This should be easy lmao how is this hard rated