Given an array arr[] of N elements containing first N positive integers. You have to sort the integers in ascending order by the following operation. Operation is to pick an integer and place it at end or at start. Every such operation increases cost by one. The task is to sort the array in the minimum cost
Example 1:
Input: N = 3
arr = {2, 1, 3}
Output: 1
Explaination: Place 1 at start.
Example 2:
Input: N = 4
arr = {4, 3, 1, 2}
Output: 2
Explaination: First place 3 at end then 
4 at end.
Your Task:
You do not need to read input or print anything. Your task is to complete the function sortingCost() which takes the value N and arr as input parameters and returns the minimum cost of sorting.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def sortingCost(self, N, arr):

        # code here

Solutions:
from collections import defaultdict

class Solution:

	def sortingCost(self, N, arr):
		store = defaultdict(lambda : 0)
		for item in arr:
			store[item] = store[item - 1] + 1
		return N - max(store.values())


class Solution:

	def sortingCost(self, N, arr):
		d = {}
		maxs = 1
		for i in arr:
			if i - 1 in d.keys():
				l = d[i - 1]
				d[i] = l + 1
				maxs = max(maxs, l + 1)
			else:
				d[i] = 1
		return N - maxs


class Solution:

	def sortingCost(self, N, arr):
		mapp = {}
		maxi = 1
		for i in range(N):
			if arr[i] - 1 in mapp:
				val = mapp[arr[i] - 1]
				mapp[arr[i]] = val + 1
				maxi = max(maxi, val + 1)
			else:
				mapp[arr[i]] = 1
		return N - maxi


class Solution:

	def sortingCost(self, N, arr):
		temp = {}
		for x in arr:
			if x - 1 in temp:
				temp[x] = temp[x - 1] + 1
			else:
				temp[x] = 1
		return N - max(temp.values())


class Solution:

	def sortingCost(self, N, arr):
		maxi = 1
		d = {}
		for i in arr:
			if i - 1 in d:
				length = d[i - 1]
				d[i] = 1 + length
				maxi = max(maxi, d[i])
			else:
				d[i] = 1
		return N - maxi


class Solution:

	def sortingCost(self, N, arr):
		hmap = {}
		cnt = 0
		for i in arr:
			if i - 1 not in hmap:
				hmap[i] = 1
			else:
				hmap[i] = hmap[i - 1] + 1
			cnt = max(cnt, hmap[i])
		return N - cnt


from collections import defaultdict

class Solution:

	def sortingCost(self, N, arr):
		d = defaultdict(int)
		mx = 0
		for val in arr:
			if d[val - 1]:
				d[val] = d[val - 1] + 1
			else:
				d[val] = 1
			mx = max(mx, d[val])
		return N - mx
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for it in range(N):
			arr[it] = int(arr[it])
		ob = Solution()
		print(ob.sortingCost(N, arr))


from collections import defaultdict

class Solution:

	def sortingCost(self, N, arr):
		d = defaultdict(int)
		mx = 0
		for val in arr:
			if d[val - 1]:
				d[val] = d[val - 1] + 1
			else:
				d[val] = 1
			mx = max(mx, d[val])
		return N - mx


class Solution:

	def sortingCost(self, N, arr):
		d = {}
		ans = 1
		for i in arr:
			if i - 1 in d:
				d[i] = 1 + d[i - 1]
			else:
				d[i] = 1
			ans = max(ans, d[i])
		return N - ans


class Solution:

	def sortingCost(self, N, arr):
		hm = {}
		m = 0
		for i in arr:
			if hm.get(i - 1):
				hm[i] = hm[i - 1] + 1
			else:
				hm[i] = 1
			m = max(m, hm[i])
		return len(arr) - m


class Solution:

	def sortingCost(self, N, arr):
		mp = {}
		max1 = -1
		for x in arr:
			if x - 1 in mp:
				mp[x] = mp[x - 1] + 1
				max1 = max(max1, mp[x])
			else:
				mp[x] = 1
		return N - max1


class Solution:

	def sortingCost(self, N, arr):
		map = {}
		for val in arr:
			if val - 1 in map:
				map[val] = map[val - 1] + 1
			else:
				map[val] = 1
		return N - max(map.values())


class Solution:

	def sortingCost(self, N, arr):
		hashM = {}
		length = 0
		for el in arr:
			if el - 1 in hashM:
				hashM[el] = hashM.get(el - 1, 0) + 1
			else:
				hashM[el] = 1
			length = max(length, hashM[el])
		return N - length


class Solution:

	def sortingCost(self, N, arr):
		mp = {}
		for x in arr:
			if x - 1 in mp:
				mp[x] = mp[x - 1] + 1
			else:
				mp[x] = 1
		max1 = float('-inf')
		for (key, val) in mp.items():
			max1 = max(max1, val)
		return N - max1


class Solution:

	def sortingCost(self, N, arr):
		dict1 = {}
		for i in arr:
			if i - 1 in dict1:
				dict1[i] = dict1[i - 1] + 1
			else:
				dict1[i] = 1
		lonsubs = 0
		for (k, v) in dict1.items():
			if v > lonsubs:
				lonsubs = v
		return N - lonsubs


class Solution:

	def sortingCost(self, N, arr):
		hmap = {}
		maxl = 1
		for ele in arr:
			if ele - 1 not in hmap:
				hmap[ele] = 1
			else:
				hmap[ele] = hmap[ele - 1] + 1
			maxl = max(maxl, hmap[ele])
		return N - maxl


class Solution:

	def sortingCost(self, N, arr):
		map = {}
		for i in range(N):
			map[arr[i]] = map.get(arr[i] - 1, 0) + 1
		return N - max(map.values())


class Solution:

	def sortingCost(self, N, arr):
		d = {}
		for a in arr:
			d[a] = d.get(a - 1, 0) + 1
		return N - max(d.values())


class Solution:

	def sortingCost(self, N, arr):
		hashmap = {}
		for i in arr:
			hashmap[i] = hashmap.get(i - 1, 0) + 1
		m = max(hashmap.values())
		return N - m


class Solution:

	def sortingCost(self, N, arr):
		mapp = {}
		for i in arr:
			if i - 1 in mapp:
				mapp[i] = mapp[i - 1] + 1
			else:
				mapp[i] = 1
		return N - max(mapp.values())


class Solution:

	def sortingCost(self, N, arr):
		d = dict()
		for i in arr:
			if i - 1 in d:
				d[i] = d[i - 1] + 1
			else:
				d[i] = 1
		m = 0
		for (k, v) in d.items():
			if v > m:
				m = v
		return N - m


class Solution:

	def sortingCost(self, N, arr):
		longsub = {}
		res = 1
		for num in arr:
			if num - 1 in longsub:
				longsub[num] = longsub[num - 1] + 1
				res = max(res, longsub[num])
			else:
				longsub[num] = 1
		return N - res


class Solution:

	def sortingCost(self, N, arr):
		mp = dict()
		max1 = 1
		for n in arr:
			if n - 1 in mp:
				mp[n] = mp[n - 1] + 1
			else:
				mp[n] = 1
		for (key, val) in mp.items():
			if val > max1:
				max1 = val
		return N - max1


from collections import defaultdict

class Solution:

	def sortingCost(self, N, arr):
		dic = defaultdict(int)
		n = len(arr)
		maxi = 1
		for num in arr:
			if num - 1 in dic:
				dic[num] = dic[num - 1]
			dic[num] += 1
			maxi = max(maxi, dic[num])
		return n - maxi


class Solution:

	def sortingCost(self, N, arr):
		d = dict()
		for elem in arr:
			if elem - 1 in d:
				d[elem] = d[elem - 1] + 1
			else:
				d[elem] = 1
		M = 0
		for (k, v) in d.items():
			if v > M:
				M = v
		return N - M


class Solution:

	def sortingCost(self, N, arr):
		d = {}
		for e in arr:
			if e not in d and e - 1 not in d:
				d[e] = 1
			elif e not in d and e - 1 in d:
				d[e] = d[e - 1] + 1
		x = max(d.values())
		return N - x