Maximum Score of a Good Subarray - Leetcode 1793 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:14 - Coding Explanation

leetcode 1793

#neetcode #leetcode #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 :')

[ianpeng]

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

[gmh]

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_witcherr]

Thanks a lot Navdeep for this great explanation👍

[jonaskhanwald]

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

[devkumar]

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

[MP-nyep]

Thank you . Another great explanation as always!

[bikkisneha]

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

[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;

}
}

[tuandino]

I used monotonic stack for this problem

[dingus]

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

while l >=0 and r <= len(nums) - 1 :
cur_score = min(nums[l:r+1]) * (r - l + 1)
res = max(res, cur_score)
if l == 0 :
r += 1
elif r == len(nums) -1 :
l -= 1
elif nums[l-1] > nums[r+1]:
l -= 1
else :
r += 1

return res

[DEEPAKKUMAR-xevb]

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

[wrishavbhattacharyya]

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

[ameyakale]

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.

[vixguy]

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

[rheemk]

HI NEETCODE HOW ARE YOU I HOPE YOU ARE WELL

[zzzzzzzjsjyue]

This should be easy lmao how is this hard rated