Maximum Value at a Given Index in a Bounded Array solution and explanation
IBM
Google
9 more videos on this problem
LeetCode 1802. Maximum Value at a Given Index in a Bounded Array | Weekly Contest 233 🏆 | ExplainedCherry Coding [IIT-G] · 12:18 · 14K views
Maximum Value at a Given Index in a Bounded Array | Detailed Explanation | GOOGLE | Leetcode-1802codestorywithMIK · 37:08 · 11K views
Maximum Value at a Given Index in a Bounded Array || Math || Binary Search || Leetcode 1802Aryan Mittal · 22:47 · 10K views
LeetCode 1802. Maximum Value at a Given Index in a Bounded ArrayHappy Coding · 17:53 · 5K views
Maximum Value at a Given Index in a Bounded Array | Leetcode - 1802Algorithms Made Easy · 18:19 · 3K views
LeetCode 1802 Maximum Value at a Given Index in a Bounded ArrayJeevan Kumar - Cracckify · 8:24 · 1K views
Maximum Value at a Given Index in a Bounded Array | Leetcode - 1802 | Binary SearchAlgorithms Made Easy · 16:29 · 1K views
1802. Maximum Value at a Given Index in a Bounded Array (Leetcode Medium)Programming Live with Larry · 29:59 · 1K views
1802. Maximum Value at a Given Index in a Bounded ArrayAyush Rao · 9:06 · 1K views
LeetCode 1802. Maximum Value at a Given Index in a Bounded Array | Weekly Contest 233宰相小甘罗 · 5:32 · 648 views
The 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 == nnums[i]is a positive integer where0 <= i < n.abs(nums[i] - nums[i+1]) <= 1where0 <= i < n-1.- The sum of all the elements of
numsdoes not exceedmaxSum. 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 <= 1090 <= index < n
Approach overview
Problem Overview: You need to build an array of length n where every element is at least 1, the total sum does not exceed maxSum, and the difference between adjacent elements is at most 1. The goal is to maximize the value at a given index. The challenge is distributing the remaining sum while maintaining the decreasing-by-one constraint away from the index.
Approach 1: Greedy Incremental Construction (O(n * value), O(1) space)
This approach simulates building the array by increasing the value at index step by step. Each time you increase the center value, you extend decreasing values to the left and right while ensuring every element remains at least 1. The required sum forms a pyramid-like structure where values drop by one as you move away from the peak. For each candidate height, compute how much sum the left and right sides require. Stop once the total exceeds maxSum. This approach is intuitive and useful for understanding the structure of the optimal array, but repeated calculations make it inefficient when maxSum is large.
Approach 2: Binary Search with Greedy Sum Calculation (O(log maxSum), O(1) space)
The optimal strategy uses binary search on the value at index. Instead of constructing arrays, guess a candidate value x and check if it is feasible within maxSum. The key observation: the left and right sides form decreasing sequences starting from x-1. If the sequence reaches 1 before covering all positions, the remaining elements stay at 1. Using arithmetic progression formulas, you can compute the required sum for both sides in constant time. Combine left sum, right sum, and the center value, then compare against maxSum. If the sum fits, increase the search range; otherwise decrease it. This transforms a potentially large search space into logarithmic iterations.
The feasibility check is essentially a small greedy calculation: always place the highest possible values near the target index and decrease outward while respecting the constraints. No explicit array is required—only arithmetic sums.
Recommended for interviews: Binary search with greedy validation. Interviewers expect you to recognize the monotonic property: if value x is feasible, all values smaller than x are also feasible. Demonstrating the greedy sum calculation shows strong understanding of constrained array construction and array optimization patterns. The incremental approach helps explain the intuition, but the binary search solution is what most interviewers want to see.
Approach 1: Binary Search Approach
The binary search approach focuses on maximizing `nums[index]` while maintaining the constraints. We consider `nums[index]` as the peak of a potential 'pyramid' in the array. By conducting a binary search on possible values for `nums[index]`, we iterate through and check whether the constraints on both sides of the index and the sum are maintained.
Each mid value tested in the binary search represents the height of the peak at index. For each mid value, we compute the minimum sum required for both sides of the index.
If the calculated sum is within `maxSum`, the peak can be higher, leading us to the right half (mid + 1) of our binary search space. Otherwise, we try smaller values by searching the left half.
def sum_left(index, value):
if value > index:
count = value - index
return (value + (value - index - 1)) * index // 2 + count
else:
return value * (value + 1) // 2 + (index - value + 1)
def sum_right(n, index, value):
right_index = n - index - 1
if value > right_index:
count = value - right_index
return (value + (value - right_index - 1)) * right_index // 2 + count
else:
return value * (value + 1) // 2 + (right_index - value + 1)
def max_value(n, index, max_sum):
left, right = 1, max_sum + 1
while left < right:
mid = left + (right - left) // 2
total_sum = mid + sum_left(index, mid) + sum_right(n, index, mid)
if total_sum <= max_sum:
left = mid + 1
else:
right = mid
return left - 1
n = 6
index = 1
max_sum = 10
print(max_value(n, index, max_sum))public class MaximumValue {
private static long sumLeft(int index, int value) {
if (value > index) {
int count = value - index;
return ((long) value + (value - index - 1)) * index / 2 + count;
} else {
return (long) value * (value + 1) / 2 + (index - value + 1);
}
}
private static long sumRight(int n, int index, int value) {
int rightIndex = n - index - 1;
if (value > rightIndex) {
int count = value - rightIndex;
return ((long) value + (value - rightIndex - 1)) * rightIndex / 2 + count;
} else {
return (long) value * (value + 1) / 2 + (rightIndex - value + 1);
}
}
public static int maxValue(int n, int index, int maxSum) {
int left = 1, right = maxSum + 1;
while (left < right) {
int mid = left + (right - left) / 2;
long sum = mid + sumLeft(index, mid) + sumRight(n, index, mid);
if (sum <= maxSum) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
public static void main(String[] args) {
int n = 6, index = 1, maxSum = 10;
System.out.println(maxValue(n, index, maxSum));
}
}#include <iostream>
using namespace std;
long long sumLeft(int index, int value) {
if (value > index) {
long long count = value - index;
return static_cast<long long>(value + (value - index - 1)) * index / 2 + count;
} else {
return static_cast<long long>(value * (value + 1)) / 2 + (index - value + 1);
}
}
long long sumRight(int n, int index, int value) {
int rightIndex = n - index - 1;
if (value > rightIndex) {
long long count = value - rightIndex;
return static_cast<long long>(value + (value - rightIndex - 1)) * rightIndex / 2 + count;
} else {
return static_cast<long long>(value * (value + 1)) / 2 + (rightIndex - value + 1);
}
}
int maxValue(int n, int index, int maxSum) {
int left = 1, right = maxSum + 1;
while (left < right) {
int mid = left + (right - left) / 2;
long long sum = mid + sumLeft(index, mid) + sumRight(n, index, mid);
if (sum <= maxSum) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
int main() {
int n = 6, index = 1, maxSum = 10;
cout << maxValue(n, index, maxSum) << endl;
return 0;
}function sumLeft(index, value) {
if (value > index) {
const count = value - index;
return (value + (value - index - 1)) * index / 2 + count;
} else {
return value * (value + 1) / 2 + (index - value + 1);
}
}
function sumRight(n, index, value) {
const rightIndex = n - index - 1;
if (value > rightIndex) {
const count = value - rightIndex;
return (value + (value - rightIndex - 1)) * rightIndex / 2 + count;
} else {
return value * (value + 1) / 2 + (rightIndex - value + 1);
}
}
function maxValue(n, index, maxSum) {
let left = 1, right = maxSum + 1;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
const sum = mid + sumLeft(index, mid) + sumRight(n, index, mid);
if (sum <= maxSum) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
const n = 6, index = 1, maxSum = 10;
console.log(maxValue(n, index, maxSum));#include <stdio.h>
#include <stdlib.h>
int sumLeft(int index, int value) {
if (value > index) {
int count = (value - index);
return (value + (value - index - 1)) * index / 2 + count;
} else {
return (value * (value + 1)) / 2 + (index - value + 1);
}
}
int sumRight(int n, int index, int value) {
int rightIndex = n - index - 1;
if (value > rightIndex) {
int count = (value - rightIndex);
return (value + (value - rightIndex - 1)) * rightIndex / 2 + count;
} else {
return (value * (value + 1)) / 2 + (rightIndex - value + 1);
}
}
int maxValue(int n, int index, int maxSum) {
int left = 1, right = maxSum + 1;
while (left < right) {
int mid = left + (right - left) / 2;
int sum = mid + sumLeft(index, mid) + sumRight(n, index, mid);
if (sum <= maxSum) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
int main() {
int n = 6, index = 1, maxSum = 10;
printf("%d\n", maxValue(n, index, maxSum));
return 0;
}using System;
public class Solution {
private static long SumLeft(int index, int value) {
if (value > index) {
long count = value - index;
return (value + (value - index - 1)) * index / 2 + count;
} else {
return (long)value * (value + 1) / 2 + (index - value + 1);
}
}
private static long SumRight(int n, int index, int value) {
int rightIndex = n - index - 1;
if (value > rightIndex) {
long count = value - rightIndex;
return (value + (value - rightIndex - 1)) * rightIndex / 2 + count;
} else {
return (long)value * (value + 1) / 2 + (rightIndex - value + 1);
}
}
public static int MaxValue(int n, int index, int maxSum) {
int left = 1, right = maxSum + 1;
while (left < right) {
int mid = left + (right - left) / 2;
long sum = mid + SumLeft(index, mid) + SumRight(n, index, mid);
if (sum <= maxSum) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
public static void Main() {
int n = 6, index = 1, maxSum = 10;
Console.WriteLine(MaxValue(n, index, maxSum));
}
}In this Python solution, we define two helper functions analogous to those in other languages for calculating the sum of sections left and right of the index. A binary search is used to find the optimal peak at the specified index.
Time complexity: O(log(maxSum)) - Due to the binary search over the range of possible values.
Space complexity: O(1) - Space used is constant, barring input and output variables.
Approach 2: Greedy Incremental Construction Approach
This approach involves incrementally building the array by focusing solely on maximizing `nums[index]` using a greedy construction. This directly extends from index to balance the array's condition and sum constraints effectively, utilizing the available sum step-by-step. We increment each value symmetrically from the index point, considering both left and right constraints and ensuring all steps preserve the `abs(nums[i] - nums[i+1]) <= 1` condition.
We keep track of increments needed and subtract from `maxSum` accordingly, thereby implicitly maximizing `nums[index]` while maintaining valid conditions.
def max_value(n, index, max_sum):
left, right = index, index
current_value, sum_ = 1, n
while sum_ + right - left <= max_sum:
sum_ += (right - left + 1)
current_value += 1
if left > 0: left -= 1
if right < n - 1: right += 1
if left == 0 and right == n - 1:
added = (max_sum - sum_) // n
return current_value + added
return current_value
n = 6
index = 1
max_sum = 10
print(max_value(n, index, max_sum))public class Solution {
public static int maxValue(int n, int index, int maxSum) {
int left = index, right = index;
int currentValue = 1, sum = n;
while (sum + right - left <= maxSum) {
sum += (right - left + 1);
currentValue++;
if (left > 0) left--;
if (right < n - 1) right++;
if (left == 0 && right == n - 1) {
int added = (maxSum - sum) / n;
return currentValue + added;
}
}
return currentValue;
}
public static void main(String[] args) {
int n = 6, index = 1, maxSum = 10;
System.out.println(maxValue(n, index, maxSum));
}
}#include <iostream>
using namespace std;
int maxValue(int n, int index, int maxSum) {
int left = index, right = index;
int currentValue = 1, sum = n;
while (sum + right - left <= maxSum) {
sum += (right - left + 1);
currentValue++;
if (left > 0) left--;
if (right < n - 1) right++;
if (left == 0 && right == n - 1) {
int added = (maxSum - sum) / n;
return currentValue + added;
}
}
return currentValue;
}
int main() {
int n = 6, index = 1, maxSum = 10;
cout << maxValue(n, index, maxSum) << endl;
return 0;
}function maxValue(n, index, maxSum) {
let left = index, right = index;
let currentValue = 1, sum = n;
while (sum + right - left <= maxSum) {
sum += (right - left + 1);
currentValue++;
if (left > 0) left--;
if (right < n - 1) right++;
if (left === 0 && right === n - 1) {
const added = Math.floor((maxSum - sum) / n);
return currentValue + added;
}
}
return currentValue;
}
const n = 6, index = 1, maxSum = 10;
console.log(maxValue(n, index, maxSum));#include <stdio.h>
int maxValue(int n, int index, int maxSum) {
int left = index, right = index;
int currentValue = 1, sum = n;
while (sum + right - left <= maxSum) {
sum += (right - left + 1);
currentValue++;
if (left > 0) left--;
if (right < n - 1) right++;
if (left == 0 && right == n - 1) {
int added = (maxSum - sum) / n;
return currentValue + added;
}
}
return currentValue;
}
int main() {
int n = 6, index = 1, maxSum = 10;
printf("%d\n", maxValue(n, index, maxSum));
return 0;
}using System;
public class Solution {
public static int MaxValue(int n, int index, int maxSum) {
int left = index, right = index;
int currentValue = 1, sum = n;
while (sum + right - left <= maxSum) {
sum += (right - left + 1);
currentValue++;
if (left > 0) left--;
if (right < n - 1) right++;
if (left == 0 && right == n - 1) {
int added = (maxSum - sum) / n;
return currentValue + added;
}
}
return currentValue;
}
public static void Main() {
int n = 6, index = 1, maxSum = 10;
Console.WriteLine(MaxValue(n, index, maxSum));
}
}The Python solution applies a logical approach to extend the array incrementally, ensuring conditions are met and maximizing within available sum across boundaries centered at index.
Time complexity: O(n) - Progressively covers all possible incremental moves within given span.
Space complexity: O(1) - Simplistic constant-space operation.
Approach 3: Binary Search
According to the problem description, if we determine the value of nums[index] as x, we can find a minimum array sum. That is, the elements on the left side of index in the array decrease from x-1 to 1, and if there are remaining elements, the remaining elements are all 1; similarly, the elements at index and on the right side of the array decrease from x to 1, and if there are remaining elements, the remaining elements are all 1.
In this way, we can calculate the sum of the array. If the sum is less than or equal to maxSum, then the current x is valid. As x increases, the sum of the array will also increase, so we can use the binary search method to find the maximum x that meets the conditions.
To facilitate the calculation of the sum of the elements on the left and right sides of the array, we define a function sum(x, cnt), which represents the sum of an array with cnt elements and a maximum value of x. The function sum(x, cnt) can be divided into two cases:
- If
x geq cnt, then the sum of the array is\frac{(x + x - cnt + 1) times cnt}{2} - If
x \lt cnt, then the sum of the array is\frac{(x + 1) times x}{2} + cnt - x
Next, define the left boundary of the binary search as left = 1, the right boundary as right = maxSum, and then binary search for the value mid of nums[index]. If sum(mid - 1, index) + sum(mid, n - index) leq maxSum, then the current mid is valid, we can update left to mid, otherwise we update right to mid - 1.
Finally, return left as the answer.
The time complexity is O(log M), where M=maxSum. The space complexity is O(1).
func maxValue(n int, index int, maxSum int) int {
sum := func(x, cnt int) int {
if x >= cnt {
return (x + x - cnt + 1) * cnt / 2
}
return (x+1)*x/2 + cnt - x
}
return sort.Search(maxSum, func(x int) bool {
x++
return sum(x-1, index)+sum(x, n-index) > maxSum
})
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time complexity: O(log(maxSum)) - Due to the binary search over the range of possible values. Space complexity: O(1) - Space used is constant, barring input and output variables. |
| Greedy Incremental Construction Approach | Time complexity: O(n) - Progressively covers all possible incremental moves within given span. Space complexity: O(1) - Simplistic constant-space operation. |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Incremental Construction | O(n * value) | O(1) | Useful for understanding the pyramid structure and constraints during initial reasoning |
| Binary Search with Greedy Sum Check | O(log maxSum) | O(1) | Best approach for large constraints; standard interview solution |
Frequently asked questions
Is Maximum Value at a Given Index in a Bounded Array easy or hard?
The problem is rated Medium because the constraints push you toward a binary search on the answer rather than direct simulation. Recognizing the monotonic feasibility condition and deriving the arithmetic sum formula is the main challenge.
Maximum Value at a Given Index in a Bounded Array Python/Java solution
Most implementations follow the same binary search template across languages. Python, Java, C++, JavaScript, and C# versions all compute the left and right decreasing sums using arithmetic progression formulas and adjust the search range based on feasibility.
How to solve Maximum Value at a Given Index in a Bounded Array in O(log n)?
Use binary search on the candidate value at the given index. For each guess x, compute the minimum sum needed to build decreasing sequences on the left and right sides while keeping elements at least 1. If the total sum is within maxSum, increase the search range; otherwise decrease it. This results in O(log maxSum) complexity.
What is the best approach for Maximum Value at a Given Index in a Bounded Array?
Binary search with a greedy feasibility check is the most efficient approach. You binary search the value at the target index and compute the minimum sum required for the rest of the array using decreasing sequences. Each feasibility check runs in O(1), leading to overall O(log maxSum) time and O(1) space.
Is Maximum Value at a Given Index in a Bounded Array asked at Google/Amazon/Meta?
Array optimization and binary search on answer problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. The pattern of checking feasibility with a monotonic condition is especially common in system and algorithm interviews.
What data structure is used in Maximum Value at a Given Index in a Bounded Array?
The solution primarily relies on arithmetic calculations and binary search rather than complex data structures. The array itself is conceptual; you compute the required sums mathematically instead of building the full array.
What is the time complexity of Maximum Value at a Given Index in a Bounded Array?
The optimal solution runs in O(log maxSum) time using binary search on the possible value at the index. Each step calculates the required sum using arithmetic formulas in constant time. Space complexity remains O(1) because no additional data structures are required.