Covid Vaccination

The idea is to choose a peak value at the ‘dayNumber’ th index. Then we can create the array like a mountain with the peak of the mountain being at the  ‘dayNumber’ th index. The sum of the elements of this array must be less than or equal to maxVaccines.If we find that the sum is greater, then we have chosen a high peak value, and if it is less, then it means we have chosen a smaller peak value. So we have to select the peak value such that given conditions are fulfilled. So we can iterate from maxVaacines to 1 and check if this is the peak value for which the array can be created. If we find such a peak, then we will return its value.

 We need to find the maximum number, which can be the peak of the array vaccine,s and the sum of the array will not exceed maxVaccines. 

Let the peak of the array or vaccines[dayNumber] be x.

Then, we can say the array may look like [... x-2 x-1 x x-1 x-2 …] since abs([vaccine[i+1] - vaccine[i]) <= 1. However, while making the array, we will not decrease after reaching 1 since vaccines[i] > 0.

We can easily find the formula for the total sum of the array vaccines from the peak value and we do not need to create the whole array. 

Let's take the left part of the peak as an example. It can have 2 cases:

1. [1,1,1, ... , 1, 2, 3, ... , peak]
   here leftSum = no of ones - 1 + (peak * (peak+1))/2
2. [k, k+1, k+2, ... , peak-1, peak]
   How to calculate this? This subarray can be regarded as a portion of the following array: [{1, 2, 3, ... , k-1} + {k, k+1, ... , peak}]. So it's easy to get the equation as leftSum = (peak * (peak + 1)) / 2 - (k * (k + 1)) / 2

The same thing goes with the right side.

If the number of elements of the array on the left side of the peak is less than the peak value, we will get situation 2, and if it is more or equal, then we get situation 1. Now we can use the formula according to the situation and find the sum of elements on the left of the peak. Similarly, we can find the sum of the elements to the right of the peak. So we get the sum of all the elements of the array. Now we see if this sum is equal to, less than, or greater than maxVaccines.

If it is equal or less, then this is the required peak value. If it is more, we have to reduce the peak value till we get the desired value.

Now, we need to iterate from maxCapacity till we find an x that satisfies the sum (vaccines) <= maxVaccines. We will stop iterating when we find such a value, and that will be our answer.

The steps are as follows:

• We will initialize two variables ‘left’ and ‘right’ to dayNumber and n-1-dayNumber, respectively, denoting left of peak array elements number and right of peak array elements number respectively.
• We will initialize a variable ans with 1 denoting the value at the required index.
  • We will iterate from i = 0 to maxVaccines - 1:
    • We will declare a function solve which takes 3 arguments mid, left, right denoting the mid value, number of elements to the left of the peak, number of elements to the right of the peak. It returns the sum of the elements of the array.
    • Solve function returns the sum of elements of the array.
      • We will initialize a variable sum with mid*mid.
      • If (mid - 1) is greater than equal to the left sum, then decrement sum by k*(k+1)/2 where k equals mid - 1- left.
      • Else increment sum by the value left - mid +1.
      • If (mid - 1) is greater than equal to the right sum, then decrement sum by k*(k+1)/2 where k equals mid - 1- right.
      • Else increment sum by right - mid +1.
      • We will return the value of the sum as the final answer.
• We initialize x with the value returned by recursive function solve, which has 3 parameters(i, left, right), denoting the value of i the number of elements to the left of mid and the number of elements to the right of mid.
• If x less than equals ‘maxSum’, we set ans = i and break out of the loop.
• We will return ‘ans’ as the final answer.

O(maxVaccines), where maxVaccines is the total number of vaccines available for the drive.

As we check for all values from maxVaccines to 1, there are at most ‘maxVaccines’ number of iterations. Hence the overall complexity is O(maxVaccines).

O(1)

As we are not using any extra space. Hence, the overall space complexity is O(1).