1802. Maximum Value at a Given Index in a Bounded Array


Problem Description

In this problem, we are tasked with constructing an array nums with the following constraints:

  • The length of the array nums is equal to the given integer n.
  • Each element in the array is a positive integer.
  • The absolute difference between any two consecutive elements is at most 1.
  • The sum of all elements in nums does not exceed a given integer maxSum.
  • Among all possible nums arrays that satisfy the above conditions, we want to maximize the value of nums[index].

Our objective is to find out what that maximized nums[index] is, given the parameters n (the length of the array), index (the specific position in the array we want to maximize), and maxSum (the maximum allowed sum of all elements in the array).

Intuition

The intuition behind the solution is to leverage binary search to efficiently find the maximum possible value of nums[index].

  1. We know that nums[index] must be a positive integer and that the sum of all elements in the array must not exceed maxSum. This means that nums[index] has an upper bound given by maxSum.

  2. The idea is to perform a binary search, starting with the lowest possible value for nums[index] (which is 1) and the maximum possible value, which would be maxSum (assuming all other values in the array are 1).

  3. For each possible value of nums[index] we test in our binary search, we calculate the sum of elements that would be required to form a valid array if nums[index] were that value. To do this, the sum function is used, which calculates the sum of elements in a portion of the array that slopes upwards or downwards by 1 with each step away from nums[index].

  4. If the calculated sum is less than or equal to maxSum while maintaining the constraints of the problem, it means we can potentially increase nums[index]. On the other hand, if the sum exceeds maxSum, then nums[index] must be lower.

By using this method, when we eventually narrow down to a single value through binary search, we find the maximum value of nums[index] that can exist within an array satisfying all the described constraints.

Learn more about Greedy and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The solution provided uses a binary search algorithm to find the maximum value of nums[index]. The binary search algorithm is a classic approach to efficiently search for an element in a sorted array by repeatedly dividing the search interval in half.

The following steps are taken in this implementation:

  1. Initialize Search Range: The search for the maximum value of nums[index] begins by setting the left bound to 1, which is the smallest possible value for any element in the array, and right bound to maxSum, the highest possible value for the nums[index] (assuming all other elements are at the minimum value of 1).

  2. Binary Search Loop: A while loop runs as long as the left bound is less than right. The loop calculates the mid value as the average of left and right, setting up the next guess for nums[index].

  3. Calculate Required Sum: In each iteration, the program calculates the required sum for the array if nums[index] were equal to mid. This is done using a custom sum function, which accounts for the sum of the pyramid-like sequence that forms when values decrease by 1 on each side of the index.

    • sum(x, cnt) Function: This function calculates the sum of the first cnt terms of an arithmetic series that starts at x and decreases by 1 each term until it reaches 1 or runs out of terms. If x is greater than cnt, the sum is the sum of cnt terms starting at x and subtracting down to (x - cnt + 1). If x is less than or equal to cnt, then the sum includes all numbers down to 1, and the remaining terms are 1s. The formula is based on the sum of the first n natural numbers n(n + 1)/2 and adjusted for the start being x instead of 1.

    The function calculates two sums:

    • The sum for the left side from nums[index] to the start of the array.
    • The sum for the right side from nums[index] to the end of the array.
  4. Update Search Bounds: Depending on whether the sum of the sequence with nums[index] equal to mid exceeds maxSum or not, we adjust the binary search range accordingly:

    • If the total sum does not exceed maxSum, it is safe to move the left bound up to mid because a larger or equal nums[index] is viable.
    • If the total sum exceeds maxSum, the right bound is set to mid - 1 because we need a smaller nums[index] to reduce the total sum.
  5. Determine the Maximum Value: After exit from the loop, the maximum possible value for nums[index] is found, which is pointed by left. At this point, left is the largest value that did not violate the sum constraint. Since the constraints ensure that the sequence is increasing then decreasing around nums[index] and that the maximum sum does not exceed maxSum, left indeed maximizes nums[index].

By the end of this process, the solution has efficiently zeroed in on the largest possible value for nums[index] in compliance with all the problem's constraints using binary search.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the mentioned constraints.

Suppose we have the following inputs:

  • n = 5 (length of the array)
  • index = 2 (position in the array we want to maximize)
  • maxSum = 10 (maximum allowed sum of all elements in the array)

Step by Step Process:

  1. Initialize Search Range:

    • We start with left = 1 and right = maxSum = 10.
  2. Binary Search Loop:

    • Begin with left = 1 and right = 10.
    • Calculate mid = (left + right) / 2, let's assume integer division, so with left = 1 and right = 10, mid = 5.
  3. Calculate Required Sum:

    • We calculate the sum for nums[index] = mid.
    • Using the sum function, we calculate the sum for the left part (from start to index) and the right part (from index to end).
    • For the left part, we need 2 values (elements at index 0 and 1), and for the right part, we also need 2 values (elements at index 3 and 4).
    • sumLeft = sum(mid, 3) = sum(5, 3) = 5 + 4 + 1 (as the third term would be 0) = 10.
    • sumRight = sum(mid, 2) = sum(5, 2) = 5 + 4 = 9.
    • Total sum = sumLeft + sumRight - mid (we subtract mid because it's counted in both the left and right sums) = 10 + 9 - 5 = 14.
    • This sum exceeds maxSum; therefore, we need to reduce mid.
  4. Update Search Bounds:

    • Since 14 exceeds maxSum, we set right = mid - 1 = 4.
  5. Loop Continuation:

    • Adjust mid with the new bounds, left = 1 and right = 4.
    • New mid = (1 + 4) / 2 = 2.
    • Calculate new sums with mid = 2.
    • sumLeft = sum(2, 3) = 2 + 1 + 1 = 4.
    • sumRight = sum(2, 2) = 2 + 1 = 3.
    • Total sum = sumLeft + sumRight - mid = 4 + 3 - 2 = 5.
    • This sum fits within maxSum, so we try to increase mid by moving left up.
  6. Update Search Bounds Again:

    • As 5 is less than maxSum, we now set left = mid = 2.
    • Now left = 2 and right = 4.
  7. Finishing the Search:

    • Continue the binary search until left and right meet.
    • Suppose in the next iteration mid = 3 does not exceed maxSum but mid = 4 does, we will stop with left at 3.
  8. Determination:

    • The binary search concludes when left equals right, which is the value just before the sum exceeded maxSum.
    • We find left to be 3, so nums[index] = 3 is the largest possible value that does not violate the constraints.

This example illustrates the solution approach, showing how a binary search systematically narrows down the maximum value for nums[index] while adhering to the problem's constraints. By calculating sums that would form a valid array configuration for each guess and adjusting our bounds accordingly, we efficiently pinpoint the solution.

Not Sure What to Study? Take the 2-min Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Python Solution

1class Solution:
2    def maxValue(self, n: int, index: int, maxSum: int) -> int:
3
4        # Define a local function to calculate the sum of the
5        # arithmetic series that starts at `start_value`, has `count` number of elements
6        def calculate_sum(start_value, count):
7            if start_value >= count:
8                # If the start value is larger than or equal to count,
9                # calculate the sum of the first `count` numbers in the arithmetic series
10                # descending from `start_value`
11                return (start_value + start_value - count + 1) * count // 2
12            else:
13                # If start_value is less than count, then the series is not long 
14                # enough to decrease down to 1. It bottoms out at 1 after `start_value` steps
15                # Then we have to count the remaining `count - start_value` times 1.
16                return (start_value + 1) * start_value // 2 + count - start_value
17
18        left, right = 1, maxSum  # Set the search range between 1 and maxSum
19        while left < right:      # Use binary search to find maximum value
20            mid = (left + right + 1) >> 1  # Calcualte the middle point
21
22            # Check if the sum of both sides with `mid` as the peak value is <= maxSum
23            if calculate_sum(mid - 1, index) + calculate_sum(mid, n - index - 1) + mid <= maxSum:
24                left = mid   # If it's less than or equal to maxSum, this is a new possible solution
25            else:
26                right = mid - 1  # If it exceeds maxSum, we discard the mid value and go lower
27
28        return left  # At the end of the loop, `left` is our maximum value
29
30# Example of how to use the class
31# solution = Solution()
32# result = solution.maxValue(10, 5, 54)
33# print(result)  # The results would print the maximum value that can be achieved
34

Java Solution

1class Solution {
2
3    // Method to find the maximum integer value that can be placed in position 'index'
4    // of an array of length 'n' such that the total sum does not exceed 'maxSum'
5    // and the array is a 0-indexed array with non-negative integers.
6    public int maxValue(int n, int index, int maxSum) {
7        // Define search boundaries for binary search
8        int left = 1, right = maxSum;
9
10        // Perform binary search
11        while (left < right) {
12            // Calculate midpoint and avoid integer overflow
13            int mid = (left + right + 1) >>> 1;
14
15            // If the calculated sum is within the allowed range, search in the upper half
16            if (sum(mid - 1, index) + sum(mid, n - index - 1) <= maxSum) {
17                left = mid;
18            } else {
19                // Otherwise, search in the lower half
20                right = mid - 1;
21            }
22        }
23
24        // At this point, 'left' is the maximum value that can be placed at 'index'
25        return left;
26    }
27
28    // Helper method to calculate the sum of the values we could place in the array
29    // if we start from 'x' and decrement by 1 until we reach 1, limited by 'count'
30    private long sum(long x, int count) {
31        // If 'x' is greater than 'count', we can simply calculate a triangular sum
32        if (x >= count) {
33            return (x + x - count + 1) * count / 2;
34        } else {
35            // Otherwise, we calculate the triangular sum up to 'x' and add the remaining
36            // 'count - x' ones (since we cannot decrement below 1)
37            return (x + 1) * x / 2 + count - x;
38        }
39    }
40}
41

C++ Solution

1class Solution {
2public:
3    // Helper function to calculate sum in a range with certain conditions
4    // If x is greater or equal to count, it calculates the sum of an arithmetic sequence,
5    // Otherwise, it calculates the partial sum and adds the remaining terms 
6    long calculateSum(long x, int count) {
7        if (x >= count) {
8            // Full arithmetic sequence
9            return (x + x - count + 1) * count / 2;
10        } else {
11            // Partial arithmetic sequence + remaining elements
12            return (x + 1) * x / 2 + count - x;
13        }
14    }
15  
16    // Main function to find the maximum value that can be inserted at a given index
17    int maxValue(int n, int index, int maxSum) {
18        int minValue = 1, maxValue = maxSum; // set the bounds for binary search
19      
20        // Binary search to find the max value possible to achieve sum up to maxSum
21        while (minValue < maxValue) {
22            int midValue = (minValue + maxValue + 1) >> 1;
23          
24            // Check if the sum of values on both sides fits within maxSum
25            if (calculateSum(midValue - 1, index) + calculateSum(midValue, n - index - 1) <= maxSum) {
26                minValue = midValue; // Solution exists, go right
27            } else {
28                maxValue = midValue - 1; // Solution doesn't fit, go left
29            }
30        }
31      
32        // minValue holds the maximum value possible for the array
33        return minValue;
34    }
35};
36

Typescript Solution

1// Helper function to calculate sum in a range with certain conditions
2// If x is greater or equal to count, it calculates the sum of an arithmetic sequence,
3// Otherwise, it calculates the partial sum and adds the remaining terms 
4function calculateSum(x: number, count: number): number {
5    if (x >= count) {
6        // Full arithmetic sequence
7        return (x + x - count + 1) * count / 2;
8    } else {
9        // Partial arithmetic sequence + remaining elements
10        return (x + 1) * x / 2 + count - x;
11    }
12}
13
14// Main function to find the maximum value that can be inserted at a given index to not exceed maxSum
15function maxValue(n: number, index: number, maxSum: number): number {
16    let minValue = 1;
17    let maxValue = maxSum; // set the bounds for binary search
18  
19    // Binary search to find the max value possible to achieve sum up to maxSum
20    while (minValue < maxValue) {
21        const midValue = Math.floor((minValue + maxValue + 1) / 2);
22      
23        // Check if the sum of values on both sides fits within maxSum
24        if (calculateSum(midValue - 1, index) + calculateSum(midValue, n - index - 1) <= maxSum - midValue) {
25            minValue = midValue; // Solution exists, go right
26        } else {
27            maxValue = midValue - 1; // Solution doesn't fit, go left
28        }
29    }
30  
31    // minValue holds the maximum value possible for the array
32    return minValue;
33}
34
Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

The time complexity of the provided code is O(log(maxSum)). The binary search algorithm runs between 1 and maxSum, which determines the number of iterations needed to find the solution. In each iteration, the sum function is called twice, each call of which is O(1) because the operations involve simple arithmetic and a conditional check, and thus don't depend on the size of n or maxSum.

The space complexity of the code is O(1). There are only a fixed number of variables used (left, right, mid, and within the sum function), and no extra space that scales with the input size is required. Therefore, the amount of memory used is constant.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫