Problem

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.

Examples

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

Solution

Method 1 - Binary Search

To solve this problem, we can use a binary search approach. The idea is to find the maximum value for nums[index] while ensuring that all the conditions mentioned are satisfied.

Here is the approach:

  1. Initialization:
    • We need a function to calculate the sum of the array based on a given peak (maximum possible value at index) and the constraints.
    • Use binary search to determine the maximum possible value at index.
  2. Binary Search:
    • Perform binary search on the possible values of nums[index] from 1 to maxSum.
    • For each candidate value, check if the constructed array satisfies the maxSum constraint.
  3. Sum Calculation:
    • Determine the sum of the segment to the left of index, including index.
    • Determine the sum of the segment to the right of index.
    • Ensure the total sum does not exceed maxSum.

Code

Java
public class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum;

        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (isValid(n, index, maxSum, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean isValid(int n, int index, int maxSum, int value) {
        long leftSum = sum(index, value - 1);
        long rightSum = sum(n - index - 1, value - 1);
        long totalSum = leftSum + rightSum + value;
        return totalSum <= maxSum;
    }

    private long sum(int length, long value) {
        if (length >= value) {
            return (value * (value + 1)) / 2 + (length - value);
        } else {
            return (length * (2 * value - length + 1)) / 2;
        }
    }
}
Python
class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        left, right = 1, maxSum

        def isValid(value):
            left_sum = sum_helper(index, value - 1)
            right_sum = sum_helper(n - index - 1, value - 1)
            total_sum = left_sum + right_sum + value
            return total_sum <= maxSum

        def sum_helper(length, value):
            if length >= value:
                return value * (value + 1) // 2 + (length - value)
            else:
                return length * (2 * value - length + 1) // 2

        while left < right:
            mid = (left + right + 1) // 2
            if isValid(mid):
                left = mid
            else:
                right = mid - 1

        return left

Complexity

  • ⏰ Time complexity: O(log (maxSum))
    • The binary search runs in O(log(maxSum)) as it halves the search space each time.
    • For each candidate mid-value, the isValid function runs in O(1) time, and its helper function sum_helper also runs in O(1).
  • 🧺 Space complexity: O(1)