1802. Maximum Value at a Given Index in a Bounded Array
Asked at Microsoft
Difficulty
Medium
Time
O(log maxSum)
Space
O(1)
Pattern
Math
Companies
1
Problem
You are given three positive integers n, index, and maxSum. Build an array nums of length n that follows these rules:
- Every element is a positive integer (at least 1).
- Neighbours differ by at most 1:
abs(nums[i] - nums[i+1]) <= 1. - The total of all elements is at most
maxSum.
Among all arrays that satisfy these rules, make nums[index] as large as possible, and return that largest value.
The trick is that a big value at index forces the values next to it to be big too. Each step away from index can drop by at most 1, so the cheapest valid array looks like a mountain that peaks at index.
A mountain shape around index
Constraints
- ●
1 <= n <= maxSum <= 10^9 - ●
0 <= index < n - ●
nums[i] >= 1 for every i
Examples
n = 4, index = 2, maxSum = 62n = 6, index = 1, maxSum = 103Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft questions → |
How to Think About It
The key constraint: the sum of the array cannot exceed maxSum, and all values must be at least 1. If we maximize arr[index] to some value m, we need the surrounding elements to be as small as possible while still being positive and forming a valid non-increasing slope from index.
The optimal shape around index is a "mountain": values increase by 1 each step from both ends toward index, peaking at index. For example, if index = 2 and n = 5 and peak = 4: [1, 2, 4, 2, 1]. This minimizes the total sum for a given peak value.
Binary search on the answer m (the value at index). For each candidate m, calculate the minimum possible sum of the array with arr[index] = m. If this sum <= maxSum, m is feasible, so try higher. Otherwise, try lower.
Calculating the minimum sum for peak m: the left side has index elements (indices 0 to index-1), the right side has n - index - 1 elements. Each side forms a ramp from 1 up to m-1. If the ramp is shorter than m-1, elements stay at 1. Use the formula: sum of a ramp from 1 to k is k*(k+1)/2, and if there are extra elements, they contribute 1 each.
The formula for left side: left_len = index. The ramp height is min(m-1, left_len). Sum = ramp_sum + (left_len - ramp_sum_len) * 1. Similarly for the right side with right_len = n - index - 1.
Total minimum sum = left_sum + m + right_sum.
If total <= maxSum, value m is achievable.
Binary search bounds: low = 1, high = maxSum (worst case, the entire sum is one element). Complexity: O(n log maxSum) — O(n) to compute the minimum sum, O(log maxSum) iterations.
Optimal Approach
Binary search on m (the value at index). For each candidate m, compute the minimum possible sum of a valid array with arr[index] = m.
To compute the minimum sum:
- Left side:
left_len = index. Ramp from 1 up tomin(m-1, left_len). Letleft_ramp = min(m-1, left_len). Sum of ramp =left_ramp * (left_ramp + 1) / 2. Remaining elements:(left_len - left_ramp) * 1. - Right side:
right_len = n - index - 1. Same formula withright_ramp = min(m-1, right_len). - Total =
left_sum + m + right_sum.
If total <= maxSum, m is feasible (try higher). Else, try lower.
Walkthrough: n = 4, index = 2, maxSum = 6.
- Try
m = 4: left_len=2, right_len=1. left_ramp=min(3,2)=2, sum=3. right_ramp=min(3,1)=1, sum=1. Total=3+4+1=8 > 6. Too high. - Try
m = 2: left_ramp=min(1,2)=1, sum=1. right_ramp=min(1,1)=1, sum=1. Total=1+2+1=4 <= 6. Feasible. - Try
m = 3: left_ramp=min(2,2)=2, sum=3. right_ramp=min(2,1)=1, sum=1. Total=3+3+1=7 > 6. Too high. - Answer: 2.
Time: O(n log maxSum). Space: O(1).
Binary search the peak
What Trips People Up in Real Interviews
Not realizing the optimal array shape is a "mountain" centered at index. The surrounding elements should decrease by 1 each step away from index (clamped at 1). Any other shape uses more sum for the same peak.
Off-by-one errors in the ramp calculation. The left side has index elements (indices 0 to index-1), not index + 1. The right side has n - index - 1 elements. Double-check the boundaries.
Forgetting that all elements must be at least 1, not 0. The problem states arr[i] > 0, so the ramp floors at 1, not 0. This affects the sum calculation.
Using a linear scan instead of binary search. You could try each value of m from 1 upward, but that is O(maxSum). Binary search on m gives O(log maxSum) checks.
Not handling the case where the ramp height exceeds the available elements on one side. If index = 1 (left side has only 1 element) and m = 5, you can only ramp to 2 on the left, not to 5. Use min(m-1, left_len) to cap the ramp.
Solution Code
O(log maxSum) timedef maxValue(n, index, maxSum):
def min_sum(m):
left_len = index
right_len = n - index - 1
left_ramp = min(m - 1, left_len)
right_ramp = min(m - 1, right_len)
left_sum = left_ramp * (left_ramp + 1) // 2 + max(0, left_len - left_ramp)
right_sum = right_ramp * (right_ramp + 1) // 2 + max(0, right_len - right_ramp)
return left_sum + m + right_sum
lo, hi = 1, maxSum
while lo < hi:
mid = (lo + hi + 1) // 2
if min_sum(mid) <= maxSum:
lo = mid
else:
hi = mid - 1
return loFrequently Asked Questions
What is the Maximum Value at a Given Index in a Bounded Array problem?
You are given three positive integers `n`, `index`, and `maxSum`. You need to construct an array `arr` of length `n` where `arr[index]` is maximized, `0 < arr[i]` for all indices, and the total sum of `arr` is at most `maxSum`. Return the maximum possible value at `index`.
How do you solve Maximum Value at a Given Index in a Bounded Array?
The optimal approach runs in O(log maxSum) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Maximum Value at a Given Index in a Bounded Array?
Maximum Value at a Given Index in a Bounded Array is asked at Microsoft. It is a medium difficulty problem.
What are common mistakes on Maximum Value at a Given Index in a Bounded Array?
- Not realizing the optimal array shape is a "mountain" centered at `index`. The surrounding elements should decrease by 1 each step away from `index` (clamped at 1). Any other shape uses more sum for the same peak.
- Off-by-one errors in the ramp calculation. The left side has `index` elements (indices 0 to index-1), not `index + 1`. The right side has `n - index - 1` elements. Double-check the boundaries.
- Forgetting that all elements must be at least 1, not 0. The problem states `arr[i] > 0`, so the ramp floors at 1, not 0. This affects the sum calculation.
- Using a linear scan instead of binary search. You could try each value of `m` from 1 upward, but that is `O(maxSum)`. Binary search on `m` gives `O(log maxSum)` checks.
- Not handling the case where the ramp height exceeds the available elements on one side. If `index = 1` (left side has only 1 element) and `m = 5`, you can only ramp to 2 on the left, not to 5. Use `min(m-1, left_len)` to cap the ramp.