Maximum Value at a Given Index in a Bounded Array

Leetcode Daily Challenge (10th June, 2023)

10 June, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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 <= 109
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:-

java

python

leetcode

dsa