# Maximum Value at a Given Index in a Bounded Array LeetCode Solution

Difficulty Level Medium

## Problem Statement

The problem Maximum Value at a Given Index in a Bounded Array LeetCode Solution says You are given three positive integers: n, index, and maxSum. You want to construct an array nums(0-indexed) that satisfies the following conditions:

• nums.length == n
• nums[i] is a positive integer where 0 <= i < n.
• abs(nums[i]-nums[i+1]) <= 1 where 0 <= i < n-1.
• The sum of all the elements of nums does not exceed maxSum.
• nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.

n = 8

index = 3

maxSum = 14

3

n = 7

index = 4

maxSum = 8

2

## Explanation for Maximum Value at a Given Index in a Bounded Array LeetCode Solution:

i) For the first case, We can have the array as [0, 1, 2, 3, 2, 1, 0, 0].  So the max value at index 3 is 3. This is the max value we can have which satisfies all the constraints.

i) For the second case, We can have the array as [0, 0, 0, 1, 2, 1, 0].  So the max value at index 4 is 2. This is the max value we can have which satisfies all the constraints.

### Idea:

We first do maxSum -= n,
then all elements need only to valid A[i]>=0.

We binary search the final result between left and right,
where left = 0 and right = maxSum.

For each test, we check the minimum sum if A[index] = a.
The minimum case would be A[index] is a peak in A.
It’s an arithmetic sequence on the left of A[index] with the difference 1.
It’s also an arithmetic sequence on the right of A[index] with the difference -1.

On the left, A = max(a – index, 0),
On the right, A[n-1] = max(a – ((n-1) – index), 0),

The sum of arithmetic sequence {b, b+1, ….a},
equals to (a + b) * (a – b + 1)/ 2.

## Code

### Java Program for Maximum Value at a Given Index in a Bounded Array

```class Solution {
public int maxValue(int n, int index, int maxSum) {
maxSum -= n;
int left = 0, right = maxSum, mid;
while (left < right) {
mid = (left + right + 1) / 2;
if (test(n, index, mid) <= maxSum)
left = mid;
else
right = mid - 1;
}
return left + 1;
}

private long test(int n, int index, int a) {
int b = Math.max(a - index, 0);
long res = (long)(a + b) * (a - b + 1) / 2;
b = Math.max(a - ((n - 1) - index), 0);
res += (long)(a + b) * (a - b + 1) / 2;
return res - a;
}
}```

### C++ Program for Maximum Value at a Given Index in a Bounded Array

```class Solution {
public:
int maxValue(int n, int index, int maxSum) {
maxSum -= n;
int left = 0, right = maxSum, mid;
while (left < right) {
mid = (left + right + 1) / 2;
if (test(n, index, mid) <= maxSum)
left = mid;
else
right = mid - 1;
}
return left + 1;
}

long test(int n, int index, int a) {
int b = max(a - index, 0);
long res = long(a + b) * (a - b + 1) / 2;
b = max(a - ((n - 1) - index), 0);
res += long(a + b) * (a - b + 1) / 2;
return res - a;
}
};```

### Python Program for Maximum Value at a Given Index in a Bounded Array

```class Solution(object):
def maxValue(self, n, index, maxSum):
def test(a):
b = max(a - index, 0)
res = (a + b) * (a - b + 1) / 2
b = max(a - ((n - 1) - index), 0)
res += (a + b) * (a - b + 1) / 2
return res - a

maxSum -= n
left, right = 0, maxSum
while left < right:
mid = (left + right + 1) / 2
if test(mid) <= maxSum:
left = mid
else:
right = mid - 1
return left + 1
```

## Complexity Analysis for Maximum Value at a Given Index in a Bounded Array LeetCode Solution

### Time Complexity

For each value, we can check the sum in O(1)  time using the formula. So time complexity is O(log(maxSum)).

### Space Complexity

Here we are not using any extra space. So Space complexity is O(1).

Translate »