Given an array arr[] denoting heights of N towers and a positive integer K, you have to modify the height of each tower either by increasing or decreasing them by K only once.
Find out what could be the possible minimum difference of the height of shortest and longest towers after you have modified each tower.
Note: Assume that height of the tower can be negative.
A slight modification of the problem can be found here. 
Example 1:
Input:
K = 2, N = 4
Arr[] = {1, 5, 8, 10}
Output:
5
Explanation:
The array can be modified as 
{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
{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

Amortized analysis

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[n - 1] - arr[0]
		for i in range(1, n):
			ans = min(ans, max(arr[i - 1] + k, arr[n - 1] - k) - min(arr[0] + k, arr[i] - k))
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		arr = sorted(arr)
		minimum = arr[0]
		maximum = arr[n - 1]
		res = maximum - minimum
		for i in range(len(arr)):
			minimum = min(arr[i] - k, arr[0] + k)
			maximum = max(arr[i - 1] + k, arr[n - 1] - k)
			res = min(maximum - minimum, res)
		return res


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		arr = sorted(arr)
		high = arr[n - 1]
		diff = high - arr[0]
		for i in range(1, n):
			max_height = max(arr[i - 1] + k, high - k)
			min_height = min(arr[i] - k, arr[0] + k)
			diff = min(diff, max_height - min_height)
		return diff


class Solution:

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


class Solution:

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


def binarySearch(arr, elem):
	a = 0
	b = len(arr) - 1
	i = -1
	while a <= b:
		mid = (a + b) // 2
		element = arr[mid]
		if element == elem:
			i = mid
		if element >= elem:
			b = mid - 1
		else:
			a = mid + 1
	return i

class Solution:

	def getMinDiff(self, arr, n, k):
		heights = [0 for i in range(2 * n)]
		for i in range(n):
			height = arr[i]
			heights[i] = height + k
			heights[i + n] = height - k
		heights.sort()
		i = 0
		j = binarySearch(heights, heights[-1] - 2 * k)
		minSumDiff = -1
		leftElemMax = heights[0] + 2 * k
		while i < 2 * n and heights[i] <= leftElemMax:
			diff = heights[j] - heights[i]
			if minSumDiff == -1 or diff < minSumDiff:
				minSumDiff = diff
			leftH = heights[i]
			while heights[i] == leftH:
				i += 1
				if i == 2 * n:
					break
			while heights[j] < leftH + 2 * k:
				j += 1
				if j == 2 * n:
					break
		return minSumDiff


import numpy as np
import math

class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		arr = np.array(arr)
		minz = math.inf
		minimum = arr[0]
		maximum = arr[-1]
		minz = min(minz, maximum - minimum)
		arr = arr + k
		minimum = arr[0]
		maximum = arr[-1]
		minz = min(minz, maximum - minimum)
		right_max = -math.inf
		for i in range(-1, -n - 1, -1):
			arr[i] = arr[i] - 2 * k
			right_max = max(right_max, arr[i])
			if arr[i] < minimum:
				minimum = arr[i]
			if i == -1:
				maximum = max(arr)
			elif i > -n:
				maximum = max(arr[i - 1], right_max)
			else:
				maximum = right_max
			minz = min(minz, maximum - minimum)
		return minz


class Solution:

	def getMinDiff(self, arr, n, k):
		arr = sorted(arr)
		d = arr[n - 1] - arr[0]
		t = arr[n - 1]
		f = arr[0]
		for i in range(1, n):
			t = max(arr[i - 1] + k, arr[n - 1] - k)
			f = min(arr[0] + k, arr[i] - k)
			d = min(d, t - f)
		return d


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		maxo = arr[-1]
		mino = arr[0]
		out = maxo - mino
		for i in range(1, n):
			maxo = max(arr[i - 1] + k, arr[-1] - k)
			mino = min(arr[i] - k, arr[0] + k)
			out = min(out, maxo - mino)
		return out


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		i = 0
		ans = 1000000000.0
		while i < n:
			mn = min([arr[0], arr[i] - k])
			if i > 0:
				mx = max([arr[n - 1] - k, arr[i - 1]])
			else:
				mx = arr[n - 1] - k
			ans = min([ans, mx - mn])
			arr[i] += k
			i += 1
		ans = min([ans, arr[n - 1] - arr[0]])
		return ans


class Solution:

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


class Solution:

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


from heapq import heappush, heappop

class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort(reverse=True)
		nums = [n + k for n in arr]
		ans = nums[0] - nums[-1]
		for i in range(n - 1):
			nums[i] -= k
			nums[i] -= k
			maxNums = max(nums[0], nums[i + 1])
			minNums = min(nums[-1], nums[i])
			ans = min(ans, maxNums - minNums)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		minDiff = arr[n - 1] - arr[0]
		for i in range(1, n):
			currMax = max(arr[i - 1] + k, arr[n - 1] - k)
			currMin = min(arr[i] - k, arr[0] + k)
			minDiff = min(minDiff, currMax - currMin)
		return minDiff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		result = arr[n - 1] - arr[0]
		for i in range(n - 1):
			min_height = min(arr[0] + k, arr[i + 1] - k)
			max_height = max(arr[n - 1] - k, arr[i] + k)
			result = min(result, max_height - min_height)
		return result


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		(minVal, maxVal) = (arr[0], arr[-1])
		minDiff = maxVal - minVal
		for i in range(1, n):
			minVal = min(arr[0] + k, arr[i] - k)
			maxVal = max(arr[-1] - k, arr[i - 1] + k)
			minDiff = min(minDiff, maxVal - minVal)
		return minDiff


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		sorted_array = sorted(arr)
		difference = sorted_array[-1] - sorted_array[0]
		for i in range(1, n):
			min_ = min(sorted_array[0] + k, sorted_array[i] - k)
			max_ = max(sorted_array[-1] - k, sorted_array[i - 1] + k)
			difference = min(difference, max_ - min_)
		return difference


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		sum_min = arr[0]
		diff_max = arr[-1]
		a = diff_max - sum_min
		for i in range(1, n):
			diff_max = max(arr[i - 1] + k, arr[-1] - k)
			sum_min = min(arr[i] - k, arr[0] + k)
			a = min(a, diff_max - sum_min)
		return a


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		min_diff = arr[-1] - arr[0]
		for i in range(n - 1):
			min_tower = min(arr[0] + k, arr[i + 1] - k)
			max_tower = max(arr[i] + k, arr[-1] - k)
			diff = max_tower - min_tower
			min_diff = min(min_diff, diff)
			min_tower = min(arr[i + 1] - k, arr[0] + k)
			max_tower = max(arr[i] + k, arr[-1] - k)
			diff = max_tower - min_tower
			min_diff = min(min_diff, diff)
		return min_diff


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		small = arr[0]
		large = arr[n - 1]
		res = large - small
		for i in range(1, n):
			tempSmall = min(arr[i] - k, small + k)
			tempLarge = max(arr[i - 1] + k, large - k)
			res = min(res, tempLarge - tempSmall)
		return res


import numpy as np

class Solution:

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


from math import ceil

class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		diff = arr[-1] - arr[0]
		if diff <= k:
			return diff
		lo = arr[0] + k
		hi = arr[-1] - k
		min_diff = diff
		for i in range(0, n - 1):
			highest = max(arr[i] + k, hi)
			lowest = min(arr[i + 1] - k, lo)
			min_diff = min(min_diff, highest - lowest)
		return min_diff


class Solution:

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


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		arr = sorted(arr)
		MAX = arr[-1]
		MIN = arr[0]
		ans = MAX - MIN
		for i in range(n - 1):
			MIN = min(arr[0] + k, arr[i + 1] - k)
			MAX = max(arr[n - 1] - k, arr[i] + k)
			ans = min(ans, MAX - MIN)
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		v = []
		taken = [0] * n
		for i in range(n):
			v.append([arr[i] - k, i])
			v.append([arr[i] + k, i])
		v.sort()
		elements_in_range = 0
		left = right = 0
		while elements_in_range < n and right < len(v):
			if taken[v[right][1]] == 0:
				elements_in_range += 1
			taken[v[right][1]] += 1
			right += 1
		ans = v[right - 1][0] - v[left][0]
		while right < len(v):
			if taken[v[left][1]] == 1:
				elements_in_range -= 1
			taken[v[left][1]] -= 1
			left += 1
			while elements_in_range < n and right < len(v):
				if taken[v[right][1]] == 0:
					elements_in_range += 1
				taken[v[right][1]] += 1
				right += 1
			if elements_in_range == n:
				ans = min(ans, v[right - 1][0] - v[left][0])
			else:
				break
		return ans


class Solution:

	def getMinDiff(self, arr, n, k):
		point = arr
		point.sort()
		currentMin = point[0]
		currentMax = point[-1]
		minSum = abs(currentMax - currentMin)
		for i in range(1, n):
			currentMin = min(point[0] + k, point[i] - k)
			currentMax = max(point[i - 1] + k, point[-1] - k)
			minSum = min(minSum, abs(currentMax - currentMin))
		return minSum


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		max1 = arr[-1]
		min2 = arr[0]
		out = max1 - min2
		for i in range(1, n):
			max1 = max(arr[i - 1] + k, arr[-1] - k)
			min2 = min(arr[i] - k, arr[0] + k)
			out = min(out, max1 - min2)
		return out


class Solution:

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


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		t = sorted(arr)
		max1 = t[n - 1]
		min1 = t[0]
		res = max1 - min1
		for i in range(n):
			max1 = max(t[i - 1] + k, t[n - 1] - k)
			min1 = min(t[i] - k, t[0] + k)
			res = min(res, max1 - min1)
		return res


class Solution:

	def getMinDiff(self, arr, n, k):
		arr.sort()
		n = len(arr)
		var1 = max(arr)
		var2 = min(arr)
		result = var1 - var2
		for i in range(1, len(arr)):
			maxi = max(arr[n - 1] - k, arr[i - 1] + k)
			mini = min(arr[0] + k, arr[i] - k)
			result = min(result, maxi - mini)
		return result


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		aux = []
		for i in range(n):
			aux.append([arr[i] - k, i])
			aux.append([arr[i] + k, i])
		aux.sort(key=lambda x: x[0])
		counts = [0 for i in range(n)]
		partial_min = 1e+100
		j = 0
		index_count = 0
		for i in range(0, 2 * n):
			while index_count < n and j < 2 * n:
				counts[aux[j][1]] += 1
				if counts[aux[j][1]] == 1:
					index_count += 1
				j += 1
			if index_count == n:
				partial_min = min(partial_min, aux[j - 1][0] - aux[i][0])
			counts[aux[i][1]] -= 1
			if counts[aux[i][1]] == 0:
				index_count -= 1
		return partial_min


class Solution:

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


class Solution:

	def getMinDiff(self, arr, n, k):
		d = []
		mapped = [0 for i in range(n)]
		c = 0
		for i in range(n):
			d.append((arr[i] + k, i))
			d.append((arr[i] - k, i))
		d.sort(key=lambda x: x[0])
		j = 0
		ans = 1e+100
		for i in range(n):
			while c < n and j < 2 * n:
				if mapped[d[j][1]] == 0:
					c += 1
				mapped[d[j][1]] += 1
				j += 1
			if c == n:
				ans = min(ans, d[j - 1][0] - d[i][0])
			if mapped[d[i][1]] == 1:
				c -= 1
			mapped[d[i][1]] -= 1
		return ans


class Solution:

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