Maximum Value at a Given Index in a Bounded Array Solution
Maximum Value at a Given Index in a Bounded Array Problem Description:
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.
Examples:
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].
Input: n = 6, index = 1, maxSum = 10
Output: 3
Explanation: A possible array is [2, 3, 2, 1, 1, 1], satisfying all conditions. The sum is 10, which does not exceed maxSum = 10. No valid array allows nums[1] = 4 without exceeding the sum limit, so the maximum nums[1] is 3.
Constraints:
1 <= n <= maxSum <= 10⁹
0 <= index < n
Brute Force Approach
To approach the problem, we are given three positive integers: n, index, and maxSum, and we need to determine the maximum possible value of nums[index] while ensuring that the array satisfies given constraints. The array nums must have n elements, each a positive integer, with adjacent elements differing by at most 1, and the total sum of all elements cannot exceed maxSum.
Our goal is to find the maximum value of nums[index] while ensuring that the sum of the array remains within maxSum.
What can be the minimum value of nums[index]?
The minimum value of nums[index] should be 1, as each element in the array must be a positive integer. If we assume that all other elements in the array are 1 or only one element is present in the array i.e. 1, then 1 becomes the only possible maximum value that can be placed at nums[index].
What would be the maximum value of nums[index]?
The maximum possible value of nums[index] should be maxSum in the best-case scenario. This occurs when the entire sum is allocated to nums[index], and either the array has a size of 1 or no other elements are present besides nums[index].
Thus, our search space for nums[index] ranges from 1 to maxSum. The problem then reduces to finding the maximum possible nums[index] that satisfies all conditions.
A naive approach that comes to mind is to iterate from 1 to maxSum and check whether it's possible to construct an array satisfying the constraints. If it's possible, then it's a valid solution.
Consider n = 4, index = 2, maxSum = 6.
We start by setting the smallest possible value as 1 and the largest possible value as 6 (since maxSum = 6). We then check whether it is possible to construct the array for different values of nums[index]:
- If nums[index] = 1, we can construct an array like [1,1,1,1], which satisfies the constraints.
- If nums[index] = 2, we can construct [1,1,2,1], which still satisfies the constraints.
- If nums[index] = 3, we cannot construct a valid array within maxSum = 6 without violating the sum constraint, as the minimum possible sum we can make is from the array [1,2,3,2], and it results in a sum of 8, which exceeds maxSum = 6.
- For all nums[index] = 4, 5, 6, we cannot satisfy the condition sum ≤ maxSum because the minimum possible sum required to construct a valid array increases as nums[index] increases. Even for nums[index] = 3, the sum already exceeds maxSum, so any higher value will further increase the total sum, making it impossible to stay within the given constraint.
Since 3 is the first point where it's not possible, we return 2, the point before it. Thus, the answer is 2.
We can see that every number from 1 to 2 allows us to construct a valid array. But as soon as we try 3 or more, it’s no longer possible because the sum exceeds maxSum.
Let’s define maxValue as the maximum possible value for nums[index]. Any number greater than maxValue would make it impossible to construct a valid array within the maxSum constraint. However, any number from 1 to maxValue ensures that we can construct an array satisfying all the given conditions. On the other hand, any number from maxValue + 1 to maxSum will never satisfy the constraints, as the sum of the array would exceed maxSum.
How can we determine if the array is valid given the value of nums[index]?
Alright! Let's break it down in a way that makes sense step by step.
We need to build an array where:
- All numbers are positive integers (like 1, 2, 3, etc.).
- Adjacent numbers can differ by at most 1 (meaning, each number can be at most 1 more or 1 less than its neighbor).
- The total sum of the array should be ≤ maxSum.
Now, we are trying to maximize nums[index], which means we want to make it as large as possible while still keeping the sum within limits.
How do we build this array?
- Let's say we fix nums[index] = x (we already know this value because we are checking possible values in the range [1, maxSum]).
- Since we want nums[index] to be the biggest number in the array, all other numbers must be less than or equal to x.
So, we start with something like this:
[_, _, _, x, _, _]
Now, how do we fill in the rest?
- The number next to x can be either x or x - 1 (because the difference between adjacent numbers can be at most 1).
- To keep the sum as small as possible, we take the smaller value, which is x - 1.
So now, the array looks like:
[_, _, x-1, x, x-1, _]
- Similarly, for the next positions, the number can be either x-1 or x-2. Again, to keep the sum low, we choose x-2.
Now, the array looks like this:
[_, x-2, x-1, x, x-1, x-2]
- We keep filling in the rest by decreasing numbers step by step, following the same pattern:
[x-3, x-2, x-1, x, x-1, x-2]
This way, we have built an array where:
1. The difference between adjacent numbers is at most 1
2. The sum is minimized
3. nums[index] is maximized
Now, we just calculate the total sum of this array and check if it fits within maxSum.
- If sum ≤ maxSum, then x is a valid choice.
And that’s how we construct the array while making sure we satisfy all conditions!
Alright! Now that we know how to construct the array while keeping nums[index] as large as possible and maintaining the smallest sum, the next question is:
How do we efficiently calculate this sum?
We could just loop through all the elements and add them up, but that would be slow when n is large. Instead, we can use mathematical formulas to compute the sum efficiently in constant time.
Let’s break it down step by step!
Step 1: Understanding the sum calculation
We already know that the array is shaped like this:
[x-k, ..., x-2, x-1, x, x-1, x-2, ..., x-k]
To find the total sum, we can break it into two parts:
- Left Side (including x at index)
- Right Side (after index, excluding x itself)
Since we know nums[index] = x, we will include x as part of the left sum and compute the right sum separately.
Step 2: How do we compute the left side?
The left side consists of decreasing numbers:
[x-k, ..., x-2, x-1]
How far back does this sequence go?
- If x is large enough, the sequence will reach 1 before we run out of space on the left.
- If x is small, it will be cut off by the left boundary of the array before reaching 1.
Let’s handle both cases:
Case 1: The full decreasing sequence fits within the left boundary
If x > index, it means we can decrease the values fully without hitting the start of the array.
In this case, the sequence on the left side will be: [x - index, ..., x - 1, x]
This follows an arithmetic progression, where each element decreases by 1 as we move left. The sum of an arithmetic sequence can be calculated using the formula: sum=(A₁ + Aₙ) * n/2
where:
- A₁ is the first term (x - index)
- Aₙ is the last term (x)
- n is the number of terms (index + 1)
Applying these values, the sum of the left side becomes:(x + (x − index)) × (index + 1)/2
Case 2: The decreasing sequence gets cut off
If x ≤ index, we reach 1 before running out of space on the left.
In this case, we first add the sum of the first x natural numbers: x*(x+1)/2
But we still have extra spaces left (since we didn’t reach the boundary). Those extra places will just be filled with 1s (because the smallest possible value is 1).
How many such 1s are there?
Simply (index - x + 1).
So, the final sum for the left side is: x(x+1)/2+(index−x+1)
Step 3: How do we compute the right side?
The right side follows the same logic as the left side. The only difference is that instead of checking against index, we check against n - index - 1 (i.e., the number of elements to the right of index).
Case 1: The full decreasing sequence fits within the right boundary
If x ≥ (n - index), it means we can decrease the values fully without hitting the end of the array.
In this case, the sequence on the right side will be:
[x, x - 1, ..., x - (n - index) + 1]
This follows an arithmetic progression, where each element decreases by 1 as we move right. The sum of an arithmetic sequence is given by: sum=(A₁ + Aₙ) * n/2
where:
- A₁ is the first term (x)
- Aₙ is the last term (x - (n - index) + 1)
- n is the number of terms (n - index)
Applying these values, the sum of the right side becomes: (x+(x−(n−index)+1)) × (n−index)/2
Case 2: The decreasing sequence gets cut off
If x < (n - index), we reach 1 before running out of space on the right.
In this case, we first add the sum of the first x natural numbers: x(x+1)/2
But we still have extra spaces left (since we didn’t reach the boundary). Those extra places will just be filled with 1s (because the smallest possible value is 1).
How many such 1s are there?
Simply (n - index - x).
So, the final sum for the right side is: x * (x+1)/2 + (n−index−x)
Step 4: Putting it all together
Now, we can compute the total sum as:
sum = left sum (including x) + right sum (excluding x)
And we check whether this sum is ≤ maxSum. If yes, then x is a valid choice. Otherwise, we need to try a smaller value of x.
Let's understand with an example:
Input: n = 6, index = 1, maxSum = 10
We start with nums[index] = 1 and increase it while keeping the total sum ≤ maxSum.
- nums[index] = 1 → [1, 1, 1, 1, 1, 1] → Sum = 6 (Valid)
- nums[index] = 2 → [1, 2, 1, 1, 1, 1] → Sum = 7 (Valid)
- nums[index] = 3 → [1, 3, 2, 1, 1, 1] → Sum = 9 (Valid)
- nums[index] = 4 → [3, 4, 3, 2, 1, 1] → Sum = 14 (Exceeds maxSum)
Since 4 is invalid, the maximum nums[index] is 3.
Steps to Implement the Solution:
Define a Function to Check Feasibility (isPossible)
- Compute the total sum required for a given target value at index.
- Calculate the sum for the left side (before index).
- Calculate the sum for the right side (after index).
- Ensure the total sum does not exceed maxSum.
Implement the maxValue Function
- Initialize ans to store the maximum possible value.
- Iterate from 1 to maxSum, checking feasibility using isPossible.
- If a value is valid, update ans; otherwise, stop the loop.
Maximum Value at a Given Index in a Bounded Array / Code Implementation
1. Maximum Value at a Given Index in a Bounded Array solution in c++ Try on Compiler
// C++ implementation of the solution
class Solution {
// Function to check if it is possible to form the array with a given target value at the index
bool isPossible(int n, int index, int maxSum, int target) {
// Variable to store the total sum of the array
long long count = 0;
// Calculate the sum of the left part of the array including the target index
if (target > index) {
count += (long long)(target + target - index) * (index + 1) / 2;
} else {
count += (long long)(target + 1) * target / 2 + index - target + 1;
}
// Calculate the sum of the right part of the array excluding the target index
if (target >= n - index) {
count += (long long)(target + target - n + 1 + index) * (n - index) / 2;
} else {
count += (long long)(target + 1) * target / 2 + n - index - target;
}
// Check if the total sum is within the allowed maxSum constraint
return count - target <= maxSum;
}
public:
// Function to find the maximum possible value at the given index
int maxValue(int n, int index, int maxSum) {
// Variable to store the result
int ans = 0;
// Iterate through all possible values from 1 to maxSum
for (int i = 1; i <= maxSum; i++) {
// Check if it is possible to form the array with the current value
if (isPossible(n, index, maxSum, i)) {
// Update the answer if the value is valid
ans = i;
} else {
// Stop if further increments are not possible
break;
}
}
// Return the maximum possible value at the index
return ans;
}
};
2. Maximum Value at a Given Index in a Bounded Array solution in Java Try on Compiler
// Java implementation of the solution
class Solution {
// Function to check if it is possible to form the array with a given target value at the index
private boolean isPossible(int n, int index, int maxSum, int target) {
// Variable to store the total sum of the array
long count = 0;
// Calculate the sum of the left part of the array including the target index
if (target > index) {
count += (long)(target + target - index) * (index + 1) / 2;
} else {
count += (long)(target + 1) * target / 2 + index - target + 1;
}
// Calculate the sum of the right part of the array excluding the target index
if (target >= n - index) {
count += (long)(target + target - n + 1 + index) * (n - index) / 2;
} else {
count += (long)(target + 1) * target / 2 + n - index - target;
}
// Check if the total sum is within the allowed maxSum constraint
return count - target <= maxSum;
}
// Function to find the maximum possible value at the given index
public int maxValue(int n, int index, int maxSum) {
// Variable to store the result
int ans = 0;
// Iterate through all possible values from 1 to maxSum
for (int i = 1; i <= maxSum; i++) {
// Check if it is possible to form the array with current value
if (isPossible(n, index, maxSum, i)) {
// Update the answer if the value is valid
ans = i;
} else {
// Stop if further increments are not possible
break;
}
}
// Return the maximum possible value at the index
return ans;
}
}
3. Maximum Value at a Given Index in a Bounded Array solution in Python Try on Compiler
# Python implementation of the solution
class Solution:
# Function to check if it is possible to form the array with a given target value at the index
def isPossible(self, n, index, maxSum, target):
# Variable to store the total sum of the array
count = 0
# Calculate the sum of the left part of the array including the target index
if target > index:
count += (target + (target - index)) * (index + 1) // 2
else:
count += (target * (target + 1)) // 2 + (index - target + 1)
# Calculate the sum of the right part of the array excluding the target index
if target >= n - index:
count += (target + (target - (n - index - 1))) * (n - index) // 2
else:
count += (target * (target + 1)) // 2 + (n - index - target)
# Check if the total sum is within the allowed maxSum constraint
return count - target <= maxSum
# Function to find the maximum possible value at the given index
def maxValue(self, n, index, maxSum):
# Variable to store the result
ans = 0
# Iterate through all possible values from 1 to maxSum
for i in range(1, maxSum + 1):
# Check if it is possible to form the array with the current value
if self.isPossible(n, index, maxSum, i):
# Update the answer if the value is valid
ans = i
else:
# Stop if further increments are not possible
break
# Return the maximum possible value at the index
return ans
4. Maximum Value at a Given Index in a Bounded Array solution in Javascript Try on Compiler
/**
* @param {number} n
* @param {number} index
* @param {number} maxSum
* @return {number}
*/
// Function to check if it is possible to form the array with a given target value at the index
var isPossible = function (n, index, maxSum, target) {
// Variable to store the total sum of the array
let count = 0;
// Calculate the sum of the left part of the array including the target index
if (target > index) {
count += ((target + (target - index)) * (index + 1)) / 2;
} else {
count += ((target * (target + 1)) / 2) + (index - target + 1);
}
// Calculate the sum of the right part of the array excluding the target index
if (target >= n - index) {
count += ((target + (target - (n - index - 1))) * (n - index)) / 2;
} else {
count += ((target * (target + 1)) / 2) + (n - index - target);
}
// Check if the total sum is within the allowed maxSum constraint
return count - target <= maxSum;
}
var maxValue = function (n, index, maxSum) {
// Variable to store the result
let ans = 0;
// Iterate through all possible values from 1 to maxSum
for (let i = 1; i <= maxSum; i++) {
// Check if it is possible to form the array with the current value
if (isPossible(n, index, maxSum, i)) {
// Update the answer if the value is valid
ans = i;
} else {
// Stop if further increments are not possible
break;
}
}
// Return the maximum possible value at the index
return ans;
};Complexity Analysis of Maximum Value at a Given Index in a Bounded Array (brute force):
Time Complexity: O(maxSum)
In the given approach, we iterate from 1 to maxSum and check whether it is possible to construct a valid array using the isPossible function.
Step 1: Analyzing the Outer Loop (Linear Search in maxValue)
- The loop runs from 1 to maxSum, meaning it has a worst-case complexity of O(maxSum).
- For each iteration, we call isPossible to verify if the current value is feasible.
Step 2: Analyzing the isPossible Function
- The function calculates the sum of the left and right parts of the array.
- These computations involve simple arithmetic operations, which take O(1) time.
- Thus, each call to isPossible runs in O(1).
Overall Time Complexity
- Since isPossible runs in O(1) and is called O(maxSum) times, the total time complexity is: O(maxSum) * O(1) = O(maxSum)
Space Complexity: O(1)
- Auxiliary Space Complexity: O(1)
The only additional space used is a few integer and long long variables (count, ans, i, and function parameters).
Since these variables take O(1) space, the auxiliary space complexity is: O(1). - Total Space Complexity: O(1)
All computations are done in-place, and no additional memory is allocated dynamically.
Therefore, the total space complexity is O(1).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(maxSum), where maxSum is the upper limit of the sum constraint (with a maximum value of 10⁹). In the worst-case scenario, the algorithm iterates from 1 to maxSum, leading to a time complexity of O(maxSum).
This time complexity can become inefficient when maxSum is large, particularly when maxSum is close to its upper bound (10⁹). In such cases, the algorithm may perform a large number of operations (nearly 10⁹), making it impractical for large inputs.
This solution may not execute efficiently for all test cases, particularly when maxSum is near its upper limit. While it may work for inputs with smaller values of maxSum, it could exceed the time limits for large inputs where maxSum is close to its maximum constraint.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs with large values of maxSum, this time complexity could lead to inefficient execution.
How to optimize it?
In the previous approach, we checked every possible value of nums[index] (from 1 to maxSum) and verified if it was possible to construct the array while maintaining the given constraints. This gave us an O(maxSum) time complexity, which was too slow and caused TLE (Time Limit Exceeded).
Now, let’s think about improving this.
The main issue was that we checked every possible value of nums[index] from 1 to maxSum, which took a lot of time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the maximum possible value of nums[index] that still satisfies all the constraints. We know this maximum lies between 1 (minimum value of nums[index]) and maxSum (upper bound).
Now that we know the two endpoints, 1 and maxSum, let's make a few observations:
- The data structure is sorted:
The range of possible values for nums[index] is naturally sorted from 1 to maxSum. - The search space is monotonic:
- If a certain value for nums[index] allows us to construct a valid array, then any smaller value will also work.
- If a certain value does not allow us to construct a valid array, then any larger value will also fail.
- For the example n = 4, index = 2, maxSum = 6, the algorithm will fail for a value nums[index] = 3 because it exceeds maxSum. However, starting from nums[index] = 2, it will succeed (T, T, T), and the search will find that the maximum valid nums[index] is 2. This illustrates the monotonic property: once a value works, it will continue to work for smaller numbers.
- The middle element helps minimize or maximize the search space:
If we take the middle value of the current range and check if it works (i.e., can we construct a valid array under the given constraints), we can narrow the search space:
If it works, we move to the right half to find a larger valid number for nums[index].
If it doesn’t work, we move to the left half to find a smaller valid number for nums[index].
If we plot a graph with the possible values of nums[index] on the x-axis and the corresponding sum of the constructed array on the y-axis, we observe the following pattern:
- Before reaching the maximum valid nums[index], we can successfully construct an array that satisfies all constraints.
- However, once nums[index] exceeds this maximum value, it becomes impossible to construct a valid array while keeping the sum within maxSum.
Thus, maxIndex represents the largest value at the index that still satisfies all constraints. Once this number is found, constructing a valid array remains feasible for any number ≤ maxIndex.
With these points in mind, it's clear that instead of linearly checking all possible values from 1 to maxSum, we can take the middle value and continually reduce the search space.
Does this approach remind you of something you've seen before?
Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the range of nums[index], we efficiently narrow down the search space to find the maximum valid value instead of checking each value linearly.
Maximum Value at a Given Index in a Bounded Array Binary Search Algorithm
Binary search can help us quickly find the maximum possible value for nums[index] while satisfying all constraints.
- Start by taking the middle value between low (1) and high (maxSum).
- If this mid value satisfies the condition that we can construct a valid array under maxSum, we store it as a potential answer and move the search to the right half, looking for a larger valid value.
- Otherwise, we move the search to the left half to find a smaller valid value.
- We continue this process as long as low ≤ high.
- Once the condition breaks, the stored answer is returned as the maximum value of nums[index].
Once the condition breaks, the stored answer is returned as the maximum possible value for nums[index] in the constructed array.
By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.
Let us understand this approach with a video,
maximum-value-at-a-given-index-in-a-bounded-array-Animation Explaination
Let's understand with an example:
Initial Setup:
- low = 1, high = 10 (maxSum)
- Binary search to find the maximum possible nums[index]
Step 1:
- mid = (1 + 10) / 2 = 5
- Check if we can construct a valid array with nums[1] = 5 while keeping the total sum ≤ 10.
- Total sum required for nums = [1, 5, 4, 3, 2, 1] = 16 (exceeds maxSum) → Invalid
- Move left: high = 4
Step 2:
- mid = (1 + 4) / 2 = 2
- Check if we can construct a valid array with nums[1] = 2.
- Total sum required for nums = [1, 2, 2, 1, 1, 1] = 8 (valid)
- Move right: low = 3, store ans = 2
Step 3:
- mid = (3 + 4) / 2 = 3
- Check if we can construct a valid array with nums[1] = 3.
- Total sum required for nums = [1, 3, 2, 2, 1, 1] = 10 (valid)
- Move right: low = 4, store ans = 3
Step 4:
- mid = (4 + 4) / 2 = 4
- Check if we can construct a valid array with nums[1] = 4.
- Total sum required for nums = [1, 4, 3, 2, 2, 1] = 13 (exceeds maxSum) → Invalid
- Move left: high = 3
Termination:
- low > high, so ans = 3 is the final answer.
Final Output: nums[index] = 3
How to code it up:
- Define a Function to Check Feasibility (isPossible)
- Compute the total sum required for a given target value at index.
- Calculate the sum for the left side (before index).
- Calculate the sum for the right side (after index).
- Ensure the total sum does not exceed maxSum.
2. Implement the Main Function (maxValue)
- Initialize low to 1 and high to maxSum for binary search.
- Set a variable ans to store the maximum possible value.
- Perform binary search:
- Compute mid as the average of low and high.
- Call isPossible with mid to check feasibility.
- If feasible, update ans and move low to mid + 1.
- If not feasible, move high to mid - 1.
- Return ans as the result.
Maximum Value at a Given Index in a Bounded Array / Code Implementation
1. Maximum Value at a Given Index in a Bounded Array solution in c++ Try on Compiler
class Solution {
// Function to check if it's possible to create an array satisfying the given constraints
bool isPossible(int n, int index, int maxSum, int target)
{
// Variable to store the total sum of the array
long long count = 0;
// Calculate the sum of the left side (including the target index)
if (target > index) {
count += (long long)(target + target - index) * (index + 1) / 2;
} else {
count += (long long)(target + 1) * target / 2 + index - target + 1;
}
// Calculate the sum of the right side (excluding the target index)
if (target >= n - index) {
count += (long long)(target + target - n + 1 + index) * (n - index) / 2;
} else {
count += (long long)(target + 1) * target / 2 + n - index - target;
}
// Check if the total sum is within the allowed maxSum
return count - target <= maxSum;
}
public:
// Function to find the maximum possible value at the given index
int maxValue(int n, int index, int maxSum) {
// Initialize binary search range
long long low = 1;
long long high = maxSum;
// Variable to store the result
int ans = 0;
// Perform binary search
while (low <= high)
{
// Calculate the middle value
int mid = (low + high) / 2;
// Check if it's possible to form the array with the mid value
if (isPossible(n, index, maxSum, mid))
{
// Update answer and move to the right half
ans = mid;
low = mid + 1;
}
else
{
// Move to the left half
high = mid - 1;
}
}
// Return the maximum possible value at the index
return ans;
}
};
2. Maximum Value at a Given Index in a Bounded Array solution in Java Try on Compiler
class Solution {
// Function to check if it's possible to create an array satisfying the given constraints
private boolean isPossible(int n, int index, int maxSum, int target) {
// Variable to store the total sum of the array
long count = 0;
// Calculate the sum of the left side (including the target index)
if (target > index) {
count += (long) (target + target - index) * (index + 1) / 2;
} else {
count += (long) (target + 1) * target / 2 + index - target + 1;
}
// Calculate the sum of the right side (excluding the target index)
if (target >= n - index) {
count += (long) (target + target - n + 1 + index) * (n - index) / 2;
} else {
count += (long) (target + 1) * target / 2 + n - index - target;
}
// Check if the total sum is within the allowed maxSum
return count - target <= maxSum;
}
// Function to find the maximum possible value at the given index
public int maxValue(int n, int index, int maxSum) {
// Initialize binary search range
long low = 1;
long high = maxSum;
// Variable to store the result
int ans = 0;
// Perform binary search
while (low <= high) {
// Calculate the middle value
int mid = (int) ((low + high) / 2);
// Check if it's possible to form the array with the mid value
if (isPossible(n, index, maxSum, mid)) {
// Update answer and move to the right half
ans = mid;
low = mid + 1;
} else {
// Move to the left half
high = mid - 1;
}
}
// Return the maximum possible value at the index
return ans;
}
}
3. Maximum Value at a Given Index in a Bounded Array solution in Python Try on Compiler
class Solution:
# Function to check if it's possible to create an array satisfying the given constraints
def isPossible(self, n, index, maxSum, target):
# Variable to store the total sum of the array
count = 0
# Calculate the sum of the left side (including the target index)
if target > index:
count += (target + target - index) * (index + 1) // 2
else:
count += (target + 1) * target // 2 + index - target + 1
# Calculate the sum of the right side (excluding the target index)
if target >= n - index:
count += (target + target - n + 1 + index) * (n - index) // 2
else:
count += (target + 1) * target // 2 + n - index - target
# Check if the total sum is within the allowed maxSum
return count - target <= maxSum
# Function to find the maximum possible value at the given index
def maxValue(self, n, index, maxSum):
# Initialize binary search range
low, high = 1, maxSum
# Variable to store the result
ans = 0
# Perform binary search
while low <= high:
# Calculate the middle value
mid = (low + high) // 2
# Check if it's possible to form the array with the mid value
if self.isPossible(n, index, maxSum, mid):
# Update answer and move to the right half
ans = mid
low = mid + 1
else:
# Move to the left half
high = mid - 1
# Return the maximum possible value at the index
return ans
4. Maximum Value at a Given Index in a Bounded Array solution in Javascript Try on Compiler
/**
* @param {number} n
* @param {number} index
* @param {number} maxSum
* @return {number}
*/
// Function to check if it is possible to form the array with a given target value at the index
var isPossible = function (n, index, maxSum, target) {
// Variable to store the total sum of the array
let count = 0;
// Calculate the sum of the left part of the array including the target index
if (target > index) {
count += ((target + (target - index)) * (index + 1)) / 2;
} else {
count += ((target * (target + 1)) / 2) + (index - target + 1);
}
// Calculate the sum of the right part of the array excluding the target index
if (target >= n - index) {
count += ((target + (target - (n - index - 1))) * (n - index)) / 2;
} else {
count += ((target * (target + 1)) / 2) + (n - index - target);
}
// Check if the total sum is within the allowed maxSum constraint
return count - target <= maxSum;
}
var maxValue = function (n, index, maxSum) {
// Initialize binary search range
let low = 1;
let high = maxSum;
let ans = 0;
// Perform binary search
while (low <= high) {
// Calculate the middle value
let mid = Math.floor((low + high) / 2);
// Check if it's possible to form the array with the mid value
if (isPossible(n, index, maxSum, mid)) {
// Update answer and move to the right half
ans = mid;
low = mid + 1;
} else {
// Move to the left half
high = mid - 1;
}
}
// Return the maximum possible value at the index
return ans;
};Complexity Analysis of Maximum Value at a Given Index in a Bounded Array (binary search):
Time Complexity : O(log maxSum)
The time complexity analysis for the given solution is as follows:
- Binary Search Complexity:
- The maxValue function performs a binary search over the range [1, maxSum].
- The number of iterations in binary search is O(log maxSum) since the search space is halved in each step.
- Feasibility Check Complexity (isPossible Function):
- The isPossible function computes the total sum required for a given target in O(1) time using arithmetic formulas.
- Since it involves a few constant-time operations, its complexity is O(1).
- Overall Complexity:
- The binary search calls isPossible in each iteration.
- Thus, the overall time complexity is: O(log maxSum) * O(1) = O(log maxSum)
Space Complexity : O(1)
- Auxiliary Space Complexity: O(1)
The algorithm only uses a few integer variables. These are just primitive variables that occupy O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(1)
The input constraints ensure that we only work with a few integer variables.
Therefore, the total space complexity is O(1).
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems.
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.Return the minimum integer k such that she can eat all the bananas within h hours.
2. Maximum Index
Given an array, arr[] of non-negative integers. The task is to return the maximum of j - i (i<=j) subjected to the constraint of arr[i] <= arr[j].