Formatted question description: https://leetcode.ca/all/1802.html
1802. Maximum Value at a Given Index in a Bounded Array
Level
Medium
Description
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 == n
nums[i]
is a positive integer where0 <= i < n
.abs(nums[i] - nums[i+1]) <= 1
where0 <= i < n-1
.- The sum of all the elements of
nums
does not exceedmaxSum
. 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: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.
Example 2:
Input: n = 6, index = 1, maxSum = 10
Output: 3
Constraints:
1 <= n <= maxSum <= 10^9
0 <= index < n
Solution
Use binary search. Initialize low = 1
and high = maxSum
. Each time calculate mid
as the mean of low
and high
, and calculate the minimum possible sum of nums
when nums[index] = mid
. If the minimum possible sum is greater than maxSum
, let high = mid - 1
. Otherwise, let low = mid
. Finally, the answer is low
.
Note that all elements in nums
must be positive, which should be considered during binary search.
class Solution {
public int maxValue(int n, int index, int maxSum) {
int low = 1, high = maxSum;
while (low < high) {
long mid = (high - low + 1) / 2 + low;
long sumLeft = ((mid - index) + (mid - 1)) * index / 2;
if (mid <= index)
sumLeft = (mid - 1) * mid / 2 + index - mid + 1;
sumLeft = Math.max(sumLeft, index);
long sumRight = ((mid - 1) + (mid - (n - 1 - index))) * (n - index - 1) / 2;
if (mid <= n - 1 - index)
sumRight = (mid - 1) * mid / 2 + (n - 1 - index - mid) + 1;
sumRight = Math.max(sumRight, n - index - 1);
long sum = sumLeft + sumRight + mid;
if (sum > maxSum)
high = (int) mid - 1;
else
low = (int) mid;
}
return low;
}
}