Given an array of N integers, you have to find if it is possible to partition the array with following rules:
	Each element should belong to exactly one partition.
	Each partition should have atleast K elements.
	Absolute difference between any pair of elements in the same partition should not exceed M.
Example 1:
Input:
N = 5
K = 2
M = 3
A[] = {8, 3, 9, 1, 2}
Output:
YES
Explanation:
We can partition the array into two 
partitions: {8, 9} and {3, 1, 2} such that
all rules are satisfied.
Your Task:
You don't need to read input or print anything. Your task is to complete the function partitionArray() which takes the number of elements N, integer K, integer M and array A[ ] as input parameters and returns true if we can partition the array such that all rules are satisfied, else returns false.
Expected Time Complexity: O(N * Log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 2*10^{5}
1 ≤ K ≤ N
1 ≤ M ≤ 10^{9}
1 ≤ A[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3



class Solution:

    def partitionArray(self,N,K,M,arr):

        #code here

Solutions:
class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [False] * N
		for (i, e) in enumerate(arr[K - 1:], start=K - 1):
			n = i + 1 - k + 1
			(lo, hi) = (0, n)
			while lo < hi:
				mi = lo + (hi - lo) // 2
				if arr[i] - arr[mi] <= M:
					hi = mi
				else:
					lo = mi + 1
			for j in range(lo, n):
				if j == 0 or dp[j - 1]:
					dp[i] = True
					break
		return dp[-1]


from bisect import bisect_left

class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [0] * (N + 1)
		dp[0] = 1
		for i in range(K, N + 1):
			ind = bisect_left(arr, arr[i - 1] - M, 0, i - 1)
			h = i - K
			for j in range(ind, h + 1):
				dp[i] = dp[i] or dp[j]
				if dp[i]:
					break
		return dp[N]


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		ls = [0]
		for i in range(K - 1, N):
			while i - ls[0] + 1 >= K:
				if arr[i] - arr[ls[0]] <= M:
					ls.append(i + 1)
					break
				ls.pop(0)
				if not ls:
					return False
		return ls[-1] == N


from collections import deque

class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		q = deque([0])
		for i in range(K - 1, N):
			while i - q[0] + 1 >= K:
				if arr[i] - arr[q[0]] <= M:
					q.append(i + 1)
					break
				q.popleft()
				if not q:
					return False
		return q[-1] == N


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [-1 for i in range(N)]

		def fun(arr, i):
			if i >= len(arr):
				return True
			elif dp[i] != -1:
				return dp[i]
			else:
				dp[i] = False
				for l in range(i + K - 1, len(arr)):
					if arr[l] - arr[i] <= M:
						dp[i] = dp[i] or fun(arr, l + 1)
				return dp[i]
		return fun(arr, 0)


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		memo = {}

		def recur(strt, end):
			nonlocal N, K, M, arr, memo
			if strt >= N:
				return True
			if end - strt + 1 < K:
				return False
			if (strt, end) in memo:
				return memo[strt, end]
			j = strt + K - 1
			while j < N and arr[j] - arr[strt] <= M:
				res = recur(j + 1, end)
				if res:
					memo[strt, end] = True
					return res
				j += 1
			memo[strt, end] = False
			return False
		return recur(0, N - 1)


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [False] * N
		for (i, e) in enumerate(arr[K - 1:], start=K - 1):
			n = i + 1 - k + 1
			(lo, hi) = (0, n)
			while lo < hi:
				mi = lo + (hi - lo) // 2
				if arr[i] - arr[mi] <= M:
					hi = mi
				else:
					lo = mi + 1
			for j in range(lo, n):
				if j == 0 or dp[j - 1]:
					dp[i] = True
					break
		return dp[-1]
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, k, m) = map(int, input().split())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		ans = obj.partitionArray(n, k, m, arr)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp_lst = [False] * N
		for (i, e) in enumerate(arr[K - 1:], start=K - 1):
			n = i + 1 - k + 1
			(low, high) = (0, n)
			while low < high:
				mid = low + (high - low) // 2
				if arr[i] - arr[mid] <= M:
					high = mid
				else:
					low = mid + 1
			for j in range(low, n):
				if j == 0 or dp_lst[j - 1]:
					dp_lst[i] = True
					break
		return dp_lst[-1]


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [0 for _ in range(N)]
		for (i, arri) in enumerate(arr[K - 1:], start=K - 1):
			n = i + 1 - k + 1
			low = 0
			high = n
			while low < high:
				mid = (low + high) // 2
				if arr[i] - arr[mid] <= M:
					high = mid
				else:
					low = mid + 1
			for j in range(low, n):
				if j == 0 or dp[j - 1] == 1:
					dp[i] = 1
					break
		return dp[-1]


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		cache = {}

		def dp(i):
			if i in cache:
				return cache[i]
			if N - i < K:
				return False
			if N - i == K:
				return arr[-1] - arr[i] <= M
			if N - i > K and arr[-1] - arr[i] <= M:
				return True
			cache[i] = False
			for k in range(i + K - 1, N):
				val = True
				if arr[k] - arr[i] <= M:
					val &= dp(k + 1)
					if val:
						cache[i] = True
						return cache[i]
				else:
					break
			return cache[i]
		return dp(0)


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()

		def dfs(start):
			if start == N:
				return True
			nexti = start + k - 1
			while nexti < N:
				if arr[nexti] - arr[start] > M:
					return False
				if dfs(nexti + 1):
					return True
				nexti += 1
			return False
		return dfs(0)


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [-1] * N
		can_do = self.solve(0, arr, K, M, dp)
		return can_do

	def solve(self, start, arr, K, M, dp):
		n = len(arr)
		if start >= n:
			return True
		if dp[start] != -1:
			return dp[start]
		for i in range(start + K - 1, n):
			diff = abs(arr[i] - arr[start])
			if diff > M:
				break
			next_solvable = self.solve(i + 1, arr, K, M, dp)
			if next_solvable:
				dp[start] = True
				return dp[start]
		dp[start] = False
		return dp[start]


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()
		dp = [-1] * (N + 1)

		def dfs(i):
			if i >= N:
				return 1
			if n - i < K:
				return 0
			for j in range(i + k - 1, N):
				if arr[j] - arr[i] > m:
					return 0
				if dfs(j + 1):
					return 1
			return 0
		return dfs(0)


from collections import deque

class Solution:

	def partitionArray(self, n, k, m, arr):
		arr.sort()
		queue = deque([0])
		for i in range(k - 1, n):
			while i - queue[0] + 1 >= k:
				if arr[i] - arr[queue[0]] <= m:
					queue.append(i + 1)
					break
				queue.popleft()
				if not queue:
					return False
		return queue[-1] == n


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()

		def rec(start, arr, k, m, n):
			if start >= n:
				return True
			for i in range(start + k - 1, n):
				if arr[i] - arr[start] > m:
					return False
				if rec(i + 1, arr, k, m, n):
					return True
			return False
		return rec(0, arr, K, M, N)


class Solution:

	def partitionArray(self, n, k, m, arr):
		arr = arr[:n]
		arr.sort()
		q = [0]
		for i in range(k - 1, n):
			while i - q[0] + 1 >= k:
				if arr[i] - arr[q[0]] <= m:
					q.append(i + 1)
					break
				q.pop(0)
				if not q:
					return 0
		return q[-1] == n


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()

		def helper(indx):
			n = len(arr)
			if indx >= n:
				return True
			if n - indx < k:
				return False
			for i in range(indx + k - 1, n):
				if arr[i] - arr[indx] > M:
					return False
				if helper(i + 1):
					return True
			return False
		return helper(0)


class Solution:

	def partitionArray(self, N, K, M, arr):
		arr.sort()

		def dfs(i):
			if i >= N:
				return True
			for j in range(i + K - 1, N):
				if abs(arr[j] - arr[i]) > M:
					break
				if dfs(j + 1):
					return True
			return False
		dp = [-1] * N
		return dfs(0)