Scale Engineer

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
MathGreedy
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 <= 109
  • 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.

class Solution {    public int maxValue(int n, int index, int maxSum) {        for (int x = maxSum; x >= 1; --x) {            if (getMinSum(n, index, x) <= maxSum) {                return x;            }        }        return 0; // Should not be reached given constraints    }     private long getMinSum(int n, int index, int val) {        long totalSum = val;        totalSum += calculateSideSum(index, val);        totalSum += calculateSideSum(n - 1 - index, val);        return totalSum;    }     private long calculateSideSum(long count, int val) {        long m = val - 1;        long sum = 0;        if (count >= m) {            // Sequence goes down to 1, then flat at 1s            sum = m * (m + 1) / 2;            sum += (count - m);        } else {            // Sequence is an arithmetic progression that doesn't reach 1            long first = m;            long last = m - count + 1;            sum = count * (first + last) / 2;        }        return sum;    }}

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.

Solutions

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;  }}

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 →

Next problem