Problem

Submissions

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

Statement▼

Given three positive integers, n, index, and maxSum, output the nums[index] by constructing an array of nums with the length of n, which satisfies the following conditions:

The length of the array nums is equal to n.
Each element nums[i] is a positive integer, where $1$ $\leq$ i $\lt$ n.
The absolute difference between two consecutive elements, nums[i] and nums[i+1], is at most $1$ .
The sum of all elements in nums does not exceed maxSum.
The element at nums[index] contains the maximum value.

Constraints:

$1$ $\leq$ n $\leq$ maxSum $\leq$ $10^9$
$0$ $\leq$ index $\lt$ n

The solution to maximizing the value at a given index in a bounded array involves using a binary search approach combined with mathematical calculations of arithmetic sequences. To achieve this, we need to ensure that the values on both sides of nums[index] decrease by at most $1$ until reaching $1$ (we cannot go beyond 1 because the elements should be positive), minimizing the overall sum of the array.

The algorithm to solve this problem is as follows:

Initialization

Initialize two variables, left and right, with the values $1$ and maxSum, respectively. We can assign a minimum value of $1$ to an element, and the maximum value of maxSum.
Start a loop and Iterate until left is less than right, and calculate the sum of left and right elements as listed below:

Calculate mid

Calculate mid as $mid = (left + right + 1) / 2$ .

Determine values on the left side

If mid is greater than index, there will be a sequence starting from mid to the $mid - index$ (right to left). This sequence will form a series $[mid - index, mid - index + 1, mid - 1, ..., mid]$ , which is an arithmetic series. This arithmetic series is calculated as $(mid + mid - index) * (index + 1) / 2.$

For example, if n = 5, index = 4, and maxSum = 20, then mid will equal $11$ (calculated by the formula given above). The sequence will be (from right to left, i.e., mid to left): $[7, 8, 9, 10, 11]$ , and the sum of this series will be calculated as $(11 + 11 - 4) * (4 + 1) / 2 = 45$ .

Otherwise, if mid is less than or equal to index, then there will be a sequence starting from mid to $1$ (right to left). This sequence will form a series $[1, 2, 3, ..., mid - 1, mid]$ , which is an arithmetic series. In mathematics, this arithmetic series is calculated as $(mid + 1) * mid / 2$ . In addition to the arithmetic series, there will also be a sequence of $1$ s of length $index - mid + 1$ .

For example, if n = 8, index = 7, maxSum = 9, then mid will equal $5$ . The sequence will be (from right to left, i.e., mid to left): $[1, 2, 3, 4 ,5]$ , and the sum of this series will be calculated as $(5 + 1) * 5 / 2 = 15$ .

Moreover, there will be $3$ consecutive $1$ s, which will be calculated by $7 - 5 + 1 = 3.$

The total sum of the left side is calculated by $(mid + 1) * mid / 2 + index - mid + 1$ .

Determine values on the right side

If mid is greater than or equal to n - index, there will be a sequence starting from mid to $mid - n + 1 + index$ (left to right). This sequence will form a series $[mid, mid - 1, mid - 2, ... , mid - n + 1 + index]$ , which is an arithmetic series. In mathematics, this arithmetic series is calculated as $(mid + mid - n + 1 + index) * (n - index) / 2$ .

For example, if n = 10, index = 7, and maxSum = 11, then mid will equal $6$ . The sequence will be (from mid to right): $[6, 5, 4]$ , and the sum of this series will be calculated as $(6 + 6 - 10 + 1 + 7) * (10 - 7) / 2 = 15$ .

Otherwise, if mid is less than n - index, there will be a sequence starting from mid to 1. This sequence will form a series $[mid, mid - 1, ..., 2, 1]$ , which is an arithmetic series. In mathematics, this arithmetic series is calculated as $(mid + 1) * mid / 2$ . In addition to the arithmetic series, there will also be a sequence of $1$ s of length $n - index - mid$ .

For example, if n = 8, index = 2, maxSum = 9, then mid will equal $5$ . The sequence will be (from left to right, i.e., mid to 1): $[5, 4, 3, 2, 1]$ , and the sum of this series will be calculated as $(mid + 1) * mid / 2 = 15$ .

Moreover, there will be $1$ consecutive $1$ s, as calculated by $8 - 2 - 5 = 1$ .

The total sum of the right side is calculated by $(mid + 1) * mid / 2 + n - index - mid$ .

Sum calculation

Calculate the total sum of the array by combining the sum of both sides and subtracting the value of mid. The reason for subtracting mid is that it is calculated twice (in the sum of the left and the sum of the right).

Updating variables

If the sum of the array is less than or equal to the maxSum, we will use the right half of the array by updating the left with the value of mid.
Otherwise, we will go with the left half of the array by updating right with the value of mid - 1.

After the loop terminates, we will return the value of left because it is the index of the maximum value of nums.

Let’s look at the following illustration to get a better understanding of the solution:

⋮