LeetCode 1802. Maximum Value at a Given Index in a Bounded Array Solution in Java, C++, Python & Go | Explanation + Code

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

Solutions

Solution 1: Binary Search

According to the problem description, if we determine the value of nums[index] as x, we can find a minimum array sum. That is, the elements on the left side of index in the array decrease from x-1 to 1, and if there are remaining elements, the remaining elements are all 1; similarly, the elements at index and on the right side of the array decrease from x to 1, and if there are remaining elements, the remaining elements are all 1.

In this way, we can calculate the sum of the array. If the sum is less than or equal to maxSum, then the current x is valid. As x increases, the sum of the array will also increase, so we can use the binary search method to find the maximum x that meets the conditions.

To facilitate the calculation of the sum of the elements on the left and right sides of the array, we define a function sum(x, cnt), which represents the sum of an array with cnt elements and a maximum value of x. The function sum(x, cnt) can be divided into two cases:

• If x ≥ cnt, then the sum of the array is ^{(x + x - cnt + 1) × cnt}⁄₂
• If x \lt cnt, then the sum of the array is ^{(x + 1) × x}⁄₂ + cnt - x

Next, define the left boundary of the binary search as left = 1, the right boundary as right = maxSum, and then binary search for the value mid of nums[index]. If sum(mid - 1, index) + sum(mid, n - index) ≤ maxSum, then the current mid is valid, we can update left to mid, otherwise we update right to mid - 1.

Finally, return left as the answer.

The time complexity is O(log M), where M=maxSum. The space complexity is O(1).

PythonJavaC++Go

class Solution: def maxValue(self, n: int, index: int, maxSum: int) -> int: def sum(x, cnt): return ( (x + x - cnt + 1) * cnt // 2 if x >= cnt else (x + 1) * x // 2 + cnt - x ) left, right = 1, maxSum while left < right: mid = (left + right + 1) >> 1 if sum(mid - 1, index) + sum(mid, n - index) <= maxSum: left = mid else: right = mid - 1 return left(code-box)

class Solution { public int maxValue(int n, int index, int maxSum) { int left = 1, right = maxSum; while (left < right) { int mid = (left + right + 1) >>> 1; if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) { left = mid; } else { right = mid - 1; } } return left; } private long sum(long x, int cnt) { return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x; } }(code-box)

class Solution { public: int maxValue(int n, int index, int maxSum) { auto sum = [](long x, int cnt) { return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x; }; int left = 1, right = maxSum; while (left < right) { int mid = (left + right + 1) >> 1; if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) { left = mid; } else { right = mid - 1; } } return left; } };(code-box)

func maxValue(n int, index int, maxSum int) int { sum := func(x, cnt int) int { if x >= cnt { return (x + x - cnt + 1) * cnt / 2 } return (x+1)*x/2 + cnt - x } return sort.Search(maxSum, func(x int) bool { x++ return sum(x-1, index)+sum(x, n-index) > maxSum }) }(code-box)