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

Solution: simulation

• Time complexity: O(logn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @param {number} index
 * @param {number} maxSum
 * @return {number}
 */
const maxValue = function (n, index, maxSum) {
  let left = (right = index);
  let result = 1;

  maxSum -= n;

  while (left > 0 || right < n - 1) {
    const gap = right - left + 1;

    if (maxSum < gap) break;
    maxSum -= gap;
    result += 1;
    left = Math.max(0, left - 1);
    right = Math.min(n - 1, right + 1);
  }
  return result + Math.floor(maxSum / n);
};