Maximum Value at a Given Index in a Bounded Array | Leetcode - 1802

Join this channel to get access to perks:

To support us you can donate

Check out our other popular playlists:
Questions you might like:

If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful.

#coding #leetcode #programminglife #programmingisfun #programmer #tech #software #codinglife #leetcode

[MGtvMusic]

The nums[i] is a positive integer where i is 0 to <n is not incorrect,
It doesn't talk about nums[i] being in that range but just means that it is in the index range of 0 to n-1

[sakarmichel]

Hi,

Thank you for taking the time to make this detail video!
You have put in a lot of work in making this video and that deserves praise.
I am having a hard time understand how the division operator is use to calculate the remaining increment.
Is it possible you can provide another example of how to calculate the remaining increment with the division operator please?
Timestamp 13:12

Never Give Up,

[Prem_Parmar]

TLE Step approach:

class Solution {
public int maxValue(int n, int index, int maxSum) {

int maxLeft = index;
int maxRight = n - index - 1;

int sum = n;
int maxIndexValue = 1;

for (int i = 1; sum < maxSum ;i++) {
maxIndexValue++; sum++;
sum += (maxLeft - i > 0 ? i : maxLeft);
sum += (maxRight - i > 0 ? i : maxRight);
}

return maxIndexValue;

}
}

[netanelkomm]

Thank you, you helped me a lot.
I got the unoptimized solution before watching your video and was going insane about the TLE and didn't know how to improve it :P

[Aryan]

python equivalent O(n)

def maxValue(self, n: int, index: int, maxSum: int) -> int:
value = 1
maxSum -= n # initalize array by 1
left, right = 0, 0
leftMax = index # length of subarray to the left of index
rightMax = n - index - 1

while maxSum > 0 :
value += 1
leftVal = min(left, leftMax) # [1, 2, 2, 1]
rightVal = min(right, rightMax)
left += 1
right += 1

maxSum -= (1 + leftVal + rightVal)

if leftVal == leftMax and rightVal == rightMax:
break

if maxSum > 0:
value += maxSum // n

return value-1 if maxSum < 0 else value