Maximum Value at a Given Index in a Bounded Array LeetCode Solution

Difficulty Level Medium
Frequently asked in MicrosoftViews 4255

Problem Statement

The problem Maximum Value at a Given Index in a Bounded Array LeetCode Solution says 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.

Example for Maximum Value at a Given Index in a Bounded Array LeetCode Solution:

Test Case 1:

Input:

n = 8

index = 3

maxSum = 14

Output:

3

Test Case 2:

Input:

n = 7

index = 4

maxSum = 8

Output:

2

Explanation for Maximum Value at a Given Index in a Bounded Array LeetCode Solution:

i) For the first case, We can have the array as [0, 1, 2, 3, 2, 1, 0, 0].  So the max value at index 3 is 3. This is the max value we can have which satisfies all the constraints.

i) For the second case, We can have the array as [0, 0, 0, 1, 2, 1, 0].  So the max value at index 4 is 2. This is the max value we can have which satisfies all the constraints.

Approach

Idea:

We first do maxSum -= n,
then all elements need only to valid A[i]>=0.

We binary search the final result between left and right,
where left = 0 and right = maxSum.

For each test, we check the minimum sum if A[index] = a.
The minimum case would be A[index] is a peak in A.
It’s an arithmetic sequence on the left of A[index] with the difference 1.
It’s also an arithmetic sequence on the right of A[index] with the difference -1.

On the left, A[0] = max(a – index, 0),
On the right, A[n-1] = max(a – ((n-1) – index), 0),

The sum of arithmetic sequence {b, b+1, ….a},
equals to (a + b) * (a – b + 1)/ 2.

Code

Java Program for Maximum Value at a Given Index in a Bounded Array

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        maxSum -= n;
        int left = 0, right = maxSum, mid;
        while (left < right) {
            mid = (left + right + 1) / 2;
            if (test(n, index, mid) <= maxSum)
                left = mid;
            else
                right = mid - 1;
        }
        return left + 1;
    }
    
    private long test(int n, int index, int a) {
        int b = Math.max(a - index, 0);
        long res = (long)(a + b) * (a - b + 1) / 2;
        b = Math.max(a - ((n - 1) - index), 0);
        res += (long)(a + b) * (a - b + 1) / 2;
        return res - a;
    }
}

C++ Program for Maximum Value at a Given Index in a Bounded Array

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        maxSum -= n;
        int left = 0, right = maxSum, mid;
        while (left < right) {
            mid = (left + right + 1) / 2;
            if (test(n, index, mid) <= maxSum)
                left = mid;
            else
                right = mid - 1;
        }
        return left + 1;
    }

    long test(int n, int index, int a) {
        int b = max(a - index, 0);
        long res = long(a + b) * (a - b + 1) / 2;
        b = max(a - ((n - 1) - index), 0);
        res += long(a + b) * (a - b + 1) / 2;
        return res - a;
    }
};

Python Program for Maximum Value at a Given Index in a Bounded Array

class Solution(object):
    def maxValue(self, n, index, maxSum):
        def test(a):
            b = max(a - index, 0)
            res = (a + b) * (a - b + 1) / 2
            b = max(a - ((n - 1) - index), 0)
            res += (a + b) * (a - b + 1) / 2
            return res - a

        maxSum -= n
        left, right = 0, maxSum
        while left < right:
            mid = (left + right + 1) / 2
            if test(mid) <= maxSum:
                left = mid
            else:
                right = mid - 1
        return left + 1

Complexity Analysis for Maximum Value at a Given Index in a Bounded Array LeetCode Solution

Time Complexity

For each value, we can check the sum in O(1)  time using the formula. So time complexity is O(log(maxSum)).

Space Complexity

Here we are not using any extra space. So Space complexity is O(1).

Reference: https://en.wikipedia.org/wiki/Binary_search_algorithm

 

 

 

 

Translate »