Maximum Value at a Given Index in a Bounded Array

Med

#1648Time: O(maxSum) - In the worst-case scenario, the loop runs from `maxSum` down to the actual answer. Since `maxSum` can be up to 10^9, this is not feasible.Space: O(1) - Constant extra space is used.1 company

Patterns

Math Greedy

Algorithms

Binary Search

Companies

ByteDance

Prompt

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 <= 10⁹
0 <= index < n

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but inefficient approach is to check every possible value for nums[index] starting from the largest possible (maxSum) down to the smallest (1). The first value that satisfies the sum constraint is the answer. This method exhaustively checks all potential answers in a linear fashion.

Algorithm

Iterate through all possible values for nums[index] from maxSum down to 1. Let's call the current candidate value x.
For each x, calculate the minimum possible sum of the array. This minimum sum is achieved when the array forms a pyramid shape with x at index, and values decrease by 1 on both sides until they reach 1.
The function getMinSum(n, index, x) is used to calculate this sum. It computes the sum of the peak x, the sum of the left side, and the sum of the right side.
If getMinSum(n, index, x) is less than or equal to maxSum, it means x is a valid value for nums[index]. Since we are iterating downwards, this is the highest possible valid value.
Return x as soon as a valid one is found.

Walkthrough

The core of the problem is to find the maximum value x for nums[index] such that an array satisfying all conditions can be constructed. To maximize x, we must minimize the sum of all other elements. The condition abs(nums[i] - nums[i+1]) <= 1 implies that the smallest possible sum for a given nums[index] = x occurs when the array values form a pyramid shape centered at index. The values decrease by 1 as we move away from the index in either direction, until they hit the minimum allowed value of 1, after which they remain 1.

This brute-force approach iterates through every possible value for x from maxSum down to 1. For each x, it calculates the minimum sum of such a pyramid-shaped array. If this sum is within the maxSum limit, we have found our answer because we are checking in decreasing order.

1class Solution {2    public int maxValue(int n, int index, int maxSum) {3        for (int x = maxSum; x >= 1; --x) {4            if (getMinSum(n, index, x) <= maxSum) {5                return x;6            }7        }8        return 0; // Should not be reached given constraints9    }10 11    private long getMinSum(int n, int index, int val) {12        long totalSum = val;13        totalSum += calculateSideSum(index, val);14        totalSum += calculateSideSum(n - 1 - index, val);15        return totalSum;16    }17 18    private long calculateSideSum(long count, int val) {19        long m = val - 1;20        long sum = 0;21        if (count >= m) {22            // Sequence goes down to 1, then flat at 1s23            sum = m * (m + 1) / 2;24            sum += (count - m);25        } else {26            // Sequence is an arithmetic progression that doesn't reach 127            long first = m;28            long last = m - count + 1;29            sum = count * (first + last) / 2;30        }31        return sum;32    }33}

Complexity

Time

O(maxSum) - In the worst-case scenario, the loop runs from `maxSum` down to the actual answer. Since `maxSum` can be up to 10^9, this is not feasible.

Space

O(1) - Constant extra space is used.

Trade-offs

Pros

Simple to understand and implement.

Cons

Extremely inefficient for large inputs.
Will result in a 'Time Limit Exceeded' error on most platforms due to the large constraints on maxSum.

A highly efficient approach utilizes binary search on the possible values of nums[index]. The key observation is that the total sum of the array is a monotonically increasing function of nums[index]. If we can construct an array with nums[index] = x that satisfies the sum constraint, we can certainly do so for any value less than x. This monotonicity allows us to efficiently search for the maximum possible value.

Algorithm

Observe that if a value x is achievable for nums[index], any value smaller than x is also achievable. This monotonic property allows for binary search on the answer.
To simplify calculations, transform the problem. Instead of an array of positive integers summing to maxSum, consider an array of non-negative integers a[i] = nums[i] - 1 summing to maxSum - n. We want to maximize a[index]. Let peak = a[index].
The search space for peak is from 0 to maxSum - n.
Perform a binary search on this range. For each mid value (a candidate for peak):
- Calculate the minimum sum of the array a. This sum is a pyramid with a[index] = mid, and values a[i] = max(0, mid - |i - index|). The sum can be calculated using arithmetic series formulas.
- This involves summing the peak value, the sum of the left side, and the sum of the right side.
If the calculated sum is less than or equal to maxSum - n, it means mid is a possible peak. We try for a larger peak, so we set ans = mid and low = mid + 1.
If the sum is greater, mid is too large. We search in the lower half by setting high = mid - 1.
The final result for nums[index] is ans + 1.

Walkthrough

To find the maximum nums[index], we must minimize the sum of the array. This is achieved by creating a pyramid-like structure where nums[index] is the peak, and values decrease by 1 as we move away from index until they reach 1.

A clever simplification is to subtract n from maxSum. This is equivalent to considering an array a where a[i] = nums[i] - 1 >= 0, and the sum of a must not exceed maxSum - n. Our goal is to maximize a[index]. Let's call this maximum value peak. The array a will have a shape a[i] = max(0, peak - |i - index|). The sum of a is a monotonic function of peak, making it ideal for binary search.

The search space for peak is [0, maxSum - n]. We use binary search to find the largest peak for which the sum of the corresponding array a does not exceed maxSum - n.

The sum of the pyramid a is peak plus the sums of the left and right sides. The sum of a side with count elements and a starting value of peak - 1 can be calculated using formulas for arithmetic series. Special care must be taken for potential integer overflows by using long for sum calculations.

1class Solution {2    public int maxValue(int n, int index, int maxSum) {3        long newMaxSum = (long)maxSum - n;4        long low = 0, high = newMaxSum;5        long ans = 0;6 7        while (low <= high) {8            long mid = low + (high - low) / 2;9            long currentSum = calculatePyramidSum(mid, index, n);10            11            if (currentSum <= newMaxSum) {12                ans = mid;13                low = mid + 1;14            } else {15                high = mid - 1;16            }17        }18        19        return (int)(ans + 1);20    }21 22    private long calculatePyramidSum(long peak, int index, int n) {23        long sum = peak;24        long leftCount = index;25        long rightCount = n - 1 - index;26 27        // Calculate sum of the left side28        if (leftCount >= peak) {29            // Sum of peak-1, peak-2, ..., 1, 0, ...30            // This is the sum of numbers from 1 to peak-1.31            sum += peak * (peak - 1) / 2;32        } else {33            // Sum of peak-1, peak-2, ..., peak-leftCount34            long first = peak - 1;35            long last = peak - leftCount;36            sum += leftCount * (first + last) / 2;37        }38 39        // Calculate sum of the right side40        if (rightCount >= peak) {41            // Sum of peak-1, peak-2, ..., 1, 0, ...42            sum += peak * (peak - 1) / 2;43        } else {44            long first = peak - 1;45            long last = peak - rightCount;46            sum += rightCount * (first + last) / 2;47        }48        49        return sum;50    }51}

Complexity

Time

O(log(maxSum)) - The binary search is performed on a range of values up to `maxSum`. Each check inside the binary search takes constant time.

Space

O(1) - We only use a few variables for the binary search, resulting in constant space usage.

Trade-offs

Pros

Highly efficient with logarithmic time complexity.
Optimal solution that passes for all given constraints.

Cons

The logic for calculating the pyramid sum can be tricky to get right.
Requires careful handling of large numbers using long to prevent integer overflow.

Solutions

Solution

1class Solution {2public3  int maxValue(int n, int index, int maxSum) {4    int left = 1, right = maxSum;5    while (left < right) {6      int mid = (left + right + 1) >>> 1;7      if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {8        left = mid;9      } else {10        right = mid - 1;11      }12    }13    return left;14  }15private16  long sum(long x, int cnt) {17    return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;18  }19}

1class Solution:2    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

1class Solution {2public:3  int maxValue(int n, int index, int maxSum) {4    auto sum = [](long x, int cnt) {5      return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;6    };7    int left = 1, right = maxSum;8    while (left < right) {9      int mid = (left + right + 1) >> 1;10      if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {11        left = mid;12      } else {13        right = mid - 1;14      }15    }16    return left;17  }18};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem