Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1802.html

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

Level

Medium

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: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.

Example 2:

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

Output: 3

Constraints:

• 1 <= n <= maxSum <= 10^9
• 0 <= index < n

Solution

Use binary search. Initialize low = 1 and high = maxSum. Each time calculate mid as the mean of low and high, and calculate the minimum possible sum of nums when nums[index] = mid. If the minimum possible sum is greater than maxSum, let high = mid - 1. Otherwise, let low = mid. Finally, the answer is low.

Note that all elements in nums must be positive, which should be considered during binary search.

• Java
• C++
• Python
• Go

• class Solution {
      public int maxValue(int n, int index, int maxSum) {
          int low = 1, high = maxSum;
          while (low < high) {
              long mid = (high - low + 1) / 2 + low;
              long sumLeft = ((mid - index) + (mid - 1)) * index / 2;
              if (mid <= index)
                  sumLeft = (mid - 1) * mid / 2 + index - mid + 1;
              sumLeft = Math.max(sumLeft, index);
              long sumRight = ((mid - 1) + (mid - (n - 1 - index))) * (n - index - 1) / 2;
              if (mid <= n - 1 - index)
                  sumRight = (mid - 1) * mid / 2 + (n - 1 - index - mid) + 1;
              sumRight = Math.max(sumRight, n - index - 1);
              long sum = sumLeft + sumRight + mid;
              if (sum > maxSum)
                  high = (int) mid - 1;
              else
                  low = (int) mid;
          }
          return low;
      }
  }
  
  ############
  
  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;
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/
  // Time: O(log(maxSum))
  // Space: O(1)
  class Solution {
      long count(long len, long M) {
          return M >= len ? (2 * M - len + 1) * len / 2 : ((M - 1) * M / 2 + len);
      }
      bool valid(long n, long i, long maxSum, long M) {
          long left = count(i + 1, M), right = count(n - i, M);
          return left + right - M <= maxSum;
      }
  public:
      int maxValue(int n, int index, int maxSum) {
          int L = 1, R = maxSum;
          while (L <= R) {
              int M = (L + R) / 2;
              if (valid(n, index, maxSum, M)) L = M + 1;
              else R = M - 1;
          }
          return R;
      }
  };
  

• 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
  
  ############
  
  # 1802. Maximum Value at a Given Index in a Bounded Array
  # https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/
  
  class Solution:
      def maxValue(self, n: int, index: int, maxSum: int) -> int:
          def good(a):
              b = max(a - index, 0)
              res = (a + b) * (a - b + 1) // 2
              b = max(a - ((n - 1) - index), 0)
              res += (a + b) * (a - b + 1) // 2
              return res - a
          
          maxSum -= n
          left, right = 0, maxSum
          
          while left < right:
              mid = (left + right + 1) // 2
              if good(mid) <= maxSum:
                  left = mid
              else:
                  right = mid - 1
          
          return left + 1
  
  

• 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
  	})
  }
  

All Problems

All Solutions