LeetCode 1802. Maximum Value at a Given Index in a Bounded Array | Weekly Contest 233 🏆 | Explained

A very nice problem using binary search. Here you yourself have to set a particular value for index and then validate the conditions.
I have realised this concept is asked in a lot of good coding problems. So keep this method in your mind/ arsenal to solve problems.

Connect with me at

1 Like = motivation
1 Subscribe = more motivation :)
SUBSCRIBE guys ...

Thanks for watching friends.
Please like and share with your friends it will give me motivation to make further videos.

[stevenchung]

The table with the fixed max value was really helpful to visualize why binary search is core to this. Thanks for this!

[Silverrrrr]

These video solutions are much better than the written ones. I tried this for myself for about 1-2 hours and understood that it has to be some kind of binary search thing but I could not recall the formula n*(n+1) / 2. Now I understand this well, thanks

[bharath]

Thanks I was facing dfficulty figuring out the left and right sums. You did it in a very lucid manner.

[jacklo]

good explanation, but I have some question:
how about 1, 2, 2, 1, like the input is 4, 2, 6
It looks like that it won't consider duplicating 2 in the left side. But it will just return the closest res
How could you prove that we don't need to consider that?

[avneet]

Such a nice solution. I just couldn't think of arranging it in that 2D array kinda thing even though I was thinking about that approach. Many other nice tricks too.

[SurajKumar-bwoi]

Thanks for making a video on this one!
Your maths way of checking is easy-to-understand as compared to what written on leetcode discussion forums.
Liked & Subscribed :)

[rusty-coder]

Thank you very much sir, your explanation is fantastic.

[madetolaugh]

I have been coding for almost 3 months now but i am not able to come up with an optimal approach to solve the problem on leetcode. What should I do ?

[gangadharmatta]

Bro..Never bother about Video length..your way of explanation is excellent❤

[deepanshuacademics]

Sir How are you returning a long to int?

[harshpratapsingh]

I was also trying to solve like this only but i was not able to find a generic way to calculate rightSum and leftSum😅😅

[shirinjulka]

For the test case: n = 6, index = 1, maxSum = 10
Could you explain how the leftsum is calculated?
How does l in the formula ls=(m*(m+1))/2 -((m-l)*(m-l+1))/2; work?

[amarelswtor]

Fantastic solution and great explanation! Subscribed!

[SuperShank]

nice. but we need to prove that when you set value at index to maxSum, it is sufficient to decrement by 1 on either side of index. You could also keep the same number on either side of index since abs(nums[i]-nums[i+1]) <= 1? Why reuse the number 1 only at the left and right ends?

[aadil]

const mid = left + Math.floor((right - left)/2);
I'm calculating the mid like so in js.
for some reason it gives TLE. Can you explain why?

here's the entire code:
var maxValue = function(n, index, maxSum) {

const getSum = (val) => {
// calc the left side
let count = 0;

if(val > index) {
count += (val + (val - index)) * ((index + 1)/2);
} else {
const ones = (index + 1 - val);
count += ones + (val + 1) * (val)/2;
}

// for right
if(val > n - index) {
count += (val + (val - (n - 1 - index))) * (n-index)/2;
} else {
const ones = (n - index) - val;
count += ones + (val + 1) * (val/2);
}

return count - val; // because we have counted val twice. remove it once so we can have it count only once.
}

let left = 1;
let right = maxSum;
while(left <= right) {
// const mid = Math.floor((right + left + 1)/2);
const mid = left + Math.floor((right - left)/2);
console.log(mid);
if(getSum(mid) <= maxSum) {
left = mid;
} else {
right = mid - 1;
}
}

return left;
};

[shanebillings]

You are reducing each number by 1 but there can be possibility that as also given in the leetcode example 1st the numbers were becoming something like this 1, 2, 2, 1(two is repeating twice)..But as per you algorithm its not like that please explan how it is also being done in your way too?

[suvrodattacp]

can anyone explain, why long m = mid - 1 ?

[spuranyarram]

Finally could understand the solution!! Do you also have Java code submissions?

[agyaani]

Samjh nhi aa rha bhaiya if else k baad bada prblm h!

[kollivenkatamadhukar]

Why m is mid - 1 and not mid, Is it to make things zero indexed