LeetCode 1802. Maximum Value at a Given Index in a Bounded Array

Binary Search

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

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
    
    long getSumInRange(long peak, int length) {
        long sum = 0;
        if (length > peak) {
            sum += (1 + peak) * peak / 2;
            sum += (length - peak);
        } else {
            long minimum = peak - length + 1;
            sum += (minimum + peak) * length / 2;
        }
        return sum;
    }
    
    bool check(int n, int index, int maxSum, int peak) {
        long sum = getSumInRange(peak, index + 1) + getSumInRange(peak, n - index) - peak;
        return sum > (long)maxSum;
    }
    
public:
    int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum;
        int ans = 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            bool exceed = check(n, index, maxSum, mid);
            if (exceed) {
                right = mid - 1;
            } else {
                ans = mid;
                left = mid + 1;
            }
        }
        
        return ans;
    }
};