Code Implementation

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def calc_sum(mid):
            # Calculate sum on the left of index
            if mid > index:
                left_sum = (mid + mid - index) * (index + 1) // 2
            else:
                left_sum = (mid + 1) * mid // 2 + (index - mid + 1)
            # Calculate sum on the right of index
            if mid > n - index - 1:
                right_sum = (mid + mid - (n - index - 1)) * (n - index) // 2
            else:
                right_sum = (mid + 1) * mid // 2 + (n - index - mid)
            # Remove double counted mid
            return left_sum + right_sum - mid

        left, right = 1, maxSum
        ans = 1
        while left <= right:
            mid = (left + right) // 2
            s = calc_sum(mid)
            if s <= maxSum:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans
      

class Solution {
public:
    long long calc_sum(int mid, int n, int index) {
        long long left, right;
        if (mid > index)
            left = (long long)(mid + mid - index) * (index + 1) / 2;
        else
            left = (long long)(mid + 1) * mid / 2 + (index - mid + 1);
        if (mid > n - index - 1)
            right = (long long)(mid + mid - (n - index - 1)) * (n - index) / 2;
        else
            right = (long long)(mid + 1) * mid / 2 + (n - index - mid);
        return left + right - mid;
    }

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

class Solution {
    private long calcSum(int mid, int n, int index) {
        long left, right;
        if (mid > index)
            left = (long)(mid + mid - index) * (index + 1) / 2;
        else
            left = (long)(mid + 1) * mid / 2 + (index - mid + 1);
        if (mid > n - index - 1)
            right = (long)(mid + mid - (n - index - 1)) * (n - index) / 2;
        else
            right = (long)(mid + 1) * mid / 2 + (n - index - mid);
        return left + right - mid;
    }

    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum, ans = 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (calcSum(mid, n, index) <= maxSum) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}
      

var maxValue = function(n, index, maxSum) {
    function calcSum(mid) {
        let left, right;
        if (mid > index)
            left = (mid + mid - index) * (index + 1) / 2;
        else
            left = (mid + 1) * mid / 2 + (index - mid + 1);
        if (mid > n - index - 1)
            right = (mid + mid - (n - index - 1)) * (n - index) / 2;
        else
            right = (mid + 1) * mid / 2 + (n - index - mid);
        return left + right - mid;
    }
    let left = 1, right = maxSum, ans = 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let s = calcSum(mid);
        if (s <= maxSum) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
};
      

Problem Description

Given three integers n, index, and maxSum, you are to construct an array nums of length n where:

• Each element nums[i] is a positive integer (i.e., at least 1).
• The sum of all elements in nums is at most maxSum.
• You want to maximize the value at position index in the array, i.e., nums[index], under the above constraints.
• The array can be constructed in any way as long as it satisfies the above.

Constraints:

• There is always at least one valid solution.
• All elements must be positive integers.
• Elements can be repeated except for the constraint on the sum.

Thought Process

At first, you might consider brute-forcing: try all possible values for nums[index] from 1 up to maxSum, and for each, fill in the rest of the array with the minimum possible values (1), and check if the total sum is within maxSum. However, this is inefficient for large n or maxSum.

To optimize, notice that the array should be "steep" at index and decrease as slowly as possible towards both ends, but never go below 1. For any candidate value for nums[index], the rest of the array should be minimized to allow the maximum at index.

This leads to a binary search approach: guess a value for nums[index] and, for that guess, calculate the minimal total sum required for the whole array. If it fits within maxSum, try a higher value; otherwise, try lower.

Solution Approach

The solution uses a binary search to find the largest value of nums[index] such that the sum of the array does not exceed maxSum. Here’s how:

1. Binary Search Setup:
   • Set left = 1 and right = maxSum (the highest possible value for nums[index]).
   • Iteratively narrow down the possible value for nums[index] by checking if the array can be constructed with a given mid value.
2. Sum Calculation for a Given Mid:
   • For a candidate value mid at index, the values to the left and right of index decrease by 1 for each step away from index, but never go below 1.
   • The sum for the left part is:
     • If mid > index: the sequence is strictly decreasing, sum of arithmetic sequence.
     • If mid <= index: some positions will be 1, rest form a decreasing sequence.
   • Similarly for the right part (from index+1 to n-1).
   • Add both sides and subtract mid (since nums[index] is counted twice).
3. Binary Search Iteration:
   • If the calculated sum is within maxSum, try a higher value (move left up).
   • If not, try a lower value (move right down).
   • Keep track of the maximum feasible value found.
4. Return the Maximum Value:
   • After the binary search, return the recorded answer.

This approach is efficient because it avoids constructing the array and instead computes the sum mathematically.

Example Walkthrough

Suppose n = 4, index = 2, and maxSum = 6.

1. First Guess: Try nums[2] = 3.
   • Left side: index 0 needs to be at least 1, index 1 at least 2 (since we decrease by 1 each step).
   • So left: [1,2], index: 3, right: [2,1]. But the array must be of length 4 and sum <= 6.
   • But [1,2,3,2] sums to 8 > 6, so 3 is too high.
2. Try Lower: Try nums[2] = 2.
   • Left: [1,1], index: 2, right: [1,1].
   • Array: [1,1,2,1]. Sum: 5 ≤ 6. Valid.
   • Try higher? Let's check 2 is the max.
3. Check 3 Again:
   • As above, sum is too high. So answer is 2.

The binary search would efficiently find that 2 is the maximum possible value for nums[2].

Time and Space Complexity

• Brute-Force Approach:
  • Check every possible value for nums[index] up to maxSum: O(maxSum).
  • For each, sum up the array: O(n).
  • Total: O(n * maxSum), which is not feasible for large inputs.
• Optimized Approach (Binary Search):
  • Binary search over possible values: O(log(maxSum)).
  • For each guess, compute sum in O(1) time (using math formulas for arithmetic sequences).
  • Total: O(log(maxSum)) time, O(1) space.

The optimized approach is extremely efficient, even for large n and maxSum.

Summary

The problem asks us to maximize a specific value in an array under sum and positivity constraints. By recognizing that the optimal solution forms a "mountain" shape centered at the target index (decreasing by 1 as far as possible), we can use binary search and mathematical sum formulas to efficiently find the answer. The key insight is to avoid constructing the array and instead compute the minimal sum needed for any candidate value, allowing a fast and elegant solution.