Maximize the Minimum Value After K Sublist Increments- Google Top Interview Questions

                        Solution in C++ :

#define ll long long
bool check(ll mid, vector<int>& a, int size, int k) {
    ll n = a.size();
    ll prefix[n];
    memset(prefix, 0, sizeof(prefix));
    ll sum = 0;
    ll moves = 0;

    for (ll i = 0; i < n; i++) {
        sum = sum + prefix[i];
        ll change = mid - (a[i] + sum);
        if (change > 0) {
            moves += change;
            sum = sum + change;

            if (i + size < n) prefix[i + size] -= change;
        }
    }

    return moves <= k;
}
int solve(vector<int>& a, int size, int k) {
    int n = a.size();
    ll mi = (*min_element(a.begin(), a.end()));
    ll low = mi;
    ll high = mi + k;
    ll ans = mi;

    while (low <= high) {
        ll mid = low + (high - low) / 2;
        bool x = check(mid, a, size, k);
        if (x == true) {
            ans = max(ans, mid);
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return (int)ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums, int size, int k) {
        int l = 0;
        int r = Integer.MAX_VALUE;
        int res = -1;

        while (l <= r) {
            int m = l + (r - l) / 2;
            if (possible(nums, size, k, m)) {
                res = Math.max(res, m);
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return res;
    }

    public boolean possible(int[] nums, int size, int k, int min) {
        int n = nums.length;
        int[] dec = new int[n + 1];

        int increase = 0;
        for (int i = 0; i < n; i++) {
            increase -= dec[i];
            if (increase + nums[i] < min) {
                int diff = min - (increase + nums[i]);
                k -= diff;
                if (k < 0)
                    return false;
                increase += diff;
                if (i + size < n)
                    dec[i + size] += diff;
            }
        }
        return true;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, A, size, K):
        N = len(A)

        def possible(target):
            events = [0] * N
            moves = s = 0
            for i in range(N):
                s += events[i]
                delta = target - (A[i] + s)
                if delta > 0:
                    moves += delta
                    s += delta
                    if i + size < N:
                        events[i + size] -= delta

            return moves <= K

        lo, hi = 0, 10 ** 10
        while lo < hi:
            mi = lo + hi + 1 >> 1
            if possible(mi):
                lo = mi
            else:
                hi = mi - 1
        return lo