Given an array arr[] denoting heights of N towers and a positive integer K. 
For each tower, you must perform exactly one of the following operations exactly once.
Increase the height of the tower by K
Decrease the height of the tower by K
Find out the minimum possible difference between the height of the shortest and tallest towers after you have modified each tower.
You can find a slight modification of the problem here.
Note: It is compulsory to increase or decrease the height by K for each tower. After the operation, the resultant array should not contain any negative integers.
Example 1:
Input:
K = 2, N = 4
Arr[] = {1, 5, 8, 10}
Output:
5
Explanation:
The array can be modified as 
{1+k, 5-k, 8-k, 10-k} = {3, 3, 6, 8}. 
The difference between 
the largest and the smallest is 8-3 = 5.
Example 2:
Input:
K = 3, N = 5
Arr[] = {3, 9, 12, 16, 20}
Output:
11
Explanation:
The array can be modified as
{3+k, 9+k, 12-k, 16-k, 20-k} -> {6, 12, 9, 13, 17}. 
The difference between 
the largest and the smallest is 17-6 = 11. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getMinDiff() which takes the arr[], n, and k as input parameters and returns an integer denoting the minimum difference.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints
1 ≤ K ≤ 10^{4}
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def getMinDiff(self, arr, n, k):

        # code here

Solutions:
class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			max_ = max(arr[i - 1] + k, arr[-1] - k)
			min_ = min(arr[i] - k, arr[0] + k)
			ans = min(ans, max_ - min_)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		tmin = arr[0]
		tmax = arr[n - 1]
		ans = tmax - tmin
		for i in range(1, n):
			if arr[i] < k:
				continue
			tmin = min(arr[0] + k, arr[i] - k)
			tmax = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, tmax - tmin)
		return ans


import sys

class Solution:

	def getMinDiff(self, arr, n, k):
		arr = sorted(arr)
		ans = arr[n - 1] - arr[0]
		temp_min = arr[0]
		temp_max = arr[n - 1]
		for i in range(1, n):
			if arr[i] < k:
				continue
			temp_min = min(arr[0] + k, arr[i] - k)
			temp_max = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, temp_max - temp_min)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			mini = min(arr[0] + k, arr[i] - k)
			maxi = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, maxi - mini)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			tempmin = min(arr[0] + k, arr[i] - k)
			tempmax = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, tempmax - tempmin)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			max1 = max(arr[i - 1] + k, arr[-1] - k)
			min1 = min(arr[i] - k, arr[0] + k)
			ans = min(ans, max1 - min1)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		if n == 1:
			return 0
		arr.sort()
		smallest = arr[0]
		largest = arr[n - 1]
		ans = arr[n - 1] - arr[0]
		for i in range(1, len(arr)):
			if arr[i] - k < 0:
				continue
			mi = min(arr[0] + k, arr[i] - k)
			ma = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, ma - mi)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] >= k:
				max_val = max(arr[i - 1] + k, arr[-1] - k)
				min_val = min(arr[0] + k, arr[i] - k)
				ans = min(ans, max_val - min_val)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		sm = arr[0] + k
		lg = arr[-1] - k
		diff = arr[-1] - arr[0]
		for i in range(n - 1):
			if arr[i + 1] >= k:
				mx = max(lg, arr[i] + k)
				mn = min(sm, arr[i + 1] - k)
				diff = min(mx - mn, diff)
		return diff


class Solution:

	def getMinDiff(self, arr, n, k):
		if n == 1:
			return 0
		arr.sort()
		initialDiff = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			newMin = min(arr[0] + k, arr[i] - k)
			newMax = max(arr[i - 1] + k, arr[-1] - k)
			newDiff = newMax - newMin
			if newDiff < initialDiff:
				initialDiff = newDiff
		return initialDiff


class Solution:

	def getMinDiff(self, arr, n, k):
		if n == 1:
			return 0
		arr.sort()
		initial_diff = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			new_min = min(arr[0] + k, arr[i] - k)
			new_max = max(arr[i - 1] + k, arr[-1] - k)
			new_diff = new_max - new_min
			if new_diff < initial_diff:
				initial_diff = new_diff
		return initial_diff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			max_ele = max(arr[i - 1] + k, arr[-1] - k)
			min_ele = min(arr[i] - k, arr[0] + k)
			ans = min(ans, max_ele - min_ele)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		diff = arr[n - 1] - arr[0]
		sml = arr[0] + k
		tall = arr[n - 1] - k
		for i in range(0, n - 1):
			mi = min(sml, arr[i + 1] - k)
			ma = max(tall, arr[i] + k)
			if mi < 0:
				continue
			else:
				diff = min(diff, ma - mi)
		return diff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		l = arr[0] + k
		r = arr[n - 1] - k
		res = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			maxi = max(r, arr[i - 1] + k)
			mini = min(l, arr[i] - k)
			res = min(res, maxi - mini)
		return res


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(n):
			if arr[i] < k:
				continue
			tmi = min(arr[0] + k, arr[i] - k)
			tma = max(arr[-1] - k, arr[i - 1] + k)
			ans = min(tma - tmi, ans)
		return ans


import sys

class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		mi = arr[0]
		ma = arr[n - 1]
		dif = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			mi = min(arr[0] + k, arr[i] - k)
			ma = max(arr[n - 1] - k, arr[i - 1] + k)
			dif = min(dif, ma - mi)
		return dif


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		m = arr[0] + k
		maxx = arr[-1] - k
		ans = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			m = min(arr[0] + k, arr[i] - k)
			maxx = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, maxx - m)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		sma = arr[0] + k
		lar = arr[-1] - k
		for i in range(n - 1):
			mi = min(sma, arr[i + 1] - k)
			ma = max(lar, arr[i] + k)
			if mi < 0:
				continue
			ans = min(ans, ma - mi)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		res = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] >= k:
				new_max = max(arr[i - 1] + k, arr[n - 1] - k)
				new_min = min(arr[0] + k, arr[i] - k)
				res = min(res, new_max - new_min)
		return res


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		maxh = arr[n - 1]
		minh = arr[0]
		ans = maxh - minh
		for i in range(n):
			if arr[i] < k:
				continue
			minh = min(arr[0] + k, arr[i] - k)
			maxh = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, maxh - minh)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		minHeight = arr[0]
		maxHeight = arr[n - 1]
		ans = maxHeight - minHeight
		for i in range(1, n):
			if arr[i] < k:
				continue
			minHeight = min(arr[0] + k, arr[i] - k)
			maxHeight = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, maxHeight - minHeight)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(1, n):
			x = max(arr[0] + k, arr[i - 1] + k, arr[i] - k, arr[-1] - k)
			y = min(arr[0] + k, arr[i - 1] + k, arr[i] - k, arr[-1] - k)
			if y >= 0:
				ans = min(ans, x - y)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		res = arr[n - 1] - arr[0]
		mintemp = arr[0]
		maxtemp = arr[n - 1]
		for i in range(1, n):
			if arr[i] < k or arr[n - 1] < k:
				continue
			mintemp = min(arr[0] + k, arr[i] - k)
			maxtemp = max(arr[i - 1] + k, arr[n - 1] - k)
			res = min(res, maxtemp - mintemp)
		return res


class Solution:

	def getMinDiff(self, arr, n, k):
		arr = sorted(arr)
		minDiff = arr[n - 1] - arr[0]
		if arr[n - 1] - k <= 0:
			return minDiff
		for i in range(1, n):
			if arr[i] - k >= 0:
				minH = min(arr[0] + k, arr[i] - k)
				maxH = max(arr[n - 1] - k, arr[i - 1] + k)
				minDiff = min(minDiff, maxH - minH)
		return minDiff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			minheight = min(arr[0] + k, arr[i] - k)
			maxheight = max(arr[n - 1] - k, arr[i - 1] + k)
			ans = min(ans, maxheight - minheight)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		diff = arr[n - 1] - arr[0]
		if n == 1:
			return 0
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			Max = max(arr[i - 1] + k, arr[n - 1] - k)
			Min = min(arr[0] + k, arr[i] - k)
			diff = min(diff, Max - Min)
		return diff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			small = min(arr[0] + k, arr[i] - k)
			largest = max(arr[n - 1] - k, arr[i - 1] + k)
			ans = min(ans, largest - small)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		ar = sorted(arr)
		a = ar[0] + k
		b = ar[n - 1] - k
		mina = 0
		maxb = 0
		res = ar[n - 1] - ar[0]
		for i in range(1, n):
			if ar[i] - k >= 0:
				mina = min(a, ar[i] - k)
				maxb = max(b, ar[i - 1] + k)
				res = min(res, maxb - mina)
		return res


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(1, n):
			if arr[i] >= k:
				maxH = max(arr[-1] - k, arr[i - 1] + k)
				minH = min(arr[0] + k, arr[i] - k)
				ans = min(ans, maxH - minH)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		if n == 1:
			return 0
		ans = arr[-1] - arr[0]
		lar = arr[-1] - k
		sm = arr[0] + k
		for i in range(n - 1):
			a = min(sm, arr[i + 1] - k)
			b = max(lar, arr[i] + k)
			if a < 0:
				continue
			ans = min(ans, b - a)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			small_tower = min(arr[0] + k, arr[i] - k)
			high_tower = max(arr[n - 1] - k, arr[i - 1] + k)
			ans = min(ans, high_tower - small_tower)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		min_element = arr[0]
		max_element = arr[n - 1]
		result = max_element - min_element
		for i in range(n):
			if arr[i] >= k:
				minimum = min(arr[i] - k, arr[0] + k)
				maximum = max(arr[i - 1] + k, arr[n - 1] - k)
				result = min(result, maximum - minimum)
		return result


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		minimum = arr[0]
		maximum = arr[n - 1]
		ans = maximum - minimum
		for i in range(1, n):
			if arr[i] >= k:
				minimum = min(arr[0] + k, arr[i] - k)
				maximum = max(arr[n - 1] - k, arr[i - 1] + k)
				ans = min(ans, maximum - minimum)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		ans = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			curMin = min(arr[0] + k, arr[i] - k)
			curMax = max(arr[i - 1] + k, arr[n - 1] - k)
			ans = min(ans, abs(curMax - curMin))
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		min_diff = arr[n - 1] - arr[0]
		for i in range(1, n):
			if arr[i] < k:
				continue
			max_elem = max(arr[i - 1] + k, arr[n - 1] - k)
			min_elem = min(arr[0] + k, arr[i] - k)
			min_diff = min(min_diff, max_elem - min_elem)
		return min_diff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		min_element = arr[0]
		max_element = arr[n - 1]
		result = max_element - min_element
		for i in range(1, n):
			if arr[i] - k < 0:
				continue
			max_element = max(arr[i - 1] + k, arr[n - 1] - k)
			min_element = min(arr[i] - k, arr[0] + k)
			ans = max_element - min_element
			result = min(result, ans)
		return result


class Solution:

	def getMinDiff(self, a, n, k):
		a.sort()
		ans = a[n - 1] - a[0]
		tempMax = a[n - 1]
		tempMin = a[0]
		for i in range(1, n):
			if a[i] < k:
				continue
			tempMin = min(a[0] + k, a[i] - k)
			tempMax = max(a[i - 1] + k, a[n - 1] - k)
			ans = min(tempMax - tempMin, ans)
		return ans