Given an array arr of n positive integers and a number k. One can apply a swap operation on the array any number of times, i.e choose any two index i and j (i < j) and swap arr[i] , arr[j] . Find the minimum number of swaps required to bring all the numbers less than or equal to k together, i.e. make them a contiguous subarray.
Example 1:
Input : 
arr[ ] = {2, 1, 5, 6, 3} 
K = 3
Output : 
1
Explanation:
To bring elements 2, 1, 3 together,
swap index 2 with 4 (0-based indexing),
i.e. element arr[2] = 5 with arr[4] = 3
such that final array will be- 
arr[] = {2, 1, 3, 6, 5}
Example 2:
Input : 
arr[ ] = {2, 7, 9, 5, 8, 7, 4} 
K = 6 
Output :  
2 
Explanation: 
To bring elements 2, 5, 4 together, 
swap index 0 with 2 (0-based indexing)
and index 4 with 6 (0-based indexing)
such that final array will be- 
arr[] = {9, 7, 2, 5, 4, 7, 8}
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function minSwap() that takes an array (arr), sizeOfArray (n), an integer K, and return the minimum swaps required. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Arr_{i}, K ≤10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

        

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

        #Complete the function

    





Solutions:
import sys

class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for i in range(n):
			if arr[i] <= k:
				cnt += 1
		if cnt == 0 or cnt == 1 or cnt == n:
			return 0
		ans = sys.maxsize - 1
		badEle = 0
		for i in range(cnt):
			if arr[i] > k:
				badEle += 1
		ans = min(ans, badEle)
		i = 0
		j = cnt
		while j < n:
			if arr[i] > k:
				badEle -= 1
			if arr[j] > k:
				badEle += 1
			ans = min(ans, badEle)
			i += 1
			j += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		count1 = 0
		for i in arr:
			if i <= k:
				count1 += 1
		count2 = 0
		for i in range(count1):
			if arr[i] <= k:
				count2 += 1
		ans = count2
		i = 0
		j = count1
		while j < n:
			if arr[i] <= k:
				count2 -= 1
			if arr[j] <= k:
				count2 += 1
			i += 1
			j += 1
			ans = max(ans, count2)
		return count1 - ans


class Solution:

	def minSwap(self, arr, n, k):
		if n == 0:
			return 0
		elif n == 1:
			return arr[0]
		window_size = 0
		for elem in arr:
			if elem <= k:
				window_size += 1
		bad = 0
		for i in range(0, window_size):
			if arr[i] > k:
				bad += 1
		swaps = bad
		i = 0
		j = window_size
		while j < len(arr):
			if arr[i] > k:
				bad -= 1
			if arr[j] > k:
				bad += 1
			swaps = min(swaps, bad)
			i += 1
			j += 1
		return swaps


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
		bad = 0
		for i in range(0, count):
			if arr[i] > k:
				bad += 1
		ans = bad
		j = count
		for i in range(n):
			if j == n:
				break
			if arr[i] > k:
				bad -= 1
			if arr[j] > k:
				bad += 1
			ans = min(ans, bad)
			j += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for i in arr:
			if i <= k:
				count += 1
		ans = 0
		for i in range(count):
			if arr[i] > k:
				ans += 1
		i = count
		mini = ans
		while i < n:
			if arr[i] > k:
				ans += 1
			if arr[i - count] > k:
				ans -= 1
			mini = min(ans, mini)
			i += 1
		return mini


class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for i in arr:
			if i <= k:
				cnt += 1
		res = 0
		for i in range(cnt):
			if arr[i] > k:
				res += 1
		cur = res
		for i in range(cnt, n):
			if arr[i - cnt] <= k and arr[i] > k:
				cur += 1
			elif arr[i - cnt] > k and arr[i] <= k:
				cur -= 1
			res = min(res, cur)
		return res


class Solution:

	def minSwap(self, arr, n, k):
		window = 0
		for number in arr:
			if number <= k:
				window += 1
		grtEle = 0
		for index in range(window):
			if arr[index] > k:
				grtEle += 1
		ans = grtEle
		start = 0
		for end in range(window, len(arr)):
			if arr[start] > k:
				grtEle -= 1
			start += 1
			if arr[end] > k:
				grtEle += 1
			ans = min(ans, grtEle)
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		greater = []
		lte = []
		for i in range(n):
			if arr[i] > k:
				greater.append(i)
			else:
				lte.append(i)
		wsize = len(lte)
		gsize = len(greater)
		if wsize < 2 or len(greater) == 0 or (len(greater) == 1 and (greater[0] == 0 or greater[0] == n - 1)):
			return 0
		bad = 0
		for i in range(wsize):
			if arr[i] > k:
				bad += 1
		mlen = bad
		for i in range(1, n - wsize + 1):
			if arr[i - 1] > k:
				bad -= 1
			if arr[i + wsize - 1] > k:
				bad += 1
			mlen = min(mlen, bad)
		return mlen


class Solution:

	def minSwap(self, arr, n, k):
		fav = 0
		for i in arr:
			if i <= k:
				fav += 1
		nonfav = 0
		for j in range(fav):
			if arr[j] > k:
				nonfav += 1
		(lw, rw) = (0, fav - 1)
		result = float('inf')
		while rw < n:
			result = min(result, nonfav)
			rw += 1
			if rw < n and arr[rw] > k:
				nonfav += 1
			if lw < n and arr[lw] > k:
				nonfav -= 1
			lw += 1
		return result if result != float('inf') else 0


class Solution:

	def minSwap(self, a, n, k):
		c = 0
		for i in range(n):
			if a[i] <= k:
				c += 1
		maxc = 0
		d = 0
		for i in range(c):
			if a[i] <= k:
				d += 1
		maxc = max(maxc, d)
		for i in range(c, n):
			if a[i] <= k:
				d += 1
			if a[i - c] <= k:
				d -= 1
			maxc = max(maxc, d)
		return c - maxc


class Solution:

	def minSwap(self, a, n, k):
		c = 0
		for i in range(n):
			if a[i] <= k:
				c += 1
		maxi = -10 ** 9
		f = 0
		for i in range(c):
			if a[i] <= k:
				f += 1
		maxi = max(maxi, f)
		start = 0
		for i in range(c, n):
			if a[start] <= k:
				f -= 1
			start += 1
			if a[i] <= k:
				f += 1
			maxi = max(maxi, f)
		return c - maxi


class Solution:

	def minSwap(self, arr, n, k):
		windowSize = 0
		for i in arr:
			if i <= k:
				windowSize += 1
		(i, cnt) = (0, 0)
		while i < windowSize:
			if arr[i] > k:
				cnt += 1
			i += 1
		minCnt = cnt
		while i < n:
			if arr[i] > k:
				cnt += 1
			if arr[i - windowSize] > k:
				cnt -= 1
			minCnt = min(minCnt, cnt)
			i += 1
		return minCnt


class Solution:

	def minSwap(self, arr, n, k):
		window_size = 0
		for i in range(n):
			if arr[i] <= k:
				window_size += 1
		bad_number = 0
		for i in range(window_size):
			if arr[i] > k:
				bad_number += 1
		i = 0
		j = window_size
		ans = bad_number
		while j < n:
			if arr[j] > k:
				bad_number += 1
			if arr[i] > k:
				bad_number -= 1
			i += 1
			j += 1
			ans = min(bad_number, ans)
		if window_size == 0:
			return 0
		return ans


import sys

class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for i in arr:
			if i <= k:
				count += 1
		bad = 0
		for i in range(count):
			if arr[i] > k:
				bad += 1
		min_bad = bad
		for i in range(len(arr) - count):
			if arr[i] <= k and arr[i + count] > k:
				bad += 1
			elif arr[i] > k and arr[i + count] <= k:
				bad -= 1
			min_bad = min(min_bad, bad)
		return min_bad


class Solution:

	def minSwap(self, arr, n, k):
		x = 0
		for i in range(n):
			if arr[i] <= k:
				x += 1
		c = 0
		for i in range(x):
			if arr[i] > k:
				c += 1
		(i, j) = (0, x)
		mini = c
		while j < n:
			if arr[i] > k:
				c -= 1
			if arr[j] > k:
				c += 1
			mini = min(mini, c)
			j += 1
			i += 1
		return mini


class Solution:

	def minSwap(self, arr, n, k):
		maxm = 0
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
		countLegalElement = 0
		for i in range(count):
			if arr[i] <= k:
				countLegalElement += 1
		for j in range(count, n):
			maxm = max(maxm, countLegalElement)
			if arr[j] <= k:
				countLegalElement += 1
			if arr[j - count] <= k:
				countLegalElement -= 1
		maxm = max(maxm, countLegalElement)
		minmSwap = count - maxm
		return minmSwap


class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for i in range(n):
			if arr[i] <= k:
				cnt += 1
		cnt1 = 0
		for i in range(cnt):
			if arr[i] <= k:
				cnt1 += 1
		j = 0
		mn = cnt - cnt1
		for i in range(cnt, n):
			if arr[j] <= k:
				cnt1 -= 1
			if arr[i] <= k:
				cnt1 += 1
			mn = min(mn, cnt - cnt1)
			j = j + 1
		return mn


class Solution:

	def minSwap(self, arr, n, k):
		c = 0
		for i in range(n):
			if arr[i] <= k:
				c += 1
		i = 0
		s = 0
		for i in range(c):
			if arr[i] > k:
				s += 1
		ms = s
		i = c
		j = 0
		while i < n:
			ns = s
			if arr[j] > k:
				ns -= 1
			if arr[i] > k:
				ns += 1
			s = ns
			ms = min(ms, ns)
			i += 1
			j += 1
		return ms


class Solution:

	def minSwap(self, arr, n, k):
		result = float('inf')
		count = 0
		K = 0
		for i in arr:
			if i <= k:
				K += 1
		(i, j) = (0, 0)
		while j < n:
			if arr[j] <= k:
				count += 1
			if j - i + 1 == K:
				result = min(result, K - count)
				if arr[i] <= k:
					count -= 1
				i += 1
			j += 1
		if result == float('inf'):
			return 0
		return result


class Solution:

	def minSwap(self, arr, n, k):
		c1 = 0
		for i in arr:
			if i <= k:
				c1 += 1
		c2 = 0
		for i in range(c1):
			if arr[i] <= k:
				c2 += 1
		a = c2
		i = 0
		j = c1
		while j < n:
			if arr[i] <= k:
				c2 -= 1
			if arr[j] <= k:
				c2 += 1
			i += 1
			j += 1
			a = max(a, c2)
		return c1 - a


import sys

class Solution:

	def minSwap(self, arr, n, k):
		cnt_lessk = 0
		for i in range(len(arr)):
			if arr[i] <= k:
				cnt_lessk += 1
		low = 0
		high = cnt_lessk - 1
		bad = 0
		while low <= high:
			if arr[low] > k:
				bad += 1
			low += 1
		min_bad = bad
		for i in range(len(arr) - cnt_lessk):
			if arr[i] > k and arr[i + cnt_lessk] <= k:
				bad -= 1
			if arr[i] <= k and arr[i + cnt_lessk] > k:
				bad += 1
			min_bad = min(min_bad, bad)
		return min_bad


class Solution:

	def minSwap(self, arr, n, k):
		window = 0
		nf = 0
		for i in range(n):
			if arr[i] <= k:
				window += 1
		for i in range(0, window):
			if arr[i] > k:
				nf += 1
		l = 0
		r = window - 1
		res = 9999999
		while r < n:
			res = min(res, nf)
			r += 1
			if r < n and arr[r] > k:
				nf += 1
			if r < n and arr[l] > k:
				nf -= 1
			l += 1
		return 0 if res == 9999999 else res


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
		if count == 0:
			return 0
		(i, j) = (0, 0)
		bad = 0
		ans = float('inf')
		while j < n:
			if arr[j] > k:
				bad += 1
			if j - i + 1 < count:
				j += 1
			elif j - i + 1 == count:
				ans = min(ans, bad)
				if arr[i] > k:
					bad -= 1
				i += 1
				j += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		count = sum((1 for i in arr if i <= k))
		if count == 0:
			return 0
		(i, j) = (0, 0)
		ans = 1000000000.0
		bad = 0
		while j < n:
			if arr[j] > k:
				bad += 1
			if j - i + 1 < count:
				j += 1
			elif j - i + 1 == count:
				ans = min(ans, bad)
				if arr[i] > k:
					bad -= 1
				i += 1
				j += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		fav = 0
		nonfav = 0
		for i in range(n):
			if arr[i] <= k:
				fav += 1
		for i in range(fav):
			if arr[i] <= k:
				nonfav += 1
		ans = nonfav
		i = 0
		j = fav
		while j < n:
			if arr[i] <= k:
				nonfav -= 1
			if arr[j] <= k:
				nonfav += 1
			i += 1
			j += 1
			ans = max(ans, nonfav)
		return fav - ans


class Solution:

	def minSwap(self, arr, n, k):
		n = len(arr)
		count = 0
		for num in arr:
			if num <= k:
				count += 1
		res = count
		curr = 0
		for i in range(n):
			num = arr[i]
			if num > k:
				curr += 1
			if i >= count:
				rem = arr[i - count]
				if rem > k:
					curr -= 1
			if i >= count - 1:
				res = min(res, curr)
		return res


import sys

class Solution:

	def minSwap(self, arr, n, k):
		snowBallSize = 0
		i = 0
		while i < n:
			if arr[i] <= k:
				snowBallSize += 1
			i += 1
		swap = 0
		ans_swaps = sys.maxsize
		i = 0
		while i < snowBallSize:
			if arr[i] > k:
				swap += 1
			i += 1
		ans_swaps = min(ans_swaps, swap)
		i = snowBallSize
		while i < n:
			if arr[i - snowBallSize] <= k and arr[i] > k:
				swap += 1
			elif arr[i - snowBallSize] > k and arr[i] <= k:
				swap -= 1
			ans_swaps = min(ans_swaps, swap)
			i += 1
		return ans_swaps


class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for v in arr:
			if v <= k:
				cnt += 1
		tmpCnt = 0
		for i in range(cnt):
			if arr[i] > k:
				tmpCnt += 1
		ans = tmpCnt
		for i in range(cnt, n):
			if arr[i - cnt] > k:
				tmpCnt -= 1
			if arr[i] > k:
				tmpCnt += 1
			ans = min(ans, tmpCnt)
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		c = 0
		for i in arr:
			if i <= k:
				c += 1
		b = 0
		for i in range(c):
			if arr[i] > k:
				b += 1
		m = b
		for i in range(c, n):
			if arr[i] > k:
				b += 1
			if arr[i - c] > k:
				b -= 1
			m = min(m, b)
		return m


import sys

class Solution:

	def minSwap(self, arr, n, k):
		WS = 0
		nf = 0
		for i in range(n):
			if arr[i] <= k:
				WS += 1
		for j in range(WS):
			if arr[j] > k:
				nf += 1
		s = 0
		r = WS - 1
		ans = sys.maxsize - 1
		while r < n:
			ans = min(ans, nf)
			r += 1
			if r < n and arr[r] > k:
				nf += 1
			if s < n and arr[s] > k:
				nf -= 1
			s += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for i in arr:
			if i <= k:
				count += 1
		ans = count
		temp = 0
		(i, j) = (0, 0)
		while j < n:
			if arr[j] <= k:
				temp += 1
			if j - i + 1 == count:
				ans = min([ans, count - temp])
				if arr[i] <= k:
					temp -= 1
				i += 1
			j += 1
		return ans


class Solution:

	def minSwap(self, a, n, k):
		cnt = 0
		for i in range(n):
			if a[i] <= k:
				cnt += 1
		ans = 99999
		x = 0
		y = 0
		i = 0
		j = 0
		while i < n:
			if a[i] <= k:
				x += 1
			y += 1
			if y == cnt:
				ans = min(ans, y - x)
			elif y > cnt:
				if a[j] <= k:
					x -= 1
				j += 1
				y -= 1
				ans = min(ans, y - x)
			i += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		snowBallSize = 0
		i = 0
		while i < n:
			if arr[i] <= k:
				snowBallSize += 1
			i += 1
		swap = 0
		ans_swaps = 999999999999999999999999
		i = 0
		while i < snowBallSize:
			if arr[i] > k:
				swap += 1
			i += 1
		ans_swaps = min(ans_swaps, swap)
		i = snowBallSize
		while i < n:
			if arr[i - snowBallSize] <= k and arr[i] > k:
				swap += 1
			elif arr[i - snowBallSize] > k and arr[i] <= k:
				swap -= 1
			ans_swaps = min(ans_swaps, swap)
			i += 1
		return ans_swaps


class Solution:

	def minSwap(self, arr, n, k):
		ws = 0
		for i in arr:
			if i <= k:
				ws += 1
		if ws == 0:
			return 0
		else:
			nf = 0
			for i in range(ws):
				if arr[i] <= k:
					nf += 1
			l = 0
			r = ws
			mi = nf
			while r < n:
				if arr[l] <= k:
					nf -= 1
				if arr[r] <= k:
					nf += 1
				l += 1
				r += 1
				mi = max(mi, nf)
		return ws - mi


class Solution:

	def minSwap(self, arr, n, k):
		good = 0
		bad = 0
		for i in range(n):
			if arr[i] <= k:
				good += 1
		total_bad = 0
		for i in range(good):
			if arr[i] > k:
				total_bad += 1
		i = 1
		j = good
		bad = total_bad
		while j < n:
			if arr[i - 1] > k:
				bad = bad - 1
			if arr[j] > k:
				bad += 1
			i += 1
			j += 1
			total_bad = min(total_bad, bad)
		return total_bad


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for num in arr:
			if num <= k:
				count += 1
		window_size = count
		window_count = 0
		for i in range(window_size):
			if arr[i] > k:
				window_count += 1
		min_swaps = window_count
		for i in range(1, len(arr) - window_size + 1):
			if arr[i - 1] > k:
				window_count -= 1
			if arr[i + window_size - 1] > k:
				window_count += 1
			min_swaps = min(min_swaps, window_count)
		return min_swaps


import sys

class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
		bad = 0
		for i in range(count):
			if arr[i] > k:
				bad += 1
		mn = bad
		j = count
		for i in range(n):
			if j == n:
				break
			if arr[i] > k:
				bad -= 1
			if arr[j] > k:
				bad += 1
			mn = min(mn, bad)
			j += 1
		return mn


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		for item in arr:
			if item <= k:
				count += 1
		(start, end) = (0, 0)
		res = float('inf')
		bad = 0
		while end <= len(arr) - 1:
			val = arr[end]
			if val > k:
				bad += 1
			while end - start + 1 > count:
				val = arr[start]
				if val > k:
					bad -= 1
				start += 1
			if end - start + 1 == count:
				res = min(res, bad)
			end += 1
		return res


class Solution:

	def minSwap(self, arr, n, k):
		mx = 0
		for i in range(n):
			if arr[i] <= k:
				mx += 1
		nf = 0
		for i in range(mx):
			if arr[i] > k:
				nf += 1
		ans = n - mx
		s = 0
		e = mx - 1
		while e < n:
			ans = min(ans, nf)
			if s < n and arr[s] <= k:
				s += 1
				e += 1
			else:
				s += 1
				nf -= 1
				e += 1
			if e < n and arr[e] > k:
				nf += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for x in arr:
			if x <= k:
				cnt += 1
		gap_cnt = 0
		for i in range(cnt):
			if arr[i] > k:
				gap_cnt += 1
		min_swaps = gap_cnt
		for i in range(cnt, n):
			if arr[i - cnt] > k:
				gap_cnt -= 1
			if arr[i] > k:
				gap_cnt += 1
			min_swaps = min(min_swaps, gap_cnt)
		return min_swaps


class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for el in arr:
			if el <= k:
				cnt += 1
		ans = 9999999
		lg = 0
		j = 0
		for i in range(n):
			if arr[i] > k:
				lg += 1
			if i + 1 >= cnt:
				ans = min(ans, lg)
				if arr[j] > k:
					lg -= 1
				j += 1
		if cnt == 0:
			return 0
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		import sys
		fav = 0
		nonfav = 0
		for i in range(n):
			if arr[i] <= k:
				fav += 1
		for j in range(fav):
			if arr[j] > k:
				nonfav += 1
		result = nonfav
		p = fav
		for m in range(0, n):
			if p == n:
				break
			if arr[m] > k:
				nonfav -= 1
			if arr[p] > k:
				nonfav += 1
			result = min(result, nonfav)
			p = p + 1
		return result


class Solution:

	def minSwap(self, arr, n, k):
		res = float('inf')
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
		bad = 0
		for i in range(count):
			if arr[i] > k:
				bad += 1
		res = bad
		j = count
		for i in range(n):
			if j == n:
				break
			if arr[i] > k:
				bad -= 1
			if arr[j] > k:
				bad += 1
			res = min(res, bad)
			j += 1
		return 0 if res == float('inf') else res


class Solution:

	def minSwap(self, arr, n, k):
		win_size = 0
		(ans, ctr) = (0, 0)
		for i in range(0, n):
			if arr[i] <= k:
				win_size += 1
		if win_size == 0:
			return 0
		for i in range(0, win_size):
			if arr[i] > k:
				ctr += 1
		ans = ctr
		(i, j) = (1, win_size)
		while j < n:
			if arr[j] > k:
				ctr += 1
			if arr[i - 1] > k:
				ctr -= 1
			ans = min(ans, ctr)
			(i, j) = (i + 1, j + 1)
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		cnt = 0
		for i in range(0, n):
			if arr[i] <= k:
				cnt = cnt + 1
		unwanted = 0
		for i in range(0, cnt):
			if arr[i] > k:
				unwanted = unwanted + 1
		res = unwanted
		j = cnt
		for i in range(n):
			if j == n:
				break
			if arr[i] > k:
				unwanted -= 1
			if arr[j] > k:
				unwanted += 1
			res = min(res, unwanted)
			j += 1
		return res


from functools import reduce

class Solution:

	def minSwap(self, arr, n, k):
		count = reduce(lambda a, b: a + 1, filter(lambda x: x <= k, arr), 0)
		greater = reduce(lambda a, b: a + 1, filter(lambda x: x > k, arr[:count]), 0)
		small = greater
		for i in range(count, n):
			if arr[i] > k:
				greater += 1
			if arr[i - count] > k:
				greater -= 1
			small = min(small, greater)
		return small


class Solution:

	def minSwap(self, arr, n, k):
		no_ele = 0
		for i in range(n):
			if arr[i] <= k:
				no_ele += 1
		ans_arr = arr[:no_ele]
		ans = 0
		for item in ans_arr:
			if item <= k:
				ans += 1
		j = len(ans_arr)
		fans = ans
		while j < n and no_ele != 0:
			new_ele = 0
			x = ans_arr.pop(0)
			y = arr[j]
			ans_arr += [arr[j]]
			j += 1
			if x <= k:
				ans -= 1
			if y <= k:
				ans += 1
			fans = max(fans, ans)
		final_ans = no_ele - fans
		return final_ans


class Solution:

	def minSwap(self, arr, n, k):
		c = 0
		for i in range(n):
			if arr[i] <= k:
				c += 1
		count = 0
		for i in range(c):
			if arr[i] <= k:
				count += 1
		minS = c - count
		(l, r) = (1, c)
		while r < n:
			if arr[l - 1] <= k:
				count -= 1
			if arr[r] <= k:
				count += 1
			if minS > c - count:
				minS = c - count
			l += 1
			r += 1
		return minS


class Solution:

	def minSwap(self, arr, n, k):
		count = 0
		max_len = 0
		curr_len = 0
		for i in arr:
			if i <= k:
				count += 1
		bad_number = 0
		min_window = 0
		for i in range(count):
			if arr[i] > k:
				bad_number += 1
		min_window = bad_number
		i = 0
		while count < n:
			if arr[i] > k:
				bad_number -= 1
			if arr[count] > k:
				bad_number += 1
			min_window = min(min_window, bad_number)
			i += 1
			count += 1
		return min_window


class Solution:

	def minSwap(self, arr, n, k):
		minSwaps = 0
		ct = 0
		for i in arr:
			if i <= k:
				ct += 1
		additional = 0
		for i in arr[:ct]:
			if i > k:
				additional += 1
		minSwaps = additional
		i = 0
		j = ct
		while j < n:
			if arr[i] > k:
				additional -= 1
			if arr[j] > k:
				additional += 1
			minSwaps = min(minSwaps, additional)
			i += 1
			j += 1
		return minSwaps


class Solution:

	def minSwap(self, arr, n, k):
		fav = non = 0
		for i in arr:
			if i <= k:
				fav += 1
		for j in range(fav):
			if arr[j] > k:
				non += 1
		l = 0
		r = fav - 1
		ans = 1000000000
		while r < n:
			ans = min(ans, non)
			r += 1
			if r < n and arr[r] > k:
				non += 1
			if l < n and arr[l] > k:
				non -= 1
			l += 1
		return ans


class Solution:

	def minSwap(self, arr, n, k):
		windowsize = 0
		badchar = 0
		for x in arr:
			if x <= k:
				windowsize += 1
		for i in range(0, windowsize):
			if arr[i] > k:
				badchar += 1
		res = badchar
		(i, j) = (0, windowsize)
		while j < n:
			if arr[i] > k:
				badchar -= 1
			if arr[j] > k:
				badchar += 1
			res = min(res, badchar)
			i = i + 1
			j = j + 1
		return res


class Solution:

	def minSwap(self, arr, n, k):
		c = 0
		bad = 0
		for i in range(len(arr)):
			if arr[i] <= k:
				c += 1
		if c == 0:
			return 0
		ans = 100000000000000
		i = 0
		j = 0
		while j < n:
			if j - i + 1 < c:
				if arr[j] > k:
					bad += 1
			elif j - i + 1 == c:
				if arr[j] > k:
					bad += 1
				ans = min(ans, bad)
				if arr[i] > k:
					bad -= 1
				i += 1
			j += 1
		return ans