Given an array arr[] of size N and an integer K. The task is to find the minimum number of elements that should be removed, such that A_{max}-A_{min}<=K. After the removal of elements, A_{max} and A_{min} is considered among the remaining elements. 
Note: Can you solve the probelm without using any extra space and O(N*log(N)) time complexity?
Example 1:
Input: N = 9, K = 4  
arr[] = {1,3,4,9,10,11,12,17,20}
Output: 5
Explanation: Remove 1, 3, 4 from beginning
and 17, 20 from the end.
Example 2:
Input: N = 5, K = 2 
arr[] = {1, 5, 6, 2, 8} 
Output: 3
Explanation: There are multiple ways to
remove elements in this case.
One among them is to remove 5, 6, 8.
The other is to remove 1, 2, 5
Your Task:
You don't need to read input or print anything. Your task is to complete the function removals() which takes the array of integers arr, n and k as parameters and returns an integer, denotes minimum number of elements should be remove to satisfy the condition.
Expected Time Complexity: O(Nlog(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 100
1 ≤ Arr[i], K ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3





class Solution:



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

		# code here

Solutions:
class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		i = 0
		j = 0
		ans = 0
		while j < n:
			if arr[j] - arr[i] <= k:
				j += 1
			elif arr[j] - arr[i] > k:
				i += 1
			ans = max(ans, j - i)
		return n - ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = 0
		for i in range(len(arr)):
			left = 0
			right = i
			res = 0
			while left <= right:
				mid = (left + right) // 2
				if arr[i] - arr[mid] > k:
					left = mid + 1
				else:
					res = mid
					right = mid - 1
			ans = max(ans, i - res + 1)
		return len(arr) - ans


class Solution:

	def removals(self, arr, n, k):
		arr = sorted(arr)
		(left, right) = (0, 0)
		maxLength = 0
		while right < n:
			if arr[right] - arr[left] <= k:
				right += 1
			else:
				while arr[right] - arr[left] > k and right > left:
					left += 1
			maxLength = max(maxLength, right - left)
		return n - maxLength


import sys

class Solution:

	def removals(self, arr, n, k):
		L = sorted(arr)
		ans = sys.maxsize
		for i in range(n):
			num = i
			for j in range(n - 1, -1, -1):
				if L[j] - L[i] <= k:
					ans = min(ans, num)
					break
				num += 1
		return ans


class Solution:

	def removals(self, arr, n, k):
		t = 0
		arr.sort()
		(i, j) = (0, 0)
		while j < n:
			if arr[j] - arr[i] <= k:
				if t < j - i:
					t = j - i
				j = j + 1
			else:
				i = i + 1
		return n - (t + 1)


class Solution:

	def removals(self, arr, n, k):
		arr = sorted(arr)
		i = 0
		j = 0
		m = 0
		while j < n:
			if arr[j] - arr[i] <= k:
				j = j + 1
			elif i < j:
				i = i + 1
			m = max(m, j - i)
		return n - m


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		d = {}

		def fun(i, j):
			if arr[j] - arr[i] <= k:
				return 0
			if (i, j) in d:
				return d[i, j]
			d[i, j] = 1 + min(fun(i + 1, j), fun(i, j - 1))
			return d[i, j]
		return fun(0, n - 1)


class Solution:

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

		def solve(arr, i, j, k, dp):
			if arr[j] - arr[i] <= k:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			first = 1 + solve(arr, i + 1, j, k, dp)
			last = 1 + solve(arr, i, j - 1, k, dp)
			dp[i][j] = min(first, last)
			return min(first, last)
		arr.sort()
		dp = [[-1 for y in range(n + 1)] for x in range(n + 1)]
		return solve(arr, 0, n - 1, k, dp)


class Solution:

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

		def manu(arr, i, j, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if arr[j] - arr[i] <= k:
				return j - i + 1
			dp[i][j] = max(manu(arr, i + 1, j, dp), manu(arr, i, j - 1, dp))
			return dp[i][j]
		arr = sorted(arr)
		dp = [[-1 for i in range(n)] for i in range(n)]
		return n - manu(arr, 0, n - 1, dp)


from bisect import bisect_right

class Solution:

	def removals(self, a, n, k):
		a.sort()
		maxl = 0
		for i in range(n):
			j = bisect_right(a, a[i] + k, i + 1)
			maxl = max(maxl, j - i)
		return n - maxl


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		right = n - 1
		result = 0
		left = 0
		for i in range(0, n):
			if arr[i] - arr[left] <= k:
				result = max(result, i - left + 1)
			else:
				left += 1
			if left >= n:
				break
		return n - result


class Solution:

	def removals(self, arr, n, k):
		arr = sorted(arr)
		count = 0
		diffarr = []
		for i in range(n - 1):
			diff = arr[i + 1] - arr[i]
			diffarr.append(diff)
		_sum = 0
		cnt = 0
		maxcnt = 0
		for i in range(n - 1):
			if _sum + diffarr[i] <= k:
				_sum += diffarr[i]
				cnt += 1
			elif sum != 0:
				_sum = _sum - diffarr[i - cnt] + diffarr[i]
			maxcnt = max(cnt, maxcnt)
		count = n - maxcnt - 1
		return count


class Solution:

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

		def func(ind1, ind2, k, dp, arr):
			if ind1 > ind2:
				return 0
			if dp[ind1][ind2] != -1:
				return dp[ind1][ind2]
			mx = arr[ind2]
			mi = arr[ind1]
			if mx - mi <= k:
				return 0
			last = func(ind1, ind2 - 1, k, dp, arr)
			first = func(ind1 + 1, ind2, k, dp, arr)
			dp[ind1][ind2] = 1 + min(last, first)
			return dp[ind1][ind2]
		dp = [[-1 for i in range(n)] for j in range(n)]
		arr.sort()
		kk = func(0, n - 1, k, dp, arr)
		return kk


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		remove = float('inf')
		for i in range(n):
			for j in range(i, n):
				diff = arr[j] - arr[i]
				if diff <= k and n + i - j - 1 < remove:
					remove = n + i - j - 1
		return remove


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		dp = [[0 for j in range(n)] for i in range(n)]
		for gap in range(n):
			for i in range(n - gap):
				j = i + gap
				if i == j:
					dp[i][j] = 0
				elif arr[j] - arr[i] <= k:
					dp[i][j] = 0
				else:
					dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
		return dp[0][n - 1]


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = n

		def sort(arr, i, k):
			res = -1
			start = i + 1
			end = n - 1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid] - arr[i] > k:
					end = mid - 1
				else:
					start = mid + 1
					res = mid
			return res
		ans = n - 1
		for i in range(n):
			j = sort(arr, i, k)
			if j != -1:
				ans = min(ans, n - (j - i + 1))
		return ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = float('inf')
		n = len(arr)
		i = n - 1
		j = n - 1
		while i >= 0:
			if arr[j] - arr[i] <= k:
				currMin = n - (j - i + 1)
				ans = min(ans, currMin)
				i -= 1
			else:
				j -= 1
		return ans


class Solution:

	def removals(self, arr, n, k):
		idx1 = 0
		idx2 = n - 1
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		arr.sort()

		def solve(idx1, idx2):
			if idx1 > idx2:
				return 0
			if dp[idx1][idx2] != -1:
				return dp[idx1][idx2]
			mx = arr[idx2]
			mn = arr[idx1]
			if mx - mn <= k:
				return 0
			last = solve(idx1, idx2 - 1)
			first = solve(idx1 + 1, idx2)
			dp[idx1][idx2] = 1 + min(last, first)
			return dp[idx1][idx2]
		return solve(idx1, idx2)


class Solution:

	def removals(self, a, n, k):

		def recursion(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if a[j] - a[i] <= k:
				return 0
			dp[i][j] = 1 + min(recursion(i + 1, j), recursion(i, j - 1))
			return dp[i][j]
		a.sort()
		dp = [[-1 for i in range(n + 1)] for i in range(n + 1)]
		return recursion(0, n - 1)


class Solution:

	def solve(self, arr, mx, mn, k, i, j):
		if mx - mn <= k:
			return 0
		if i == j:
			return 0
		firstremoved = 1 + self.solve(arr, mx, arr[i + 1], k, i + 1, j)
		lastremoved = 1 + self.solve(arr, arr[j - 1], mn, k, i, j - 1)
		return min(firstremoved, lastremoved)

	def removals(self, arr, n, k):
		arr = sorted(arr)
		i = 0
		mx = -1
		j = 0
		while j < n and i < n:
			if arr[j] - arr[i] <= k:
				mx = max(mx, j - i + 1)
			else:
				i += 1
			j += 1
		return n - mx


from bisect import *

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = 10 ** 9
		for i in range(n):
			ind = bisect_right(arr, arr[i] + k)
			size = ind - i
			ans = min(ans, n - size)
		return ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		dp = {}

		def fun(i, j):
			if i >= j:
				if arr[j] - arr[i] <= k:
					return 0
				return 1000000
			if arr[j] - arr[i] <= k:
				return 0
			if (i, j) in dp:
				return dp[i, j]
			dp[i, j] = min(1 + fun(i + 1, j), 1 + fun(i, j - 1))
			return dp[i, j]
		t = fun(0, n - 1)
		if t >= 1000000:
			return -1
		else:
			return t


class Solution:

	def removals(self, a, n, K):
		a.sort()
		l = 0
		r = 0
		min_elem_removed = n
		while r < n:
			if a[r] - a[l] <= K:
				r += 1
			else:
				l += 1
			curr_element = n - (r - l)
			min_elem_removed = min(min_elem_removed, curr_element)
		return min_elem_removed


class Solution:

	def removals(self, a, n, K):
		if n == 1:
			if arr[0] <= K:
				return 1
			else:
				return 0
		arr.sort()
		i = 0
		j = 0
		maxsize = 0
		while j < n:
			if a[j] - a[i] <= K:
				j += 1
			elif j > i:
				i += 1
			maxsize = max(maxsize, j - i)
		return n - maxsize


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		m = 0
		N = 0
		c = 0
		while m < n and N < n:
			if arr[N] - arr[m] <= k:
				N += 1
			else:
				if N - m > c:
					c = N - m
				m += 1
		if N - m > c:
			c = N - m
		return n - c


import bisect

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = n
		for r in range(n):
			ans = min(n - bisect.bisect_right(arr, arr[r] + k) + r, ans)
		return ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		left = 0
		right = 0
		running = 0
		count = 0
		while right < len(arr):
			while left <= right and arr[right] - arr[left] > k:
				left += 1
			if arr[right] - arr[left] <= k:
				count = max(count, right - left + 1)
			right += 1
		return n - count


class Solution:

	def solve(self, i, j, k, arr, dp):
		if i >= j:
			return 0
		if arr[j] - arr[i] <= k:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		itr = 1 + self.solve(i + 1, j, k, arr, dp)
		jtr = 1 + self.solve(i, j - 1, k, arr, dp)
		dp[i][j] = min(itr, jtr)
		return dp[i][j]

	def removals(self, arr, n, k):
		arr.sort()
		i = 0
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return self.solve(i, n - 1, k, arr, dp)


class Solution:

	def removals(self, arr, n, k):
		arr = sorted(arr)
		dp = [[n + 1 for i in range(n)] for j in range(n)]
		for count in range(n):
			for i in range(n - count):
				if arr[i + count] - arr[i] <= k:
					dp[i][i + count] = 0
				else:
					dp[i][i + count] = 1 + min(dp[i + 1][i + count], dp[i][i + count - 1])
		return dp[0][-1]


from bisect import bisect

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		min_removals = n
		i = 0
		while i < n:
			j = bisect(arr, arr[i] + k, i + 1)
			min_removals = min(min_removals, i + (n - j))
			i += 1
		return min_removals


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = -10 ** 9
		for i in range(n):
			for j in range(n):
				if arr[j] - arr[i] <= k:
					ans = max(ans, j - i + 1)
		return n - ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		maxi = 0
		(start, end) = (0, 0)
		while end < n - 1:
			if arr[end] - arr[start] <= k:
				end += 1
			if arr[end] - arr[start] > k:
				while arr[end] - arr[start] > k:
					start += 1
			if end - start > maxi:
				maxi = end - start
		return len(arr) - maxi - 1


def solve(arr, k, i, j, dp):
	if i > j:
		return 0
	elif arr[j] - arr[i] <= k:
		return 0
	elif dp[i][j] != -1:
		return dp[i][j]
	else:
		right = solve(arr, k, i + 1, j, dp)
		left = solve(arr, k, i, j - 1, dp)
		dp[i][j] = 1 + min(right, left)
	return dp[i][j]

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return solve(arr, k, 0, n - 1, dp)


class Solution:

	def removals(self, arr, n, k):
		i = 0
		j = n - 1
		arr.sort()
		memo = {}
		if n == 2:
			return 1
		else:

			def remove(arr, i, j):
				key = (i, j)
				if i >= j:
					memo[key] = 0
				if arr[j] - arr[i] <= k:
					memo[key] = 0
				if key in memo:
					return memo[key]
				else:
					memo[key] = 1 + min(remove(arr, i + 1, j), remove(arr, i, j - 1))
				return memo[key]
			return remove(arr, i, j)


class Solution:

	def removals(self, arr, n, k):
		ans = 0
		arr.sort()
		for i in range(n):
			j = i + 1
			while j < n and arr[j] - arr[i] <= k:
				j += 1
			ans = max(ans, j - i)
		return n - ans


import bisect

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		if n == 1:
			return 0
		ans = n - 1
		for i in range(n):
			j = bisect.bisect_left(arr, arr[i] + k) - 1
			ans = min(ans, n - (j - i + 1))
		return ans


class Solution:

	def solve(self, arr, n, k, i, j, dp):
		if i == j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if arr[j] - arr[i] <= k:
			dp[i][j] = 0
			return dp[i][j]
		opt1 = 1 + self.solve(arr, n, k, i + 1, j, dp)
		opt2 = 1 + self.solve(arr, n, k, i, j - 1, dp)
		dp[i][j] = min(opt1, opt2)
		return dp[i][j]

	def tabular(self, arr, n, k):
		arr.sort()
		if arr[-1] - arr[0] <= k:
			return 0
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][i] = 0
		for i in range(n - 1, -1, -1):
			for j in range(n):
				if arr[j] - arr[i] <= k:
					dp[i][j] = 0
				else:
					opt1 = 1 + dp[i + 1][j]
					opt2 = 1 + dp[i][j - 1]
					dp[i][j] = min(opt1, opt2)
		return dp[0][n - 1]

	def removals(self, arr, n, k):
		arr.sort()
		if arr[-1] - arr[0] <= k:
			return 0
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return self.solve(arr, n, k, 0, n - 1, dp)


def helper(i, j, ar, kr, dp):
	if i >= j:
		return 0
	if arr[j] - arr[i] <= k:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	fr = helper(i + 1, j, arr, k, dp)
	bk = helper(i, j - 1, arr, k, dp)
	dp[i][j] = 1 + min(fr, bk)
	return dp[i][j]

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		dp = [[-1] * (n + 1) for _ in range(n + 1)]
		return helper(0, n - 1, arr, k, dp)


class Solution:

	def answer(self, i, j, arr, k, dp):
		if i >= j:
			return float('inf')
		if arr[j] - arr[i] <= k:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		t1 = 1 + self.answer(i + 1, j, arr, k, dp)
		t2 = 1 + self.answer(i, j - 1, arr, k, dp)
		t3 = 2 + self.answer(i + 1, j - 1, arr, k, dp)
		dp[i][j] = min(t1, t2, t3)
		return dp[i][j]

	def removals(self, arr, n, k):
		arr.sort()
		dp = [[0 for x in range(n)] for x in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(0, n):
				if i >= j:
					dp[i][j] = float('inf')
				elif arr[j] - arr[i] <= k:
					dp[i][j] = 0
				else:
					t1 = 1 + dp[i + 1][j]
					t2 = 1 + dp[i][j - 1]
					t3 = 2 + dp[i + 1][j - 1]
					dp[i][j] = min(t1, t2, t3)
		if dp[0][n - 1] != float('inf'):
			return dp[0][n - 1]
		else:
			return n - 1


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = float('inf')
		if n == 1:
			return 0
		for i in range(n - 1):
			e = arr[i] + k
			l = i + 1
			u = n - 1
			while l <= u:
				mid = (l + u) // 2
				if arr[mid] >= e:
					u = mid - 1
				else:
					l = mid + 1
			if l < n and arr[l] == e:
				ans = min(ans, n - l + i - 1)
			else:
				ans = min(ans, n - l + i)
		return ans


class Solution:

	def removals(self, arr, n, k):
		i = 0
		maxlen = 0
		arr.sort()
		for j in range(n):
			if arr[j] - arr[i] <= k:
				maxlen = max(maxlen, j - i + 1)
			else:
				i += 1
		return n - maxlen


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		minimum = 999999
		count = 1
		for i in range(n - 1):
			count = 1
			for j in range(i + 1, n):
				if abs(arr[i] - arr[j]) <= k:
					count += 1
				else:
					minimum = min(minimum, n - count)
					count = 1
					break
			if count > 1:
				minimum = min(minimum, n - count)
		if count == n:
			return 0
		elif count > 1:
			minimum = min(minimum, n - count)
		return minimum


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		min_remove = n - 1
		dp = [0 for _ in range(n)]
		for i in range(1, n):
			j = dp[i - 1]
			while j < i and arr[i] - arr[j] > k:
				j += 1
			dp[i] = min(dp[i], j)
			min_remove = min(min_remove, n - (i - j + 1))
		return min_remove


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		dp = [i for i in range(n)]
		min_remove = n - 1
		for i in range(1, n):
			j = dp[i - 1]
			while j < i and arr[i] - arr[j] > k:
				j += 1
			dp[i] = min(dp[i], j)
			keep_elements = i - j + 1
			remove_elements = n - keep_elements
			min_remove = min(min_remove, remove_elements)
		return min_remove


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		dp = [i for i in range(n)]
		ans = n - 1
		for i in range(1, n):
			j = dp[i - 1]
			while j < i and arr[i] - arr[j] > k:
				j += 1
			dp[i] = min(dp[i], j)
			ans = min(ans, n - (i - j + 1))
		return ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		N = n
		dp = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N - 2, -1, -1):
			for j in range(i, N):
				if arr[j] - arr[i] > k:
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
				else:
					dp[i][j] = 0
		return dp[0][n - 1]


class Solution:

	def solve(arr, k, i, j, dp):
		if i >= j:
			return 0
		elif arr[j] - arr[i] <= k:
			return 0
		elif dp[i][j] != -1:
			return dp[i][j]
		else:
			dp[i][j] = 1 + min(Solution.solve(arr, k, i + 1, j, dp), Solution.solve(arr, k, i, j - 1, dp))
		return dp[i][j]

	def removals(self, arr, n, k):
		arr.sort()
		mini = cur = 10000000000.0
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
		return Solution.solve(arr, k, 0, n - 1, dp)


class Solution:
	h = dict()

	def solve(self, arr, i, j, k):
		if arr[j] - arr[i] <= k:
			return 0
		else:
			if (i, j) in self.h:
				return self.h[i, j]
			ans = min(1 + self.solve(arr, i + 1, j, k), 1 + self.solve(arr, i, j - 1, k))
			self.h[i, j] = ans
			return ans

	def removals(self, arr, n, k):
		if n == 1:
			return 0
		else:
			arr.sort()
			ans = self.solve(arr, 0, n - 1, k)
			self.h.clear()
			return ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		if arr[-1] - arr[0] <= k:
			return 0
		dp = [[n + 1] * (n + 1)]
		for i in range(n):
			dp.append([0] * (n + 1))
			dp[-1][-1] = i
		ans = n
		for i in range(1, n + 1):
			for j in range(n - 1, i - 2, -1):
				dp[i][j] = min(dp[i - 1][j], dp[i][j + 1])
				if arr[j] - arr[i - 1] <= k:
					ans = min(ans, dp[i][j])
				else:
					dp[i][j] += 1
		return ans


class Solution:

	def removals(self, arr, n, k):
		mini = n - 1
		arr.sort()
		for i in range(n - 1, -1, -1):
			for j in range(i):
				if arr[i] - arr[j] <= k:
					mini = min(mini, n - (i - j + 1))
					break
		return mini


class Solution:

	def removals(self, arr, n, k):
		i = 0
		j = 0
		arr.sort()
		m = -1000009
		while j < n:
			d = arr[j] - arr[i]
			if d > k:
				i += 1
			else:
				m = max(m, j - i)
				j += 1
		return n - (m + 1)


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		ans = 0
		q = 0
		for p in range(n):
			while q < n and arr[q] - arr[p] <= k:
				q += 1
			ans = max(ans, q - p)
		return n - ans


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		l = 0
		length = 0
		for r in range(1, n):
			if arr[r] - arr[l] > k:
				l += 1
			length = max(length, r - l)
		return n - length - 1


class Solution:

	def removals(self, arr, n, k):
		arr = sorted(arr)
		maxi = 1
		for i in range(n):
			for j in range(i + 1, n):
				if arr[j] - arr[i] <= k:
					maxi = max(maxi, j - i + 1)
		return n - maxi


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		self.dp = [[-1] * 101 for _ in range(101)]
		if n == 1:
			return 0
		else:
			return self.countRemovals(arr, 0, n - 1, k)

	def countRemovals(self, arr, i, j, k):
		if i >= j:
			return 0
		elif arr[j] - arr[i] <= k:
			return 0
		elif self.dp[i][j] != -1:
			return self.dp[i][j]
		elif arr[j] - arr[i] > k:
			self.dp[i][j] = 1 + min(self.countRemovals(arr, i + 1, j, k), self.countRemovals(arr, i, j - 1, k))
		return self.dp[i][j]


class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		maxLen = 0
		i = 0
		for j in range(0, n):
			if arr[j] - arr[i] <= k:
				maxLen = max(maxLen, j - i + 1)
			else:
				i += 1
			if i >= n:
				break
		totalremovals = n - maxLen
		return totalremovals


import bisect as bs

class Solution:

	def removals(self, arr, n, k):
		arr.sort()
		res = n
		for (i, val) in enumerate(arr):
			ind = bs.bisect_right(arr, val + k)
			res = min(res, i + n - ind)
		return res


class Solution:

	def removals(self, arr, n, k):
		new = [[0, 0] for i in range(n)]
		for i in range(n):
			cur = arr[i]
			for j in range(n):
				if i == j:
					continue
				if arr[j] >= cur:
					new[i][1] += 1
				else:
					new[i][0] += 1
		mindiff = float('inf')
		for i in range(n):
			for j in range(n):
				if 0 <= arr[i] - arr[j] <= k:
					curdiff = new[i][1] + new[j][0]
					mindiff = min(mindiff, curdiff)
		return mindiff