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