Maximum Value at a Given Index in a Bounded Array

Problem Statement:-

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.

Link: https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/description/

Problem Explanation with examples:-

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 <= 10<sup>9</sup>

• 0 <= index < n

Intuition:-

• Binary search approach will be followed to find the maximum value which satisfies the given conditions.

• Start with mid and check if the sum of left and right side of the array is less than or equal to maxSum.

• Also making sure, the difference between consecutive elements is not greater than 1.

Solution:-

• Define a function to calc_sum which takes count and end as parameters. If count is 0, return 0. Else, initialize start as max(end - count, 0). Calculate sum1 as end (1 + end) // 2 and sum2 as start (1 + start) // 2. Return sum1 - sum2.

• Subtract n from maxSum. Initialize l as 0 and r as maxSum.

• Iterate until l <= r. Initialize mid as (l + r) // 2. Calculate left_sum as calc_sum(index + 1, mid) and right_sum as calc_sum(n - index - 1, mid - 1).

• If left_sum + right_sum <= maxSum, update l as mid + 1. Else, update r as mid - 1.

• Return l.

Code:-

JAVA Solution

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int maxSumDiff = maxSum - n;
        int left = 0;
        int right = maxSumDiff;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            long leftSum = calcSum(index + 1, mid);
            long rightSum = calcSum(n - index - 1, mid - 1);

            if (leftSum + rightSum <= maxSumDiff) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private long calcSum(int cnt, int end) {
        if (cnt == 0) {
            return 0;
        }

        int start = Math.max(end - cnt, 0);
        long sum1 = (long) (end * (1 + end)) / 2;
        long sum2 = (long) (start * (1 + start)) / 2;
        return sum1 - sum2;
    }
}

Python Solution

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def calc_sum(cnt, end):
            if cnt == 0:
                return 0
            start = max(end - cnt, 0)
            sum1 = end * (1 + end) // 2
            sum2 = start * (1 + start) // 2
            return sum1 - sum2

        maxSum -= n
        l, r = 0, maxSum
        while l <= r:
            mid = (l + r) // 2
            left_sum = calc_sum(index + 1, mid)
            right_sum = calc_sum(n - index - 1, mid - 1)
            if left_sum + right_sum <= maxSum:
                l = mid + 1
            else:
                r = mid - 1
        return l

Complexity Analysis:-

TIME:-

The time complexity is O(log(maxSum)). The calcSum function has a time complexity of O(1). Therefore, the overall time complexity of the maxValue method is O(log(maxSum)).

SPACE:-

The space complexity is O(1) because the algorithm uses a constant amount of additional space to store variables and does not scale with the input size.

References:-

• Binary Search

Connect with me:-

• Twitter

• Github

• LinkedIn