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 where 0 <= i < n.
• abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
• The sum of all the elements of 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: 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;
    }
}

All Problems

All Solutions