You have a garden with n flowers lined up in a row. The height of ith flower is a_{i} units. You will water them for k days. In one day you can water w continuous flowers (you can do this only once in a single day). Whenever you water a flower its height increases by 1 unit. You need to maximize the height of the smallest flower all the time.
Example 1:
Input:
n=6
k=2
w=3
a[]={2,2,2,2,1,1}
Output:
2
Explanation:
Water last three flowers for first day & 
first three flowers for second day.The 
new heights will be {3,3,3,3,2,2}
Example 2:
Input:
n=2
k=5
w=1
a[]={5,8}
Output:
9
Explanation:
For the first four days water the first flower then
water the last flower once.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function maximizeMinHeight() which takes the array a[], its size N, integer K, and an integer W as input parameters and returns the maximum height possible for the smallest flower.
Expected Time Complexity: O(NLogN)
Expected Space Complexity: O(N)
Constraints:
1 <= n<= 10^{5}
1<=w<=n
1<=k<=10^{5}
1 <= a[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Data structures

Starter code: #User function Template for python3



class Solution():

    def maximizeMinHeight(self, n, k, w, a):

        #your code goes here

Solutions:
class Solution:

	def maximizeMinHeight(self, n, k, w, a):

		def _try(tar):
			mods = [0] * n
			(add, left) = (0, k)
			for i in range(n):
				add += mods[i]
				v = a[i] + add
				if v < tar:
					Δ = tar - v
					mods[i] += Δ
					if i + w < n:
						mods[i + w] -= Δ
					add += Δ
					left -= Δ
					if left < 0:
						return False
			return True
		L = min(a)
		R = L + k + 1
		while L < R:
			m = (L + R) // 2
			if _try(m):
				L = m + 1
			else:
				R = m
		return L - 1


class Solution:

	def isValid(self, arr, val, w, m):
		n = len(arr)
		difSum = [0] * n
		pref = 0
		for i in range(n):
			pref -= difSum[i]
			req = max(0, val - arr[i] - pref)
			m -= req
			pref += req
			if i + w < n:
				difSum[i + w] += req
		if m < 0:
			return False
		return True

	def maximizeMinHeight(self, n, k, w, a):
		l = 0
		r = 10 ** 9 + 1
		while l < r - 1:
			mid = (l + r) // 2
			if self.isValid(a, mid, w, k):
				l = mid
			else:
				r = mid - 1
		while r >= l:
			if self.isValid(a, r, w, k):
				return r
			r -= 1


class Solution:

	def maximizeMinHeight(self, n, k, w, a):

		def check(t, mid):
			lst = arr[:]
			for i in range(n):
				if lst[i] < mid:
					temp = mid - lst[i]
					if temp > t:
						return False
					t -= temp
					lst[i] = mid
					for j in range(i + 1, min(n, i + w)):
						lst[j] += temp
			return True
		(lo, hi) = (min(arr), min(arr) + k)
		res = None
		while lo <= hi:
			mid = (lo + hi) // 2
			if check(k, mid):
				res = mid
				lo = mid + 1
			else:
				hi = mid - 1
		return res


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		(l, h) = (min(a), 10 ** 15)

		def solve(mid):
			pre_sum = [0] * n
			cnt = 0
			for i in range(n):
				if i > 0:
					pre_sum[i] += pre_sum[i - 1]
				if a[i] + pre_sum[i] < mid:
					gg = mid - (a[i] + pre_sum[i])
					cnt += gg
					pre_sum[i] += gg
					if i + w < n:
						pre_sum[i + w] -= gg
			return cnt <= k
		while l < h:
			mid = l + h + 1 >> 1
			if solve(mid):
				l = mid
			else:
				h = mid - 1
		return l


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		high = 10 ** 9
		low = 0
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if self.isPossible(a, w, mid, k):
				low = mid + 1
				ans = max(mid, ans)
			else:
				high = mid - 1
		return ans

	def isPossible(self, arr, l, maxHeight, days):
		water = [0] * len(arr)
		for i in range(len(arr)):
			if i > 0:
				water[i] = water[i - 1]
			curHei = water[i] + arr[i]
			if i >= l:
				curHei -= water[i - l]
			if curHei < maxHeight:
				water[i] += maxHeight - curHei
				days -= maxHeight - curHei
			if days < 0:
				return False
		return True


from typing import List

class Solution:

	def isOK(self, arr: List[int], days: int, cs: int, h: int) -> bool:
		n = len(arr)
		waterSupply = [0] * n
		if arr[0] < h:
			waterSupply[0] = h - arr[0]
			days -= h - arr[0]
		if days < 0:
			return False
		for i in range(1, n):
			waterSupply[i] = waterSupply[i - 1]
			actualHeight = arr[i]
			if i >= cs:
				actualHeight += waterSupply[i] - waterSupply[i - cs]
			else:
				actualHeight += waterSupply[i]
			if actualHeight < h:
				waterSupply[i] += h - actualHeight
				days -= h - actualHeight
			if days < 0:
				return False
		return True

	def maximizeMinHeight(self, n: int, k: int, w: int, a: List[int]) -> int:
		res = -1
		mnHeight = min(a)
		mxHeight = (1 << 31) - 1
		while mnHeight <= mxHeight:
			guessHeight = (mxHeight + mnHeight) // 2
			if self.isOK(a, k, w, guessHeight) == True:
				res = guessHeight
				mnHeight = guessHeight + 1
			else:
				mxHeight = guessHeight - 1
		return res


class Solution:

	def helper(self, n, k, w, a, req):
		(res, needed) = (0, 0)
		additive = [0 for _ in range(n)]
		for i in range(n):
			if i > 0:
				additive[i] += additive[i - 1]
			if a[i] + additive[i] < req:
				needed = req - a[i] - additive[i]
				res += needed
				additive[i] += needed
				if i < n - w:
					additive[i + w] -= needed
		return res <= k

	def maximizeMinHeight(self, n, k, w, a):
		(left, right) = (1, 10000000000)
		mid = left + (right - left) // 2
		while left < mid:
			if self.helper(n, k, w, a, mid):
				left = mid
			else:
				right = mid
			mid = left + (right - left) // 2
		return mid


class Solution:

	def maximizeMinHeight(self, n, k, w, arr):

		def helper(mid):
			lis = arr.copy()
			cnt = 0
			for i in range(n):
				if lis[i] < mid:
					cnt += mid - lis[i]
					add = mid - lis[i]
					for j in range(i, min(n, i + w)):
						lis[j] += add
			return cnt <= k
		(l, r) = (1, 10 ** 9)
		ans = min(arr)
		while l <= r:
			mid = (l + r) // 2
			if helper(mid):
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans


class Solution:

	def maximizeMinHeight(self, n, k, w, a):

		def check(m, arr, c):
			for i in range(len(arr)):
				if m > arr[i]:
					x = m - arr[i]
					c -= x
					if c < 0:
						return False
					for j in range(i, min(i + w, n)):
						arr[j] += x
			return True
		l = min(a)
		h = min(a) + k
		ans = min(a)
		while l <= h:
			m = (l + h) // 2
			if check(m, a[:], k):
				ans = max(m, ans)
				l = m + 1
			else:
				h = m - 1
		return ans


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		if n == 1:
			return a[0] + k
		(minh, maxh) = (a[0], a[0])
		da = [0]
		for i in range(1, n):
			minh = min(a[i], minh)
			maxh = max(a[i], maxh)
			da.append(a[i] - a[i - 1])
		ans = minh
		maxh += k
		while minh <= maxh:
			mid = (minh + maxh) // 2
			da = [0]
			for i in range(1, n):
				da.append(a[i] - a[i - 1])
			cumsum = a[0]
			k_left = k
			flag = True
			for i in range(n):
				cumsum += da[i]
				if cumsum >= mid:
					continue
				if cumsum + k_left < mid:
					flag = False
					break
				step = mid - cumsum
				k_left -= step
				cumsum += step
				if i + w < n:
					da[i + w] -= step
			if flag:
				minh = mid + 1
				ans = max(ans, mid)
			else:
				maxh = mid - 1
		return ans


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		df = [0] * (n + w)
		df[0] = a[0]
		for j in range(1, n):
			df[j] = a[j] - a[j - 1]

		def valid(x):
			dk = k
			diff = df[:]
			prev = 0
			for l in range(n):
				cur = prev + diff[l]
				if cur < x:
					e = x - cur
					diff[l] += e
					diff[l + w] -= e
					dk -= e
					cur = x
					if dk < 0:
						return False
				prev = cur
			return True
		(lo, hi) = (0, 10 ** 10)
		while lo < hi:
			mid = (lo + hi) // 2
			if valid(mid):
				lo = mid + 1
			else:
				hi = mid
		return lo - 1


class Solution:

	def height_is_achievable(self, k, w, a, mid):
		prefix = [0] * len(a)
		for i in range(len(a)):
			if a[i] + prefix[i] >= mid:
				continue
			diff = mid - a[i] - prefix[i]
			k -= diff
			if k < 0:
				return False
			for index in range(i, i + w):
				if index >= len(prefix):
					break
				prefix[index] += diff
		return True

	def maximizeMinHeight(self, n, k, w, a):
		max_height_achievable = max(a) + k
		min_height = min(a)
		while min_height <= max_height_achievable:
			mid = (max_height_achievable + min_height) // 2
			if self.height_is_achievable(k, w, a, mid):
				min_height = mid + 1
			else:
				max_height_achievable = mid - 1
		return max_height_achievable


class Solution:

	def maximizeMinHeight(self, n, k, w, a):

		def helper(n, k, w, a, mid):
			for i in range(n):
				if a[i] < mid:
					temp = mid - a[i]
					if temp > k:
						return False
					k -= temp
					j = i
					while j < n and j < i + w:
						a[j] += temp
						j += 1
			return True
		mini = min(a)
		maxi = mini + k
		ans = 0
		while mini <= maxi:
			mid = (mini + maxi) // 2
			if helper(n, k, w, a[:], mid):
				mini = mid + 1
				ans = mid
			else:
				maxi = mid - 1
		return ans


class Solution:

	def maximizeMinHeight(self, n, k, w, ac):
		low = 1
		high = 10 ** 14
		while low < high:
			mid = (low + high) // 2
			l = [0] * n
			a = ac.copy()
			prefix_sum = 0
			prefix_add = [0] * (n + 1)
			counter = 0
			for i in range(n):
				if i >= w:
					prefix_sum -= prefix_add[i - w]
				if a[i] + prefix_sum < mid:
					to_be_added = mid - a[i] - prefix_sum
					start = min(n, i + w) - w
					prefix_add[start] += to_be_added
					prefix_sum += to_be_added
					counter += to_be_added
			if counter > k:
				high = mid
			else:
				low = mid + 1
		return low - 1


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		i = 1
		j = 10 ** 6
		ans = 10 ** 9
		while i <= j:
			mid = i + (j - i) // 2
			arr = [0] * (n + 1)
			curr = 0
			moves = 0
			for ii in range(n):
				if ii - w >= 0:
					curr -= arr[ii - w]
				if a[ii] + curr <= mid:
					arr[ii] = mid - a[ii] - curr
					curr += arr[ii]
					moves += arr[ii]
			if moves <= k:
				ans = mid
				i = mid + 1
			else:
				j = mid - 1
		return ans


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		mn = min(a)
		mx = mn + k + 1

		def f(ht):
			days = 0
			curr_ht = a[0]
			flower = [0] * (n + 1)
			diff = max(0, ht - curr_ht)
			flower[0] += diff
			days += diff
			flower[w] -= diff
			for i in range(1, n):
				flower[i] += flower[i - 1]
				curr_ht = a[i] + flower[i]
				diff = max(0, ht - curr_ht)
				flower[i] += diff
				days += diff
				if i + w < n:
					flower[i + w] -= diff
			return days <= k
		while mn < mx:
			ht = (mn + mx) // 2
			if not f(ht):
				mx = ht
			else:
				mn = ht + 1
		return mn - 1


class Solution:

	def maximizeMinHeight(self, n, k, w, a):

		def check(lvl):
			days = 0
			fls = [0] * (n + 1)
			diff = max(0, lvl - a[0])
			fls[0] = diff
			fls[w] -= diff
			days = diff
			for i in range(1, n):
				fls[i] += fls[i - 1]
				cur_ht = a[i] + fls[i]
				diff = max(0, lvl - cur_ht)
				days += diff
				fls[i] += diff
				if i + w < n:
					fls[i + w] -= diff
			return days <= k
		l = 0
		h = 1000000000
		res = -1
		while l <= h:
			mid = (l + h) // 2
			if check(mid):
				l = mid + 1
				res = mid
			else:
				h = mid - 1
		return res


class Solution:

	def check(self, arr, k, w, mid):
		ar = list(arr)
		for i in range(len(arr)):
			if ar[i] < mid:
				rem = mid - ar[i]
				if rem > k:
					return False
				k -= rem
				for j in range(i, min(i + w, len(ar))):
					ar[j] += rem
		return True

	def bin_search(self, start, end, arr, k, w):
		if start <= end:
			mid = (end + start) // 2
			if self.check(arr, k, w, mid):
				return self.bin_search(mid + 1, end, arr, k, w)
			else:
				return self.bin_search(start, mid - 1, arr, k, w)
		return start - 1

	def maximizeMinHeight(self, n, k, w, a):
		return self.bin_search(min(a), min(a) + k, a, k, w)


class Solution:

	def possible(self, mnheight, k, w, a):
		days = 0
		prefsum = 0
		dp = [0] * (n + 1)
		for i in range(n):
			prefsum += dp[i]
			height = a[i] + prefsum
			if height < mnheight:
				add = mnheight - height
				days += add
				prefsum += add
				dp[i] += add
				dp[min(n, i + w)] -= add
		return days <= k

	def maximizeMinHeight(self, n, k, w, a):
		l = min(a) + 1
		h = max(a) + k
		target = l - 1
		while l <= h:
			temp = (l + h) // 2
			if self.possible(temp, k, w, a):
				target = temp
				l = temp + 1
			else:
				h = temp - 1
		return target


class Solution:

	def isValid(self, n, l, k, w, m):
		pre = [0] * (n + 1)
		temp = 0
		for i in range(0, n):
			pre[i] += pre[i - 1]
			val = pre[i] + l[i]
			if val < m:
				pre[i] += m - val
				pre[min(n, i + w)] -= m - val
				temp += m - val
		return temp <= k

	def maximizeMinHeight(self, n, k, w, a):
		f = min(a)
		r = max(a) + k
		while f <= r:
			mid = (f + r) // 2
			if self.isValid(n, a, k, w, mid):
				f = mid + 1
			else:
				r = mid - 1
		return r


class Solution:

	def maximizeMinHeight(self, n, k, w, a):
		diff = [0] * n
		mn = a[0]
		for i in range(1, n):
			diff[i] = a[i] - a[i - 1]
			mn = min(mn, a[i])
		mx = mn + k
		ans = 0

		def isValid(k, w, tmp, a):
			for i in range(n):
				if a[i] < tmp:
					if tmp - a[i] > k:
						return False
					st = i
					inc = tmp - a[i]
					k -= inc
					if st + w >= n:
						st = max(0, n - w)
					for j in range(st, min(n, st + w)):
						a[j] += inc
			return True
		while mn <= mx:
			tmp = (mn + mx) // 2
			if isValid(k, w, tmp, a[:]):
				ans = tmp
				mn = tmp + 1
			else:
				mx = tmp - 1
		return ans


class Solution:

	def check(self, diff, k2, w, t2):
		f = 0
		for i in range(len(diff)):
			diff[i] += f
			f = diff[i]
			if diff[i] >= t2:
				continue
			k2 -= t2 - diff[i]
			if k2 < 0:
				return 0
			if i + w < len(diff):
				diff[i + w] -= t2 - diff[i]
			f = t2
		return 1

	def maximizeMinHeight(self, n, k, w, a):
		dif = [0] * n
		dif[0] = a[0]
		mi = a[0]
		for i in range(1, n):
			dif[i] = a[i] - a[i - 1]
			mi = min(a[i], mi)
		ma = mi + k
		ans = 0
		while mi <= ma:
			t = (mi + ma) // 2
			if self.check(dif.copy(), k, w, t):
				ans = t
				mi = t + 1
			else:
				ma = t - 1
		return ans


class Solution:

	def maximizeMinHeight(self, n, k, w, a):

		def func(arr):
			dibba = [0] * n
			(ad, nt) = (0, k)
			for i in range(n):
				ad += dibba[i]
				v = a[i] + ad
				if v < arr:
					res = arr - v
					dibba[i] += res
					if i + w < n:
						dibba[i + w] -= res
					ad += res
					nt -= res
					if nt < 0:
						return False
			return True
		L = min(a)
		R = L + k + 1
		while L < R:
			m = (L + R) // 2
			if func(m):
				L = m + 1
			else:
				R = m
		return L - 1