1
$\begingroup$

We have an array of $N$ positive elements. We can perform $M$ operations on this array. In each operation we have to select a subarray(contiguous) of length $W$ and increase each element by 1. Each element of the array can be increased at most $K$ times. We have to perform these operations such that the minimum element in the array is maximized. In other words, after these operations minimum element in the array should be as large as possible.

$1 \leq N, \ W \leq 10^5$

$1 \leq M, \ K \leq 10^5$

Time limit: 1 sec

I can think of an $O(N^2)$ solution but it is exceeding time limit. Can somebody provide an $O(NlogN)$ or better solution for this?

P.S.- This is an interview question

$\endgroup$
  • $\begingroup$ Would you care to provide the $O(N^2)$ solution? It would be best if anyone reading this wouldn't have to come up with something already done. $\endgroup$ – theSongbird Nov 13 '17 at 16:37
  • $\begingroup$ Also, from what I understand, you wish to maximize the minimum element of the $unchanged$ array. Correct? $\endgroup$ – theSongbird Nov 13 '17 at 16:38
  • $\begingroup$ No, the minimum element in the array after all operations should be as large as possible. It does not have anything to do with the unchanged array. $\endgroup$ – Sumit Kumar Nov 13 '17 at 17:50
  • $\begingroup$ We should increase the subarray containing the current minimum in the array. But, there can be W such subarrays. We will find the subarray containing more no. of smaller elements and increase that subarray. We will do it M times. Finally, the minimum element in the array after the operations will be the answer. I could think of only this and it looks like O(N^2). $\endgroup$ – Sumit Kumar Nov 13 '17 at 17:55
  • $\begingroup$ So the minimum element changes each time you add 1 to a subarray. You don't intend to maximize the initial minimum element of the array. $\endgroup$ – theSongbird Nov 13 '17 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.