Skip to content

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

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

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 \geq cnt\), then the sum of the array is \(\frac{(x + x - cnt + 1) \times cnt}{2}\)
  • If \(x \lt cnt\), then the sum of the array is \(\frac{(x + 1) \times x}{2} + 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) \leq 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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
    })
}

Comments