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

Problem Link

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: nums = [1,2,2,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].

Example 2:

Input: n = 6, index = 1,  maxSum = 10
Output: 3

 

Constraints:

• 1 <= n <= maxSum <= 109
• 0 <= index < n

Solution

---

Python3

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        left, right = 1, maxSum
 
        def f(start, end):
            return (end * (end - 1) // 2) - (start * (start - 1) // 2)
        
        def good(k):
            left = index
            right = n - index - 1
 
            # x x x x x 3 x x x x x
 
            extras = max(0, left - k + 1) + max(0, right - k + 1)
            leftCount = f(max(1, k - left), k)
            rightCount = f(max(1, k - right), k)
 
            return leftCount + rightCount + extras + k <= maxSum
        
        while left < right:
            mid = (left + right + 1) // 2
            
            if good(mid):
                left = mid
            else:
                right = mid - 1
        
        return left