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 where 0 <= i < n.abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.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 <= 1090 <= index < nThe 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.
The implementation defines two helper functions to calculate the sum of the left and right parts of the array relative to the index.
We use a binary search within the range of 1 to `maxSum` to find the maximum possible value at `nums[index]` that satisfies the given constraints.
C++
Java
Python
C#
JavaScript
Time complexity: O(log(maxSum)) - Binary search divides the range of possible peak values logarithmically.
Space complexity: O(1) - Uses a constant amount of space.
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.
The C solution incrementally grows `nums[index]` by extending left and right, maintaining conditions while increasing as much as possible under given max sum.
C++
Java
Python
C#
JavaScript
Time complexity: O(n) - Incrementally checks and adjusts values from center to borders of the array.
Space complexity: O(1) - Constant space used without additional data structures.
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time complexity: O(log(maxSum)) - Binary search divides the range of possible peak values logarithmically. Space complexity: O(1) - Uses a constant amount of space. |
| Greedy Incremental Construction Approach | Time complexity: O(n) - Incrementally checks and adjusts values from center to borders of the array. Space complexity: O(1) - Constant space used without additional data structures. |
LeetCode 1802. Maximum Value at a Given Index in a Bounded Array | Weekly Contest 233 🏆 | Explained • Cherry Coding [IIT-G] • 13,738 views views
Watch 9 more video solutions →Practice Maximum Value at a Given Index in a Bounded Array with our built-in code editor and test cases.
Practice on FleetCode