Leetcode 1802. Maximum Value at a Given Index in a Bounded Array Solution
Problem Explanation
You are given three positive integers n, index, and maxSum. The goal is to construct an array nums (0-indexed) that meets the following conditions:
- The length of nums is n.
- Each element of nums must be a positive integer.
- For each 0 <= i < n-1, the absolute difference between nums[i] and nums[i+1] should be less than or equal to 1.
- The sum of all the elements of nums should not exceed maxSum.
- The element nums[index] should be maximized.
We have to find the value of nums[index] for the constructed array.
Example Walk-through
For example, given n = 4, index = 2, and maxSum = 6, the output is 2. This is because there are two arrays that meet the given conditions: [1, 1, 2, 1] and [1, 2, 2, 1]. In both cases, nums[index] is 2, so 2 is returned.
Approach
The approach used in the solution is binary search. The main idea is to search for the first value (x) such that if nums[index] equals x, the sum of the elements in the array (A) >= maxSum. To solve this, we use binary search to set a range l and r, where l = 0 and r = maxSum. We then iterate until l < r, calculating the mid value and comparing the minimum sum of the array with x and maxSum.
For this purpose, we use the helper function getSum(n, index, x), which calculates the minimum sum of the array if nums[index] = x. In simple terms, this function calculates the sum of the left side and right side elements of the array based on the value of x, length of the array (n), and the index.
At the end of the iteration (when l >= r), we compare the minimum sum with the maxSum and return the max value of the nums[index] based on the comparison.
Algorithm Steps (with example)
Let's walk through the example provided above (n = 4, index = 2, and maxSum = 6).
- First, we decrement maxSum by n (maxSum = maxSum - n). The new value of maxSum is 2.
- Next, we initialize the lower limit l to 0 and upper limit r to maxSum (r = 2).
- The while loop starts and will continue iterating as long as l < r. In each iteration, we perform the following steps:
- Calculate the mid value m (m = (l + r) / 2).
- Check if the minimum sum of the array (getSum(n, index, m)) is greater than or equal to the maxSum:
- If it is, we set r = m.
- If not, we set l = m + 1.
- The loop continues until l >= r. At this point, we check if the minimum sum of the array with l (getSum(n, index, l)) is greater than maxSum.
- If so, we return l.
- If not, we return l + 1.
Python Solution
1class Solution:
2 def maxValue(self, n: int, index: int, maxSum: int) -> int:
3 maxSum -= n
4 l = 0
5 r = maxSum
6
7 while l < r:
8 m = (l + r) // 2
9 if self.getSum(n, index, m) >= maxSum:
10 r = m
11 else:
12 l = m + 1
13
14 return l if self.getSum(n, index, l) > maxSum else l + 1
15
16 def getSum(self, n: int, index: int, x: int) -> int:
17 l = min(index, x - 1)
18 r = min(n - index, x)
19 lSum = ((x - 1) + (x - 1 - l + 1)) * l // 2
20 rSum = (x + (x - r + 1)) * r // 2
21 return lSum + rSum
Java Solution
1class Solution {
2 public int maxValue(int n, int index, int maxSum) {
3 maxSum -= n;
4 int l = 0;
5 int r = maxSum;
6
7 while (l < r) {
8 int m = (l + r) / 2;
9 if (getSum(n, index, m) >= maxSum)
10 r = m;
11 else
12 l = m + 1;
13 }
14
15 return getSum(n, index, l) > maxSum ? l : l + 1;
16 }
17
18 private long getSum(int n, int index, int x) {
19 long l = Math.min(index, x - 1);
20 long r = Math.min(n - index, x);
21 long lSum = ((x - 1) + (x - 1 - l + 1)) * l / 2;
22 long rSum = (x + (x - r + 1)) * r / 2;
23 return lSum + rSum;
24 }
25}
JavaScript Solution
1class Solution {
2 maxValue(n, index, maxSum) {
3 maxSum -= n;
4 let l = 0;
5 let r = maxSum;
6
7 while (l < r) {
8 const m = Math.floor((l + r) / 2);
9 if (this.getSum(n, index, m) >= maxSum)
10 r = m;
11 else
12 l = m + 1;
13 }
14
15 return this.getSum(n, index, l) > maxSum ? l : l + 1;
16 }
17
18 getSum(n, index, x) {
19 const l = Math.min(index, x - 1);
20 const r = Math.min(n - index, x);
21 const lSum = ((x - 1) + (x - 1 - l + 1)) * l / 2;
22 const rSum = (x + (x - r + 1)) * r / 2;
23 return lSum + rSum;
24 }
25}
C++ Solution
1class Solution {
2 public:
3 int maxValue(int n, int index, int maxSum) {
4 maxSum -= n;
5 int l = 0;
6 int r = maxSum;
7
8 while (l < r) {
9 const int m = (l + r) / 2;
10 if (getSum(n, index, m) >= maxSum)
11 r = m;
12 else
13 l = m + 1;
14 }
15
16 return getSum(n, index, l) > maxSum ? l : l + 1;
17 }
18
19 private:
20 long getSum(int n, int index, int x) {
21 long l = min(index, x - 1);
22 long r = min(n - index, x);
23 long lSum = ((x - 1) + (x - 1 - l + 1)) * l / 2;
24 long rSum = (x + (x - r + 1)) * r / 2;
25 return lSum + rSum;
26 }
27};
C# Solution
1public class Solution {
2 public int MaxValue(int n, int index, int maxSum) {
3 maxSum -= n;
4 int l = 0;
5 int r = maxSum;
6
7 while (l < r) {
8 int m = (l + r) / 2;
9 if (GetSum(n, index, m) >= maxSum)
10 r = m;
11 else
12 l = m + 1;
13 }
14
15 return GetSum(n, index, l) > maxSum ? l : l + 1;
16 }
17
18 private long GetSum(int n, int index, int x) {
19 long l = Math.Min(index, x - 1);
20 long r = Math.Min(n - index, x);
21 long lSum = ((x - 1) + (x - 1 - l + 1)) * l / 2;
22 long rSum = (x + (x - r + 1)) * r / 2;
23 return lSum + rSum;
24 }
25}
This problem can be efficiently solved using binary search, as shown in the solutions provided in various programming languages. For each language, the approach uses a helper function called getSum to calculate the minimum sum of the array based on the value of x, length of the array, and index. The main function iterates through the binary search, comparing the minimum sum of the array with the given maxSum, and returning the max value of the nums[index] based on the comparison.
By analyzing the provided solutions, you'll be able to better understand how to implement this problem in the programming language of your choice, whether it's Python, Java, JavaScript, C++, or C#.