1802. Maximum Value at a Given Index in a Bounded Array - Detailed Explanation

Problem Statement

You are given three positive integers:

• n: the length of the array.
• index: the position (0-indexed) at which you want to maximize the value.
• maxSum: the maximum allowed sum of all the elements in the array.

You need to construct an array nums of length n such that:

1. Every element in nums is a positive integer (≥ 1).
2. The sum of all elements in nums is less than or equal to maxSum.
3. The absolute difference between any two adjacent elements is at most 1.

Your goal is to determine the maximum possible value at the given index that can be achieved under these conditions.

Example 1

Input:

n = 4, index = 2, maxSum = 6

Output:

2

Explanation:
One possible optimal array is [1, 2, 2, 1].

• The element at index 2 is 2 (which is the maximum possible under the constraints).
• The sum is 1+2+2+1 = 6, which is equal to maxSum.
• The adjacent difference condition holds: |1-2| = 1, |2-2| = 0, and |2-1| = 1.

Example 2

Input:

n = 6, index = 1, maxSum = 10

Output:

3

Explanation:
One optimal array is [1, 3, 2, 1, 1, 1].

• The element at index 1 is 3.
• The total sum is 1+3+2+1+1+1 = 9 (which is ≤ 10).
• Adjacent differences are within 1.

Approach Overview

A key observation is that to maximize the value at the given index while keeping the total sum under control, the optimal array will “peak” at that index and then decrease by 1 at each step as you move away from it—until you hit 1 (since every element must be at least 1). This forms a “pyramid” or “mountain” shape centered at index.

How the Array Looks

Assume the maximum value at index is x. Then:

• To the left of index, the values decrease by 1 each step (but cannot drop below 1).
• Similarly, to the right of index, the values decrease by 1 per step (clamped at 1).

For example, if x = 5 and there are enough positions on the left, the left side might look like:

…, max(5 - k, 1)

for positions k = 1, 2, … from the peak.

Key Idea: Binary Search for the Optimal Peak

The problem is “monotonic” in the sense that if a candidate value x at the target index produces a total sum that is within maxSum, then any value less than x is also feasible. This motivates a binary search on the candidate value at index.

Calculating the Sum for a Candidate Value

For a given candidate x at the target index, we need to compute the minimum possible total sum of an array that has x at index and follows the constraints.

1. Left Side (positions 0 to index – 1):

   • Let L = index be the number of positions to the left.
   • If x > L (meaning the decreasing sequence can go all the way without hitting 1), the values will be:

     x-1, x-2, …, x-L
     

     The sum of these values is an arithmetic series:

     Sum_left = (x-1 + x-L) * L / 2
     

   • If x ≤ L, then after decreasing for x - 1 steps you reach 1. For the remaining positions, the value is clamped at 1.
     Let d = x - 1. Then,

     Sum_left = (1 + (x-1)) * d / 2 + (L - d)
     

2. Right Side (positions index+1 to n-1):

   • Let R = n - index - 1 be the number of positions to the right.
   • Similarly, if x > R, then the sum on the right is:

     Sum_right = (x-1 + x-R) * R / 2
     

   • Otherwise, let d = x - 1, then:

     Sum_right = (1 + (x-1)) * d / 2 + (R - d)
     

3. Total Sum:
   The total sum required for candidate x is:

   Total = x (peak value) + Sum_left + Sum_right
   

We then compare Total with maxSum. If Total ≤ maxSum, the candidate x is feasible. Using binary search, we try to find the maximum x for which this holds.

Binary Search Process

1. Initialize the Search Range:

   • The lower bound can be 1 (minimum value at any position).
   • The upper bound can be set as maxSum because in the extreme case (if n = 1) the only element equals maxSum.

2. Check the Midpoint:

   • For a candidate mid, compute the minimum required sum using the method described above.
   • If the sum is ≤ maxSum, move the lower bound up to try a larger value.
   • Otherwise, decrease the upper bound.

3. Termination:

   • The binary search continues until the search space is exhausted, and the answer is the largest candidate found that meets the constraints.

Python Code