Formatted question description: https://leetcode.ca/all/1802.html

# 1802. Maximum Value at a Given Index in a Bounded Array

## Level

Medium

## Description

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.

**Example 1:**

**Input:** n = 4, index = 2, maxSum = 6

**Output:** 2

**Explanation:** The arrays [1,1,**2**,1] and [1,2,**2**,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.

**Example 2:**

**Input:** n = 6, index = 1, maxSum = 10

**Output:** 3

**Constraints:**

`1 <= n <= maxSum <= 10^9`

`0 <= index < n`

## Solution

Use binary search. Initialize `low = 1`

and `high = maxSum`

. Each time calculate `mid`

as the mean of `low`

and `high`

, and calculate the minimum possible sum of `nums`

when `nums[index] = mid`

. If the minimum possible sum is greater than `maxSum`

, let `high = mid - 1`

. Otherwise, let `low = mid`

. Finally, the answer is `low`

.

Note that all elements in `nums`

must be positive, which should be considered during binary search.

```
class Solution {
public int maxValue(int n, int index, int maxSum) {
int low = 1, high = maxSum;
while (low < high) {
long mid = (high - low + 1) / 2 + low;
long sumLeft = ((mid - index) + (mid - 1)) * index / 2;
if (mid <= index)
sumLeft = (mid - 1) * mid / 2 + index - mid + 1;
sumLeft = Math.max(sumLeft, index);
long sumRight = ((mid - 1) + (mid - (n - 1 - index))) * (n - index - 1) / 2;
if (mid <= n - 1 - index)
sumRight = (mid - 1) * mid / 2 + (n - 1 - index - mid) + 1;
sumRight = Math.max(sumRight, n - index - 1);
long sum = sumLeft + sumRight + mid;
if (sum > maxSum)
high = (int) mid - 1;
else
low = (int) mid;
}
return low;
}
}
```