Maximum Value at a Given Index in a Bounded Array
Asked at Microsoft
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.
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.