Maximum Value at a Given Index in a Bounded Array
Medium · Binary Search · Binary Search · Greedy · Math
Problem
You are given three positive integers n, index and maxSum. Build an array nums of length n (0-indexed) that satisfies all of the following:
- Every nums[i] is a positive integer.
- Neighboring values differ by at most 1: |nums[i] - nums[i+1]| <= 1.
- The total sum(nums) does not exceed maxSum.
Among all such arrays, make nums[index] as large as possible. Return that largest value of nums[index].
Examples
Input: n = 5, index = 2, maxSum = 11 Output: 3
[1,2,3,2,1] sums to 9. A peak of 4 needs at least [2,3,4,3,2], which sums to 14.
Input: n = 3, index = 0, maxSum = 10 Output: 4
[4,3,2] sums to 9, while a peak of 5 needs at least [5,4,3] = 12.
Input: n = 4, index = 3, maxSum = 4 Output: 1
Every value must be at least 1, so the budget of 4 allows only [1,1,1,1].
Constraints
- 1 <= n <= maxSum <= 10^9
- 0 <= index < n
Approaches
- Raise the peak one unit at a time — time O(answer), space O(1)
Follow-up
What if neighbors could differ by up to d instead of 1? The sides fall faster, so each side becomes a series with step d, still followed by ones, and the same binary search applies. See the second use case.
Related problems
Start free on Cariara · Coding problems · System design studio
