Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.
Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.
 
Example 1:
Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:
Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. 
The difference between the maximum and minimum is 1-0 = 1.

Example 3:
Input: nums = [6,6,0,1,1,4,6]
Output: 2

Example 4:
Input: nums = [1,5,6,14,15]
Output: 1

 
Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: class Solution:
    def minDifference(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		else:
			nums.sort()
			threeZero = nums[-1] - nums[3]
			twoOne = nums[-2] - nums[2]
			oneTwo = nums[-3] - nums[1]
			zeroThree = nums[-4] - nums[0]
			return min(threeZero, twoOne, oneTwo, zeroThree)


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		n = len(nums)
		nums.sort()
		i = 3
		j = n - 1
		if n <= 4:
			return 0
		ans = float('inf')
		while i >= 0 and j >= 0:
			ans = min(ans, abs(nums[i] - nums[j]))
			i -= 1
			j -= 1
		return ans


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		a = nums
		if len(a) <= 4:
			return 0
		a.sort()
		print(a)
		return min(a[-1] - a[3], a[-2] - a[2], a[-3] - a[1], a[-4] - a[0])


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		N = len(nums) - 1
		if N < 3:
			return 0
		minVal = 2 ** 32
		nums.sort()
		for i in range(4):
			minVal = min(minVal, nums[N - 3 + i] - nums[i])
		return minVal


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) < 5:
			return 0
		max4 = max3 = max2 = max1 = -float('inf')
		min4 = min3 = min2 = min1 = float('inf')
		for i in nums:
			if i > max1:
				max4 = max3
				max3 = max2
				max2 = max1
				max1 = i
			elif i > max2 and i <= max1:
				max4 = max3
				max3 = max2
				max2 = i
			elif i > max3 and i <= max2:
				max4 = max3
				max3 = i
			elif i > max4 and i <= max3:
				max4 = i
			if i < min1:
				min4 = min3
				min3 = min2
				min2 = min1
				min1 = i
			elif i < min2 and i >= min1:
				min4 = min3
				min3 = min2
				min2 = i
			elif i < min3 and i >= min2:
				min4 = min3
				min3 = i
			elif i < min4 and i >= min3:
				min4 = i
		smallest_diff = max4 - min1
		diff = max3 - min2
		if smallest_diff > diff:
			smallest_diff = diff
		diff = max2 - min3
		if smallest_diff > diff:
			smallest_diff = diff
		diff = max1 - min4
		if smallest_diff > diff:
			smallest_diff = diff
		return smallest_diff


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		nums.sort()
		return min((x - y for (x, y) in zip(nums[-4:], nums[:4])))


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		elif len(nums) == 5:
			nums_sorted = sorted(nums)
			diff = []
			for i in range(1, len(nums)):
				diff.append(nums_sorted[i] - nums_sorted[i - 1])
			return min(diff)
		else:
			largest_four = []
			smallest_four = []
			for n in nums:
				if len(largest_four) < 4:
					heapq.heappush(largest_four, n)
					heapq.heappush(smallest_four, -n)
				else:
					heapq.heappushpop(largest_four, n)
					heapq.heappushpop(smallest_four, -n)
			smallest_four = sorted([-x for x in smallest_four])
			largest_four = sorted(largest_four)
			diff_arr = [largest_four[0] - smallest_four[0], largest_four[3] - smallest_four[3], largest_four[1] - smallest_four[1], largest_four[2] - smallest_four[2]]
		return min(diff_arr)


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		n = len(nums)
		if n <= 3:
			return 0
		nums.sort()
		return min((nums[n - 4 + i] - nums[i] for i in range(4)))


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		max_3 = sorted(nums[:4], reverse=True)
		min_3 = sorted(nums[:4])
		for i in range(4, len(nums)):
			max_3.append(nums[i])
			max_3.sort(reverse=True)
			max_3.pop()
			min_3.append(nums[i])
			min_3.sort()
			min_3.pop()
		return min([max_3[i] - min_3[3 - i] for i in range(4)])


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 3:
			return 0
		nums.sort()
		x = 0
		y = len(nums) - 1
		arr = []
		while x < y:
			arr.append(nums[x])
			arr.append(nums[y])
			x += 1
			y -= 1
		if x == y:
			arr.append(nums[x])
		arr.sort()
		self.ans = float('inf')
		self.min_diff(0, len(arr) - 1, arr, 3)
		return self.ans

	def min_diff(self, i, j, arr, depth):
		if depth == 0:
			self.ans = min(self.ans, arr[j] - arr[i])
			return
		self.min_diff(i + 1, j, arr, depth - 1)
		self.min_diff(i, j - 1, arr, depth - 1)


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		(mins, maxs) = (nums[:4], nums[:4])
		for num in nums[4:]:
			mins.append(num)
			mins.sort()
			mins.pop()
			maxs.append(num)
			maxs.sort(reverse=True)
			maxs.pop()
		maxs = maxs[::-1]
		return min((maxs[i] - mins[i] for i in range(4)))


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) < 5:
			return 0
		nums = sorted(nums)
		print(nums)
		n = len(nums) - 1
		return min(nums[n] - nums[3], nums[n - 1] - nums[2], nums[n - 2] - nums[1], nums[n - 3] - nums[0])


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		nums = sorted(nums)
		(l, r) = (0, len(nums) - 1)
		res = nums[-1] - nums[0]
		for i in range(0, 4):
			res = min(res, nums[-4 + i] - nums[i])
		return res


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		(maxHeap, minHeap) = ([], [])
		import heapq
		for e in nums:
			heappush(maxHeap, e)
			heappush(minHeap, e * -1)
			if len(maxHeap) > 4:
				heappop(maxHeap)
				heappop(minHeap)
		minHeap = sorted([-1 * e for e in minHeap])
		res = float('inf')
		for i in range(4):
			res = min(res, heappop(maxHeap) - minHeap[i])
		return res


import copy
from typing import List
import numpy
import sys

class Solution:

	def minDifference(self, nums: List[int]) -> int:
		result = 0
		if len(nums) <= 4:
			return 0
		nums.sort()
		result = sys.maxsize
		result = min(result, nums[-1] - nums[3])
		result = min(result, nums[-2] - nums[2])
		result = min(result, nums[-3] - nums[1])
		result = min(result, nums[-4] - nums[0])
		return result


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		nums.sort()
		r1 = max(nums[0:-3]) - min(nums[0:-3])
		r2 = max(nums[1:-2]) - min(nums[1:-2])
		r3 = max(nums[2:-1]) - min(nums[2:-1])
		r4 = max(nums[3:]) - min(nums[3:])
		return min(r1, r2, r3, r4)


from heapq import heappush, heappop

class Solution:

	def minDifference(self, nums: List[int]) -> int:
		max_h = []
		min_h = []
		for i in nums:
			heappush(max_h, i)
			heappush(min_h, -i)
			if len(max_h) > 4:
				heappop(max_h)
				heappop(min_h)
		min_h = [-item for item in min_h]
		max_h.sort()
		min_h.sort()
		return min([max_h[i] - min_h[i] for i in range(len(max_h))])


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		nums.sort()
		return min((a - b for (a, b) in zip(nums[-4:], nums[:4])))


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		nums.sort()
		result = nums[-1] - nums[0]
		x = min(4, len(nums))
		for i in range(x):
			curr = nums[-x + i] - nums[i]
			result = min(result, curr)
		return result


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		nums.sort()
		if len(nums) <= 4:
			return 0
		res = float('inf')
		n = len(nums)
		for i in range(4):
			res = min(res, nums[n - 4 + i] - nums[i])
		return res


class Solution:

	def minDifference(self, A: List[int]) -> int:
		if len(A) <= 4:
			return 0
		A = sorted(A)
		res = math.inf
		for i in range(4):
			res = min(res, A[len(A) - i - 1] - A[3 - i])
		return res


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		nums.sort()
		print(nums)
		cur = max(nums) - min(nums)
		h1 = nums[0]
		nums[0] = nums[-1]
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		nums[0] = h1
		(h1, h2) = (nums[0], nums[1])
		(nums[0], nums[1]) = (nums[-1], nums[-1])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[0], nums[1]) = (h1, h2)
		(h1, h2, h3) = (nums[0], nums[1], nums[2])
		(nums[0], nums[1], nums[2]) = (nums[-1], nums[-1], nums[-1])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[0], nums[1], nums[2]) = (h1, h2, h3)
		(h1, h2, h3) = (nums[-1], nums[-2], nums[-3])
		(nums[-1], nums[-2], nums[-3]) = (nums[0], nums[0], nums[0])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[-1], nums[-2], nums[-3]) = (h1, h2, h3)
		(h1, h2) = (nums[-1], nums[-2])
		(nums[-1], nums[-2]) = (nums[0], nums[1])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[-1], nums[-2]) = (h1, h2)
		h1 = nums[-1]
		nums[-1] = nums[0]
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		nums[-1] = h1
		(h1, h2, h3) = (nums[0], nums[1], nums[-1])
		(nums[0], nums[1], nums[-1]) = (nums[2], nums[2], nums[2])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[0], nums[1], nums[-1]) = (nums[-2], nums[-2], nums[-2])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[0], nums[1], nums[-1]) = (h1, h2, h3)
		(h1, h2, h3) = (nums[0], nums[-1], nums[-2])
		(nums[0], nums[-1], nums[-2]) = (nums[1], nums[1], nums[1])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[0], nums[-1], nums[-2]) = (nums[-3], nums[-3], nums[-3])
		if max(nums) - min(nums) < cur:
			cur = max(nums) - min(nums)
		(nums[0], nums[-1], nums[-2]) = (h1, h2, h3)
		return cur


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		n = len(nums)
		if n < 5:
			return 0
		nums.sort()
		return min(nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1], nums[-4] - nums[0])


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) < 4:
			return 0
		from collections import Counter
		dic = sorted(Counter(nums).items())
		res = [dic[0][0]]
		if dic[0][1] > 3:
			res += [dic[0][0]] * 3
		elif dic[0][1] == 3:
			res += [dic[0][0]] * 2
			res.append(dic[1][0])
		elif dic[0][1] == 2:
			res.append(dic[0][0])
			res.append(dic[1][0])
			if dic[1][1] > 1:
				res.append(dic[1][0])
			else:
				res.append(dic[2][0])
		else:
			res.append(dic[1][0])
			if dic[1][1] > 2:
				res.append(dic[1][0])
				res.append(dic[1][0])
			elif dic[1][1] == 2:
				res.append(dic[1][0])
				res.append(dic[2][0])
			else:
				res.append(dic[2][0])
				if dic[2][1] > 1:
					res.append(dic[2][0])
				else:
					res.append(dic[3][0])
		if dic[-1][1] > 3:
			res = [dic[-1][0] - res[i] for i in range(4)]
		elif dic[-1][1] == 3:
			res = [dic[-1][0] - res[i] for i in range(1, 4)] + [dic[-2][0] - res[0]]
		elif dic[-1][1] == 2:
			tmp = [dic[-1][0] - res[i] for i in range(2, 4)]
			if dic[-2][1] > 1:
				tmp += [dic[-2][0] - res[0]] + [dic[-2][0] - res[1]]
			else:
				tmp += [dic[-3][0] - res[0]] + [dic[-2][0] - res[1]]
			res = tmp
		else:
			tmp = [dic[-1][0] - res[3]]
			if dic[-2][1] > 2:
				tmp += [dic[-2][0] - res[i] for i in range(3)]
			elif dic[-2][1] == 2:
				tmp += [dic[-2][0] - res[i] for i in range(1, 3)]
				tmp += [dic[-3][0] - res[0]]
			else:
				tmp += [dic[-2][0] - res[2]]
				tmp += [dic[-3][0] - res[1]]
				if dic[-3][1] > 1:
					tmp += [dic[-3][0] - res[0]]
				else:
					tmp += [dic[-4][0] - res[0]]
			res = tmp
		return min(res)


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		n = len(nums)
		if n < 5:
			return 0
		l = []
		h = []
		for c in nums:
			heapq.heappush(l, -c)
			if len(l) > 4:
				heapq.heappop(l)
			heapq.heappush(h, c)
			if len(h) > 4:
				heapq.heappop(h)
		l = [-c for c in l]
		l.sort()
		h.sort()
		return min(h[0] - l[0], h[1] - l[1], h[2] - l[2], h[3] - l[3])


import heapq

class Solution:

	def minDifference(self, nums: List[int]) -> int:
		largest = heapq.nlargest(4, nums)
		smallest = heapq.nsmallest(4, nums)
		m = 10 ** 10
		n = len(largest)
		for i in range(n):
			m = min(m, largest[i] - smallest[n - 1 - i])
		return max(m, 0)


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		nums.sort()
		return min(abs(nums[0] - nums[-4]), abs(nums[2] - nums[-2]), abs(nums[1] - nums[-3]), abs(nums[3] - nums[-1])) if len(nums) > 4 else 0


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		l = len(nums)
		biggest = nums[:min(4, l)]
		smallest = nums[:min(4, l)]
		for i in range(4, l):
			num = nums[i]
			biggest.append(num)
			smallest.append(num)
			biggest.remove(min(biggest))
			smallest.remove(max(smallest))
		if len(biggest) < 4:
			return 0
		bfs = [(sorted(biggest), sorted(smallest), 0)]
		opt = max(biggest) - min(smallest)
		while bfs:
			(new_biggest, new_smallest, changes) = bfs.pop(0)
			if changes == 3:
				opt = min(opt, max(new_biggest) - min(new_smallest))
				continue
			bfs.append((new_biggest[:-1], list(new_smallest), changes + 1))
			bfs.append((list(new_biggest), new_smallest[1:], changes + 1))
		return opt


class Solution:

	def _util(self, nums):
		(min_heap, max_heap) = ([], [])
		for (i, x) in enumerate(nums):
			heapq.heappush(min_heap, (x, i))
			if len(min_heap) > 4:
				heapq.heappop(min_heap)
			heapq.heappush(max_heap, (-x, i))
			if len(max_heap) > 4:
				heapq.heappop(max_heap)
		return sorted([x for (x, i) in set(min_heap + [(-x, i) for (x, i) in max_heap])])

	def minDifference(self, nums: List[int]) -> int:
		lst = sorted(nums)
		result = lst[-1] - lst[0]
		x = min(4, len(lst))
		for i in range(x):
			curr = lst[-x + i] - lst[i]
			result = min(result, curr)
		return result


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		n = len(nums)
		if n < 5:
			return 0
		nums.sort()
		diff = n - 4
		ans = math.inf
		for i in range(0, n - diff):
			ans = min(ans, nums[i + diff] - nums[i])
		return ans


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) < 5:
			return 0
		ns = sorted(nums)
		mindif = ns[-4] - ns[0]
		for i in range(1, 4):
			if ns[i - 4] - ns[i] < mindif:
				mindif = ns[i - 4] - ns[i]
		return mindif


import heapq

class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		if len(nums) == 5:
			nums.sort()
			return min((b - a for (a, b) in zip(nums, nums[1:])))
		a = heapq.nsmallest(4, nums)
		b = heapq.nlargest(4, nums)
		arr = a + b
		arr.sort()
		return min(arr[4] - arr[0], arr[5] - arr[1], arr[6] - arr[2], arr[7] - arr[3])


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 3:
			return 0
		nums.sort()
		min_diff = nums[-1] - nums[3]
		for i in range(3):
			min_diff = min(min_diff, nums[-2 - i] - nums[3 - i - 1])
		return min_diff


class Solution:

	def minDifference(self, A: List[int]) -> int:
		if len(A) <= 4:
			return 0
		max_vals = [0] * 4
		min_vals = [math.inf] * 4
		for a in A:
			for i in range(4):
				if a > max_vals[i]:
					max_vals[i + 1:] = max_vals[i:-1]
					max_vals[i] = a
					break
			for i in range(4):
				if a < min_vals[i]:
					min_vals[i + 1:] = min_vals[i:-1]
					min_vals[i] = a
					break
		res = math.inf
		for i in range(4):
			res = min(res, max_vals[i] - min_vals[3 - i])
		return res


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		nums.sort()
		l = nums[0:4]
		r = nums[-4:]
		p = 0
		res = float('inf')
		while p < 4:
			res = min(res, r[p] - l[p])
			p += 1
		return res


import heapq

class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		minheap = []
		maxheap = []
		for (j, num) in enumerate(nums):
			if len(minheap) < 4:
				heapq.heappush(minheap, -num)
			else:
				x = heapq.heappop(minheap)
				if x > -num:
					heapq.heappush(minheap, x)
				else:
					heapq.heappush(minheap, -num)
			if len(maxheap) < 4:
				heapq.heappush(maxheap, num)
			else:
				x = heapq.heappop(maxheap)
				if x > num:
					heapq.heappush(maxheap, x)
				else:
					heapq.heappush(maxheap, num)
		minheap = [-x for x in minheap]
		minheap.sort()
		maxheap.sort()
		diff = [maxheap[-1] - minheap[-1], maxheap[0] - minheap[0], maxheap[-2] - minheap[2], maxheap[-3] - minheap[1]]
		return min(diff)


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) < 5:
			return 0
		a = sorted(nums)
		H = len(nums) - 4
		L = 0
		lowest_diff = None
		for i in range(4):
			diff = a[H] - a[L]
			if lowest_diff == None or lowest_diff > diff:
				lowest_diff = diff
			H += 1
			L += 1
		return lowest_diff


class Solution:

	def minDifference(self, nums: List[int]) -> int:
		if len(nums) <= 4:
			return 0
		nums.sort()
		(a1, a2, a3, a4) = nums[:4]
		print(a1, a2, a3, a4)
		(b4, b3, b2, b1) = nums[-4:]
		return min(b4 - a1, b3 - a2, b2 - a3, b1 - a4)