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 == nnums[i] is a positive integer where 0 <= i < n.abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.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 <= 1090 <= index < nProblem Overview: You need to build an array of length n where every element is at least 1, the total sum does not exceed maxSum, and the difference between adjacent elements is at most 1. The goal is to maximize the value at a given index. The challenge is distributing the remaining sum while maintaining the decreasing-by-one constraint away from the index.
Approach 1: Greedy Incremental Construction (O(n * value), O(1) space)
This approach simulates building the array by increasing the value at index step by step. Each time you increase the center value, you extend decreasing values to the left and right while ensuring every element remains at least 1. The required sum forms a pyramid-like structure where values drop by one as you move away from the peak. For each candidate height, compute how much sum the left and right sides require. Stop once the total exceeds maxSum. This approach is intuitive and useful for understanding the structure of the optimal array, but repeated calculations make it inefficient when maxSum is large.
Approach 2: Binary Search with Greedy Sum Calculation (O(log maxSum), O(1) space)
The optimal strategy uses binary search on the value at index. Instead of constructing arrays, guess a candidate value x and check if it is feasible within maxSum. The key observation: the left and right sides form decreasing sequences starting from x-1. If the sequence reaches 1 before covering all positions, the remaining elements stay at 1. Using arithmetic progression formulas, you can compute the required sum for both sides in constant time. Combine left sum, right sum, and the center value, then compare against maxSum. If the sum fits, increase the search range; otherwise decrease it. This transforms a potentially large search space into logarithmic iterations.
The feasibility check is essentially a small greedy calculation: always place the highest possible values near the target index and decrease outward while respecting the constraints. No explicit array is required—only arithmetic sums.
Recommended for interviews: Binary search with greedy validation. Interviewers expect you to recognize the monotonic property: if value x is feasible, all values smaller than x are also feasible. Demonstrating the greedy sum calculation shows strong understanding of constrained array construction and array optimization patterns. The incremental approach helps explain the intuition, but the binary search solution is what most interviewers want to see.
The binary search approach focuses on maximizing `nums[index]` while maintaining the constraints. We consider `nums[index]` as the peak of a potential 'pyramid' in the array. By conducting a binary search on possible values for `nums[index]`, we iterate through and check whether the constraints on both sides of the index and the sum are maintained.
Each mid value tested in the binary search represents the height of the peak at index. For each mid value, we compute the minimum sum required for both sides of the index.
If the calculated sum is within `maxSum`, the peak can be higher, leading us to the right half (mid + 1) of our binary search space. Otherwise, we try smaller values by searching the left half.
The implementation defines two helper functions to calculate the sum of the left and right parts of the array relative to the index.
We use a binary search within the range of 1 to `maxSum` to find the maximum possible value at `nums[index]` that satisfies the given constraints.
Time complexity: O(log(maxSum)) - Binary search divides the range of possible peak values logarithmically.
Space complexity: O(1) - Uses a constant amount of space.
This approach involves incrementally building the array by focusing solely on maximizing `nums[index]` using a greedy construction. This directly extends from index to balance the array's condition and sum constraints effectively, utilizing the available sum step-by-step. We increment each value symmetrically from the index point, considering both left and right constraints and ensuring all steps preserve the `abs(nums[i] - nums[i+1]) <= 1` condition.
We keep track of increments needed and subtract from `maxSum` accordingly, thereby implicitly maximizing `nums[index]` while maintaining valid conditions.
The C solution incrementally grows `nums[index]` by extending left and right, maintaining conditions while increasing as much as possible under given max sum.
Time complexity: O(n) - Incrementally checks and adjusts values from center to borders of the array.
Space complexity: O(1) - Constant space used without additional data structures.
According to the problem description, if we determine the value of nums[index] as x, we can find a minimum array sum. That is, the elements on the left side of index in the array decrease from x-1 to 1, and if there are remaining elements, the remaining elements are all 1; similarly, the elements at index and on the right side of the array decrease from x to 1, and if there are remaining elements, the remaining elements are all 1.
In this way, we can calculate the sum of the array. If the sum is less than or equal to maxSum, then the current x is valid. As x increases, the sum of the array will also increase, so we can use the binary search method to find the maximum x that meets the conditions.
To facilitate the calculation of the sum of the elements on the left and right sides of the array, we define a function sum(x, cnt), which represents the sum of an array with cnt elements and a maximum value of x. The function sum(x, cnt) can be divided into two cases:
x geq cnt, then the sum of the array is \frac{(x + x - cnt + 1) times cnt}{2}x \lt cnt, then the sum of the array is \frac{(x + 1) times x}{2} + cnt - xNext, define the left boundary of the binary search as left = 1, the right boundary as right = maxSum, and then binary search for the value mid of nums[index]. If sum(mid - 1, index) + sum(mid, n - index) leq maxSum, then the current mid is valid, we can update left to mid, otherwise we update right to mid - 1.
Finally, return left as the answer.
The time complexity is O(log M), where M=maxSum. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time complexity: O(log(maxSum)) - Binary search divides the range of possible peak values logarithmically. Space complexity: O(1) - Uses a constant amount of space. |
| Greedy Incremental Construction Approach | Time complexity: O(n) - Incrementally checks and adjusts values from center to borders of the array. Space complexity: O(1) - Constant space used without additional data structures. |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Incremental Construction | O(n * value) | O(1) | Useful for understanding the pyramid structure and constraints during initial reasoning |
| Binary Search with Greedy Sum Check | O(log maxSum) | O(1) | Best approach for large constraints; standard interview solution |
LeetCode 1802. Maximum Value at a Given Index in a Bounded Array | Weekly Contest 233 🏆 | Explained • Cherry Coding [IIT-G] • 14,103 views views
Watch 9 more video solutions →Practice Maximum Value at a Given Index in a Bounded Array with our built-in code editor and test cases.
Practice on FleetCode