Maximum Value at a Given Index in a Bounded Array

Maximum Value at a Given Index in a Bounded Array - Problem

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: abs(x) equals x if x >= 0, and -x otherwise.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: The optimal array is [1,1,2,1]. The peak value 2 at index 2 satisfies all constraints: adjacent differences ≤ 1, sum = 5 ≤ 6, and 2 is maximized.

Example 2 — Edge Position

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

› Output: 3

💡 Note: The optimal array is [2,3,2,1,1,1]. Peak at index 1 has value 3, sum = 10 ≤ 10, adjacent differences ≤ 1.

Example 3 — Minimum Sum

$ Input: n = 3, index = 0, maxSum = 3

› Output: 1

💡 Note: With minimum possible sum, the array is [1,1,1]. Peak at index 0 has value 1, sum = 3 = maxSum.

Constraints

1 ≤ n ≤ 10⁹
0 ≤ index < n
1 ≤ maxSum ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

n=4, index=2, maxSum=6

Process

Build mountain with peak at index 2

Output

Maximum value 2 at index 2

Key Takeaway

🎯 Key Insight: The optimal array forms a mountain with the peak at the given index, and binary search efficiently finds the maximum valid peak height.

Asked in

G Google 15 M Microsoft 12

The key insight is that the optimal array forms a mountain shape with the peak at the given index, decreasing by 1 each step away from the peak. Best approach uses binary search on the peak height. Time: O(log maxSum), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Heights	O(maxSum × n)	O(1)	Try every possible height for nums[index] and check if valid array can be constructed
Binary Search on Answer	O(log maxSum)	O(1)	Binary search on the peak height to find the maximum valid value efficiently

Brute Force - Try All Heights — Algorithm Steps

Try heights from maxSum down to 1
For each height, calculate minimum sum needed
Return the first height that fits within maxSum

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Height

Test if peak height works

Calculate

Compute minimum sum needed

Check

Verify sum ≤ maxSum

Code -

solution.c — C

#include <stdio.h>

long long calculateSum(int peakHeight, int n, int index) {
    long long total = peakHeight;
    
    // Calculate sum for left side
    int leftCount = index;
    if (peakHeight > leftCount) {
        total += (long long)(2 * peakHeight - leftCount - 1) * leftCount / 2;
    } else {
        total += (long long)(peakHeight - 1) * peakHeight / 2;
        total += leftCount - (peakHeight - 1);
    }
    
    // Calculate sum for right side
    int rightCount = n - index - 1;
    if (peakHeight > rightCount) {
        total += (long long)(2 * peakHeight - rightCount - 1) * rightCount / 2;
    } else {
        total += (long long)(peakHeight - 1) * peakHeight / 2;
        total += rightCount - (peakHeight - 1);
    }
    
    return total;
}

int solution(int n, int index, int maxSum) {
    // Try heights from maxSum down to 1
    for (int height = maxSum; height >= 1; height--) {
        if (calculateSum(height, n, index) <= maxSum) {
            return height;
        }
    }
    return 1;
}

int main() {
    int n, index, maxSum;
    scanf("%d", &n);
    scanf("%d", &index);
    scanf("%d", &maxSum);
    
    int result = solution(n, index, maxSum);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(maxSum × n)

Try up to maxSum heights, each requiring O(n) to calculate sum

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for calculation

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

876 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Heights — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler