Watch 10 video solutions for Maximum Value at a Given Index in a Bounded Array, a medium level problem involving Binary Search, Greedy. This walkthrough by Cherry Coding [IIT-G] has 14,103 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |