LeetCode Problem 1802

Difficulty: 🟡 Medium
Topics: Math, Binary Search, Greedy

Solution

LeetCode 1802, Maximum Value at a Given Index in a Bounded Array

Problem Understanding

This problem asks us to construct an array of length n where every element is a positive integer, the difference between adjacent elements is at most 1, and the total sum of the array does not exceed maxSum.

Among all valid arrays, we want to maximize the value at a specific position, index.

The adjacency constraint is especially important:

abs(nums[i] - nums[i+1]) <= 1

This means values cannot jump sharply between neighboring positions. If one element is large, nearby elements must also be relatively large. For example, if nums[index] = 5, then the adjacent values can only be 4, 5, or 6. Since we want the smallest possible total sum while keeping the peak high, the optimal structure naturally forms a pyramid-like shape centered at index.

The input consists of:

• n, the length of the array
• index, the position we want to maximize
• maxSum, the upper bound on the total array sum

The output is a single integer:

• The maximum possible value of nums[index]

The constraints are extremely large:

1 <= n <= maxSum <= 10^9

This immediately tells us that constructing arrays explicitly or using simulation-based approaches will be too slow. Any solution worse than logarithmic or near-logarithmic time is unlikely to pass.

There are several important edge cases to keep in mind.

If n = 1, then the entire array contains only one value, so the answer is simply maxSum.

If index = 0 or index = n - 1, then the pyramid extends only in one direction. The logic must still work correctly for these boundary positions.

Another tricky case occurs when the decreasing sequence reaches 1 before covering all positions. Since every element must remain positive, remaining positions must be filled with 1s instead of continuing downward into zero or negative values.

Finally, because sums can become very large, integer overflow is a concern in languages like Go. We must use 64-bit integers during calculations.

Approaches

Brute Force Approach

A brute-force strategy would try every possible value for nums[index] and determine whether a valid array can be constructed within the sum limit.

For a candidate value x, we could explicitly build the smallest valid array centered at index:

• Start with x at index
• Decrease by 1 moving outward
• Stop decreasing at 1
• Fill remaining positions with 1

Then compute the total sum and check whether it exceeds maxSum.

This approach is correct because the minimal valid array for a fixed peak value always uses the steepest possible decrease toward 1. Any larger neighboring values would only increase the total sum unnecessarily.

However, this method is too slow if implemented naively. The candidate value may be as large as 10^9, and constructing arrays repeatedly would require linear work each time.

Key Insight

The critical observation is that if a value x is feasible at index, then every smaller value is also feasible.

This creates a monotonic condition:

If x works, then all values <= x also work.

Whenever a problem has a monotonic feasibility property, binary search becomes a strong candidate.

The next insight is that we do not need to explicitly build the array. We only need to compute the minimum possible sum required for a chosen peak value.

The optimal array shape forms two arithmetic sequences extending left and right from the peak. Using arithmetic progression formulas, we can compute the required sum in constant time.

This reduces the solution to:

1. Binary search the answer
2. Efficiently compute whether a candidate peak value fits within maxSum

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × maxSum)	O(n)	Explicitly constructs arrays for each candidate value
Optimal	O(log maxSum)	O(1)	Uses binary search with arithmetic series formulas

Algorithm Walkthrough

1. Observe that for a fixed peak value x, the minimum valid array is obtained by decreasing by 1 as we move away from index.
2. For the left side of the peak, compute the minimum sum required for index positions.

If the peak is large enough, we can form a complete descending sequence:

x-1, x-2, x-3, ...

Otherwise, the sequence reaches 1 early, and the remaining positions are filled with 1s. 3. Perform the same calculation for the right side, which contains n - index - 1 positions. 4. Add:

• the peak value x
• the left-side contribution
• the right-side contribution

This gives the minimum possible total sum for a peak of x. 5. Compare this required sum against maxSum.

• If the sum is within the limit, then x is feasible.
• Otherwise, x is too large.

6. Since feasibility is monotonic, apply binary search over the range:

[1, maxSum]

7. During binary search:

• If mid is feasible, store it as a candidate answer and search higher.
• Otherwise, search lower.

8. Continue until the search interval is exhausted.
9. Return the largest feasible value found.

Why it works

For any fixed peak value, the smallest possible valid array is uniquely determined by decreasing values outward as aggressively as allowed. Any other arrangement would increase the total sum while keeping the same peak.

Because feasibility depends monotonically on the peak value, binary search correctly finds the maximum feasible value.

The arithmetic progression formulas compute the exact minimal required sum, so every feasibility check is accurate.

Python Solution

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        
        def side_sum(peak: int, length: int) -> int:
            if peak > length:
                smallest = peak - length
                return (peak - 1 + smallest) * length // 2
            else:
                descending_sum = (peak - 1 + 1) * (peak - 1) // 2
                ones_needed = length - (peak - 1)
                return descending_sum + ones_needed
        
        def can_build(value: int) -> bool:
            total = value
            
            total += side_sum(value, index)
            total += side_sum(value, n - index - 1)
            
            return total <= maxSum
        
        left = 1
        right = maxSum
        answer = 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if can_build(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return answer

The implementation begins with the helper function side_sum, which computes the minimum sum needed on one side of the peak.

The parameter peak represents the value at nums[index], while length represents how many positions exist on that side.

There are two cases.

If the decreasing sequence does not reach 1, then the side forms a complete arithmetic progression. The code uses the arithmetic series formula to compute the sum directly.

If the sequence reaches 1 before covering all positions, then the remaining positions are filled with 1s. The code computes the descending portion separately and adds the extra ones.

The can_build function computes the total minimum required sum for a candidate peak value. It includes:

• the peak itself
• the left-side contribution
• the right-side contribution

If this total is within maxSum, the candidate value is feasible.

The main algorithm performs binary search over possible peak values. Whenever a candidate works, the algorithm attempts a larger value. Otherwise, it reduces the search range.

Because each feasibility check runs in constant time, the entire solution is extremely efficient.

Go Solution

func maxValue(n int, index int, maxSum int) int {
    
    sideSum := func(peak int64, length int64) int64 {
        if peak > length {
            smallest := peak - length
            return (peak - 1 + smallest) * length / 2
        }
        
        descendingSum := (peak - 1 + 1) * (peak - 1) / 2
        onesNeeded := length - (peak - 1)
        
        return descendingSum + onesNeeded
    }
    
    canBuild := func(value int64) bool {
        total := value
        
        total += sideSum(value, int64(index))
        total += sideSum(value, int64(n-index-1))
        
        return total <= int64(maxSum)
    }
    
    left := int64(1)
    right := int64(maxSum)
    answer := int64(1)
    
    for left <= right {
        mid := (left + right) / 2
        
        if canBuild(mid) {
            answer = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return int(answer)
}

The Go implementation follows the same logic as the Python version, but there is one important difference.

All arithmetic uses int64 instead of int because sums can exceed the range of 32-bit integers. Without this conversion, overflow could produce incorrect results for large inputs.

Other than the explicit integer type handling, the algorithm structure remains identical.

Worked Examples

Example 1

Input: n = 4, index = 2, maxSum = 6

We binary search for the largest feasible peak value.

Check value = 2

Array shape:

[1, 2, 2, 1]

Component	Value
Peak	2
Left side	1 + 2
Right side	1
Total	6

Since 6 <= maxSum, value 2 is feasible.

Check value = 3

Minimal valid shape:

[1, 2, 3, 2]

Component	Value
Peak	3
Left side	1 + 2
Right side	2
Total	8

Since 8 > maxSum, value 3 is not feasible.

Therefore, the answer is:

2

Example 2

Input: n = 6, index = 1, maxSum = 10

Check value = 3

Minimal valid array:

[2, 3, 2, 1, 1, 1]

Component	Value
Peak	3
Left side	2
Right side	2 + 1 + 1 + 1
Total	10

This exactly matches maxSum, so 3 is feasible.

Check value = 4

Minimal valid array:

[3, 4, 3, 2, 1, 1]

Component	Value
Peak	4
Left side	3
Right side	3 + 2 + 1 + 1
Total	14

This exceeds maxSum, so 4 is not feasible.

Therefore, the answer is:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log maxSum)	Binary search performs logarithmic feasibility checks
Space	O(1)	Only a constant amount of extra memory is used

The binary search examines at most log2(maxSum) candidate values. Each feasibility check uses only arithmetic formulas and constant-time calculations.

No auxiliary arrays or data structures are allocated, so the space usage remains constant.

Test Cases

solution = Solution()

assert solution.maxValue(4, 2, 6) == 2  # provided example 1
assert solution.maxValue(6, 1, 10) == 3  # provided example 2

assert solution.maxValue(1, 0, 1) == 1  # single element minimum
assert solution.maxValue(1, 0, 1000000000) == 1000000000  # single element large value

assert solution.maxValue(3, 0, 3) == 1  # edge index at beginning
assert solution.maxValue(3, 2, 3) == 1  # edge index at end

assert solution.maxValue(3, 1, 5) == 2  # symmetric small case
assert solution.maxValue(5, 2, 15) == 4  # centered pyramid

assert solution.maxValue(8, 7, 14) == 4  # index at far right
assert solution.maxValue(8, 0, 14) == 4  # index at far left

assert solution.maxValue(5, 2, 5) == 1  # all ones only possible
assert solution.maxValue(10, 5, 100) == 12  # larger feasible peak

assert solution.maxValue(1000000000, 0, 1000000000) == 1  # huge input boundary

Test Summary

Test	Why
(4, 2, 6)	Validates provided example
(6, 1, 10)	Validates second example
(1, 0, 1)	Smallest possible input
(1, 0, 1000000000)	Single-element maximum boundary
(3, 0, 3)	Tests left boundary index
(3, 2, 3)	Tests right boundary index
(3, 1, 5)	Small symmetric configuration
(5, 2, 15)	Tests balanced pyramid growth
(8, 7, 14)	Tests peak at far right
(8, 0, 14)	Tests peak at far left
(5, 2, 5)	Only all-ones array possible
(10, 5, 100)	Larger nontrivial configuration
(1000000000, 0, 1000000000)	Extreme constraint validation

Edge Cases

One important edge case occurs when n = 1. In this situation, the array contains only one element, so there are no adjacency constraints to worry about. The answer is simply maxSum. The implementation handles this naturally because the side lengths become zero, and the binary search correctly expands to the maximum feasible value.

Another tricky case occurs when the decreasing sequence reaches 1 before covering all positions. For example, if the peak is 3 but one side has length 10, the sequence becomes:

2, 1, 1, 1, 1, ...

A buggy implementation might incorrectly continue decreasing into zero or negative values. The helper function explicitly handles this by separating the descending arithmetic sequence from the remaining 1s.

Boundary indices are also easy sources of mistakes. If index = 0 or index = n - 1, one side of the pyramid has length zero. Some implementations accidentally double count or access invalid positions in these cases. This solution avoids those issues because the helper function safely handles a side length of zero and returns zero contribution.