Maximum Value at Index K

Our approach is to try to place every value between 1 to L at the K'th index and check if an array can be constructed or not. We will try to find the array having a minimum sum generated by placing the value at the K'th index and comparing the sum of the array with L. 

For a particular value val at K'th index, the array having minimum sum will have the below form:

[..,max(1,val-2), max(1,val-1), val, max(1,val-1), max(1,val-2),..]

We want all elements of the array to have the minimum value possible to obtain a minimal sum. To get the minimum sum, we are trying to decrease val by 1 at every step as the difference between any adjacent pair of indices can not exceed 1. Once val is reduced to 1, then all the remaining indexes will be assigned 1 because we are trying to construct an array with positive integers. 

Algorithm:

• We will initialize the variable maxValue with 0, and it will store the maximum possible value at the K'th index of the constructed array.
• Iterate val from 1 to L,
  • We will set the variable minSum as val. The variable minSum stores the minimum sum that could be generated by placing the value val at the K’th index.
  • Iterate pos from K-1 to 0 and find the minimum value that could be placed at pos that is the difference of val and distance between K and pos index. Add the minimum value to minSum. Note that the minimum value that could be placed at the index of the array is 1.
  • Iterate pos from K+1 to N-1 and update minSum by adding the minimum value to minSum that could be placed at index pos. Note that the minimum value that could be placed at the index of the array is 1.
  • If minSum is less than or equal to L, then update maxValue with val.
• Return the variable maxValue.

The intuition behind the approach is to observe the fact that if the array can be constructed with the value V at the K'th index having a sum less than or equal to L, then the array can be constructed by all values less than V at the K'th index. Similarly, if the array cannot be constructed with the value V at the K'th index having a sum less than or equal to L, then no array can be constructed by all values greater than V at K'th index that satisfies the above conditions.  

Therefore, our approach will be to use binary search to solve the problem. At each step of binary search, we will find the sum of the optimal array with the minimum sum that could be generated by placing the value V at the K'th index and compare the obtained value with L.  For a particular value val at K'th index, the array having minimum sum will have the below form

[..,max(1,val-2), max(1,val-1),val,max(1,val-1),max(1,val-2),..]

The formula we will be using in order to find the sum of the array is the sum of the first n natural numbers, i.e.,  (n*(n+1))/2  as we are trying to decrease val by 1 at every step till the value reaches the minimum value of the array that is 1 to obtain the optimal array with minimum sum. 

We will find the sum of the left and right array to the K’th index separately. To obtain the sum of the left array, we will find the value at the 0’th index of our constructed array, which is equal to val-K. Let the obtained value be start.

Now there will be two cases:

1. If start is greater than 0  then the left array would be like [start,start+1,start+2,...val], the sum of these values will be val*(val+1)/2 - (start)*(start-1)/2.
2. If start is less than or equal to 0 then the left array would be like [1,1,...1,2,3,...val]. The array will be divided into two parts, one part containing elements with value 1 and another part containing elements with value 1 to val and abs(start-1) stores the number of elements having value 1 in the first part. The sum of these values will be val*(val+1)/2 + abs(start-1). 

To obtain the sum of the right array to the K’th index, we will find end, which stores the value at the N-1 index, which is equal to val-(N-1-K).

Algorithm:

• We will initialize the variable maxValue as 0, low as 1, and high as L. maxValue stores the maximum possible value of the K’th index of the constructed array, low and high stores the lowest and highest values that could be placed at the index K’th respectively.
• Iterate till low is less than or equal to high,
  • Take mid equal to (low + high)/2 and we will set the variable minSum as val. The variable minSum stores the minimum sum that could be generated by placing the value val at the K’th index.
  • To find the sum of the left array to the K’th index, find the value start, which stores the value at 0’th index, which is equal to val-K. If start is more than 0, then increment minSum with the sum of the range of start to val -1, otherwise, the array will be divided into two parts, one part containing elements with value 1 and another part containing elements with value 1 to val-1 and increment minSum by the sum of both parts.
  • To find the sum of the right array to the K’th index, find the value end, which stores the value at the N-1 index, which is equal to val-(N-1-K). We will use a similar approach to the above approach that is used to find the sum of the left array to the K’th index.
  • If the sum of the array is less than or equal to L then set maxValue as mid and low as mid+1, otherwise set high as mid-1.
• Return the variable maxValue.