{x}
blog image

Maximum Value at a Given Index in a Bounded Array

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

Solution Explanation: Maximum Value at a Given Index in a Bounded Array

This problem asks to construct an array nums of length n with positive integers, where the absolute difference between consecutive elements is at most 1, the sum doesn't exceed maxSum, and nums[index] is maximized.

The core idea is to use binary search to find the maximum possible value for nums[index]. We can efficiently check if a given value for nums[index] is feasible by calculating the minimum sum of the array that satisfies the constraints.

  1. Feasibility Check: For a given nums[index] = x, the minimum sum is achieved by:

    • Decreasing values to the left of index from x-1 down to 1 (or until we run out of elements).
    • Decreasing values to the right of index from x down to 1 (or until we run out of elements).

  2. Sum Calculation: We can efficiently calculate the sum using the following observations:

    • The sum of a decreasing sequence from a to 1 is given by a * (a + 1) / 2.
    • If the sequence doesn't reach 1, we add the remaining elements (which would all be 1).

  3. Binary Search: We perform a binary search on the possible values of nums[index], starting with left = 1 (minimum possible value) and right = maxSum (maximum possible value). In each iteration:

    • Calculate the minimum sum for mid = (left + right + 1) / 2.
    • If the sum is less than or equal to maxSum, it's feasible, so update left = mid.
    • Otherwise, it's infeasible, so update right = mid - 1.

  4. Result: After the binary search converges, left will hold the maximum feasible value for nums[index].

Time and Space Complexity

  • Time Complexity: O(log(maxSum)). The binary search iterates at most O(log(maxSum)) times. The sum calculation within each iteration takes O(1) time.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementations

Python3

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

Java

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            long totalSum = calculateSum(mid - 1, index) + calculateSum(mid, n - index);
            if (totalSum <= maxSum) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
 
    private long calculateSum(long x, int count) {
        if (x >= count) {
            return (x + x - count + 1) * count / 2;
        } else {
            return (x + 1) * x / 2 + count - x;
        }
    }
}

C++

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

Go

func maxValue(n int, index int, maxSum int) int {
	calculateSum := func(x, count int) int {
		if x >= count {
			return (x + x - count + 1) * count / 2
		}
		return (x + 1) * x / 2 + count - x
	}
 
	left, right := 1, maxSum
	for left < right {
		mid := (left + right + 1) / 2
		totalSum := calculateSum(mid-1, index) + calculateSum(mid, n-index)
		if totalSum <= maxSum {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

These code examples all implement the binary search approach described above. They differ slightly in syntax but share the same underlying logic. Note the use of long long in the C++ code to prevent integer overflow when calculating totalSum. Similarly, Java uses long for the same reason. Go implicitly handles large numbers, but care should be taken in other languages to avoid overflow.