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 :')
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
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
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?)
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; } }
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 :(
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.
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 :')
Wow you make the hard problem to the medium level :O
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
Thanks a lot Navdeep for this great explanation👍
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
Thanks
We can start from end also , for finding minimum we can use segment tree now
Thank you . Another great explanation as always!
Why are we checking for left > right (line 10) ? How does it matter how big the number is ?
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
Ok I am dumb , I used , min function in cur_score , thats why it gave TLE , huh
@dingus2332 🤣we all become dumb while coding sometimes i feel
@@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
@@dingus2332 can relate 🤧
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?)
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;
}
}
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 :(
I used monotonic stack for this problem
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.
Mainly because we calculate the score using the minimum value in the subarray.
Thanks for doing it early on
Kindly post sunday leetcode contest solution also, It would be helpful. BTW thanks a lot.
does recursion work here ?
Damn.. you made it look so easy..
HI NEETCODE HOW ARE YOU I HOPE YOU ARE WELL
I solved this completely on my own! I'm proud :)
it should be an easy lol
@@zzzzzzzjsjyue2175 are you trying to bring me down?
@@vixguy nah mb
@@zzzzzzzjsjyue2175
Tears in my eyes navdeep
This should be easy lmao how is this hard rated