# Maximum Value at a Given Index in a Bounded Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-value-at-a-given-index-in-a-bounded-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance)
---
## Problem
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:** nums = [1,2,**2**,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].

**Example 2:**

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

**Constraints:**

* `1 <= n <= maxSum <= 109`
* `0 <= index < n`

# Approaches
## Linear Search (Brute Force)
A straightforward but inefficient approach is to check every possible value for `nums[index]` starting from the largest possible (`maxSum`) down to the smallest (`1`). The first value that satisfies the sum constraint is the answer. This method exhaustively checks all potential answers in a linear fashion.
**Time:** O(maxSum) - In the worst-case scenario, the loop runs from `maxSum` down to the actual answer. Since `maxSum` can be up to 10^9, this is not feasible. · **Space:** O(1) - Constant extra space is used.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient for large inputs.; Will result in a 'Time Limit Exceeded' error on most platforms due to the large constraints on `maxSum`.
### Explanation
The core of the problem is to find the maximum value `x` for `nums[index]` such that an array satisfying all conditions can be constructed. To maximize `x`, we must minimize the sum of all other elements. The condition `abs(nums[i] - nums[i+1]) <= 1` implies that the smallest possible sum for a given `nums[index] = x` occurs when the array values form a pyramid shape centered at `index`. The values decrease by 1 as we move away from the `index` in either direction, until they hit the minimum allowed value of 1, after which they remain 1.

This brute-force approach iterates through every possible value for `x` from `maxSum` down to `1`. For each `x`, it calculates the minimum sum of such a pyramid-shaped array. If this sum is within the `maxSum` limit, we have found our answer because we are checking in decreasing order.

```java
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        for (int x = maxSum; x >= 1; --x) {
            if (getMinSum(n, index, x) <= maxSum) {
                return x;
            }
        }
        return 0; // Should not be reached given constraints
    }

    private long getMinSum(int n, int index, int val) {
        long totalSum = val;
        totalSum += calculateSideSum(index, val);
        totalSum += calculateSideSum(n - 1 - index, val);
        return totalSum;
    }

    private long calculateSideSum(long count, int val) {
        long m = val - 1;
        long sum = 0;
        if (count >= m) {
            // Sequence goes down to 1, then flat at 1s
            sum = m * (m + 1) / 2;
            sum += (count - m);
        } else {
            // Sequence is an arithmetic progression that doesn't reach 1
            long first = m;
            long last = m - count + 1;
            sum = count * (first + last) / 2;
        }
        return sum;
    }
}
```
### Algorithm
*   Iterate through all possible values for `nums[index]` from `maxSum` down to `1`. Let's call the current candidate value `x`.
*   For each `x`, calculate the minimum possible sum of the array. This minimum sum is achieved when the array forms a pyramid shape with `x` at `index`, and values decrease by 1 on both sides until they reach 1.
*   The function `getMinSum(n, index, x)` is used to calculate this sum. It computes the sum of the peak `x`, the sum of the left side, and the sum of the right side.
*   If `getMinSum(n, index, x)` is less than or equal to `maxSum`, it means `x` is a valid value for `nums[index]`. Since we are iterating downwards, this is the highest possible valid value.
*   Return `x` as soon as a valid one is found.

## Binary Search on the Answer
A highly efficient approach utilizes binary search on the possible values of `nums[index]`. The key observation is that the total sum of the array is a monotonically increasing function of `nums[index]`. If we can construct an array with `nums[index] = x` that satisfies the sum constraint, we can certainly do so for any value less than `x`. This monotonicity allows us to efficiently search for the maximum possible value.
**Time:** O(log(maxSum)) - The binary search is performed on a range of values up to `maxSum`. Each check inside the binary search takes constant time. · **Space:** O(1) - We only use a few variables for the binary search, resulting in constant space usage.
**Pros:** Highly efficient with logarithmic time complexity.; Optimal solution that passes for all given constraints.
**Cons:** The logic for calculating the pyramid sum can be tricky to get right.; Requires careful handling of large numbers using `long` to prevent integer overflow.
### Explanation
To find the maximum `nums[index]`, we must minimize the sum of the array. This is achieved by creating a pyramid-like structure where `nums[index]` is the peak, and values decrease by 1 as we move away from `index` until they reach 1.

A clever simplification is to subtract `n` from `maxSum`. This is equivalent to considering an array `a` where `a[i] = nums[i] - 1 >= 0`, and the sum of `a` must not exceed `maxSum - n`. Our goal is to maximize `a[index]`. Let's call this maximum value `peak`. The array `a` will have a shape `a[i] = max(0, peak - |i - index|)`. The sum of `a` is a monotonic function of `peak`, making it ideal for binary search.

The search space for `peak` is `[0, maxSum - n]`. We use binary search to find the largest `peak` for which the sum of the corresponding array `a` does not exceed `maxSum - n`.

The sum of the pyramid `a` is `peak` plus the sums of the left and right sides. The sum of a side with `count` elements and a starting value of `peak - 1` can be calculated using formulas for arithmetic series. Special care must be taken for potential integer overflows by using `long` for sum calculations.

```java
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        long newMaxSum = (long)maxSum - n;
        long low = 0, high = newMaxSum;
        long ans = 0;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            long currentSum = calculatePyramidSum(mid, index, n);
            
            if (currentSum <= newMaxSum) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return (int)(ans + 1);
    }

    private long calculatePyramidSum(long peak, int index, int n) {
        long sum = peak;
        long leftCount = index;
        long rightCount = n - 1 - index;

        // Calculate sum of the left side
        if (leftCount >= peak) {
            // Sum of peak-1, peak-2, ..., 1, 0, ...
            // This is the sum of numbers from 1 to peak-1.
            sum += peak * (peak - 1) / 2;
        } else {
            // Sum of peak-1, peak-2, ..., peak-leftCount
            long first = peak - 1;
            long last = peak - leftCount;
            sum += leftCount * (first + last) / 2;
        }

        // Calculate sum of the right side
        if (rightCount >= peak) {
            // Sum of peak-1, peak-2, ..., 1, 0, ...
            sum += peak * (peak - 1) / 2;
        } else {
            long first = peak - 1;
            long last = peak - rightCount;
            sum += rightCount * (first + last) / 2;
        }
        
        return sum;
    }
}
```
### Algorithm
*   Observe that if a value `x` is achievable for `nums[index]`, any value smaller than `x` is also achievable. This monotonic property allows for binary search on the answer.
*   To simplify calculations, transform the problem. Instead of an array of positive integers summing to `maxSum`, consider an array of non-negative integers `a[i] = nums[i] - 1` summing to `maxSum - n`. We want to maximize `a[index]`. Let `peak = a[index]`.
*   The search space for `peak` is from `0` to `maxSum - n`.
*   Perform a binary search on this range. For each `mid` value (a candidate for `peak`):
    *   Calculate the minimum sum of the array `a`. This sum is a pyramid with `a[index] = mid`, and values `a[i] = max(0, mid - |i - index|)`. The sum can be calculated using arithmetic series formulas.
    *   This involves summing the `peak` value, the sum of the left side, and the sum of the right side.
*   If the calculated sum is less than or equal to `maxSum - n`, it means `mid` is a possible peak. We try for a larger peak, so we set `ans = mid` and `low = mid + 1`.
*   If the sum is greater, `mid` is too large. We search in the lower half by setting `high = mid - 1`.
*   The final result for `nums[index]` is `ans + 1`.

# Solutions
### Java

```java
class Solution {
public
  int maxValue(int n, int index, int maxSum) {
    int left = 1, right = maxSum;
    while (left < right) {
      int mid = (left + right + 1) >>> 1;
      if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
private
  long sum(long x, int cnt) {
    return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;
  }
}

```

### Python

```python
class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int: def sum(x, cnt): return ((x + x - cnt + 1) * cnt // 2 if x >= cnt else (x + 1) * x // 2 + cnt - x) left, right = 1, maxSum while left < right: mid = (left + right + 1) >> 1 if sum(mid - 1, index) + sum(mid, n - index) <= maxSum: left = mid else: right = mid - 1 return left

```

### CPP

```cpp
class Solution {
public:
  int maxValue(int n, int index, int maxSum) {
    auto sum = [](long x, int cnt) {
      return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;
    };
    int left = 1, right = maxSum;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
};

```