Maximum Value At A Given Index In A Bounded Array - Leetcode Solution

Problem Statement:

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.

Solution:

We can begin by noting that the array we want to construct has the following properties:

• The largest number we can construct at index i is maxSum - (n - 1) because each element in the array can be as low as 1.
• The smallest number we can construct at index i is 1 because the array must be increasing or decreasing.

Given these two properties, we can use binary search to find the maximum value we can construct at index i. We can start by setting the lower bound to 1 and the upper bound to maxSum - (n - 1) and iterate until the lower and upper bounds converge. At each iteration, we check if the mid value can be constructed at index i. To do this, we need to check if the sum of all the values in the array that are less than or equal to the mid value plus the sum of all the values greater than the mid value but less than or equal to mid + 1 is less than or equal to maxSum.

If the sum is less than or equal to maxSum, then we know that we can construct the mid value at index i. We can then update the lower bound to mid + 1. If the sum is greater than maxSum, then we know that we cannot construct the mid value at index i. We can then update the upper bound to mid - 1.

After running this binary search, the maximum value we can construct at index i will be the value at the convergence point of the lower and upper bounds.

Time Complexity:

The binary search takes O(log(maxSum - (n - 1))) iterations. Calculating the sum of the array takes O(n) time. Therefore, the overall time complexity of the solution is O(nnlog(maxSum - (n - 1))).

Space Complexity:

The solution uses constant space. Therefore, the space complexity is O(1).

Here's the code in Python:

class Solution: def maxValue(self, n: int, index: int, maxSum: int) -> int: def canConstruct(val): leftSum = max(0, val - index) leftCount = val - leftSum rightSum = max(0, val - (n - 1 - index)) rightCount = val - rightSum totalSum = (leftCount * (leftSum + val)) // 2 + (rightCount * (rightSum + val)) // 2 if val % 2 == 1: totalSum -= (leftCount + rightCount) // 2 return totalSum <= maxSum left, right = 1, maxSum - (n - 1) while left < right: mid = (left + right + 1) // 2 if canConstruct(mid): left = mid else: right = mid - 1 return left

1