Given an array of size N that has elements ranging from 0 to N-1. All elements may not be present in the array. If the element is not present then there will be -1 present in the array. Rearrange the array such that A[i] = i, and if i is not present, display -1 at that place.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {-1, -1, 6, 1, 9, 3, 2, 
                              -1, 4, -1}
Output : -1 1 2 3 4 -1 6 -1 -1 9
Explanation:
In range 0 to 9, all except 0, 5, 7 and 8 
are present. Hence, we print -1 instead of 
them.
Example 2:
Input : arr[ ] = {0, 1, 2, 3, 4, 5} 
Output : 0 1 2 3 4 5
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 modifyArray() that takes an array (arr), sizeOfArray (n), and return the modified array. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ A[i] ≤ N-1

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def modifyArray (self, arr,  n) : 
        #Complete the function



Solutions:
class Solution:

	def modifyArray(self, arr, n):
		l = set(arr)
		arr.clear()
		for i in range(0, n):
			if i in l:
				arr.append(i)
			else:
				arr.append(-1)
		return arr


class Solution:

	def modifyArray(self, arr, n):
		for i in range(n):
			while arr[i] != -1 and arr[i] != i:
				temp = arr[arr[i]]
				arr[arr[i]] = arr[i]
				arr[i] = temp
		return arr


class Solution:

	def modifyArray(self, arr, n):
		a = set(arr)
		res = []
		for i in range(n):
			if i in a:
				res.append(i)
			else:
				res.append(-1)
		return res


class Solution:

	def modifyArray(self, arr, n):
		i = 0
		while i < n:
			if arr[i] >= 0 and arr[i] != i:
				(arr[arr[i]], arr[i]) = (arr[i], arr[arr[i]])
			else:
				i += 1
		return arr


class Solution:

	def modifyArray(self, arr, n):
		s = set(arr)
		for i in range(n):
			if i in s:
				arr[i] = i
			else:
				arr[i] = -1
		return arr


class Solution:

	def modifyArray(self, arr, n):
		for i in range(n):
			if arr[i] >= 0 and arr[i] != i:
				x = arr[i]
				while arr[x] != -1 and arr[x] != x:
					y = arr[x]
					arr[x] = x
					x = y
				arr[x] = x
				if arr[i] != i:
					arr[i] = -1
		return arr


class Solution:

	def modifyArray(self, arr, n):
		l = [None] * n
		for i in range(n):
			if arr[i] != -1:
				l[arr[i]] = arr[i]
		for i in range(n):
			if l[i] == None:
				l[i] = -1
		return l


class Solution:

	def modifyArray(self, arr, n):
		d = {}
		for i in range(n):
			try:
				d[arr[i]] += 1
			except:
				d[arr[i]] = 1
		lst = []
		for i in range(n):
			if i in d:
				lst.append(i)
			else:
				lst.append(-1)
		return lst


class Solution:

	def modifyArray(self, arr, n):
		l = [-1] * n
		for i in arr:
			if i == -1:
				pass
			else:
				l[i] = 1
		l1 = []
		for i in range(n):
			if l[i] == -1:
				l1.append(-1)
			else:
				l1.append(i)
		return l1


class Solution:

	def modifyArray(self, arr, n):
		res = [-1] * n
		for i in arr:
			if i >= 0:
				res[i] = i
		return res


class Solution:

	def modifyArray(self, arr, n):
		lis = [0] * n
		arr = set(arr)
		for i in range(n):
			if i in arr:
				lis[i] = i
			else:
				lis[i] = -1
		return lis


class Solution:

	def modifyArray(self, arr, n):
		no = set()
		for i in arr:
			if i != -1 and i not in no:
				no.add(i)
		res = []
		for i in range(n):
			if i in no:
				res.append(i)
			else:
				res.append(-1)
		return res


class Solution:

	def modifyArray(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
		l = []
		for i in range(len(arr)):
			if i in d:
				l.append(i)
			else:
				l.append(-1)
		return l


class Solution:

	def modifyArray(self, arr, n):
		a = [0] * n
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 0
			d[i] += 1
		for i in range(n):
			if i in d:
				a[i] = i
			else:
				a[i] = -1
		return a


class Solution:

	def modifyArray(self, arr, n):
		m = {}
		for i in arr:
			m[i] = 1
		for i in range(n):
			if i in m:
				arr[i] = i
			else:
				arr[i] = -1
		return arr


class Solution:

	def modifyArray(self, A, len):
		for i in range(0, len):
			if A[i] != -1 and A[i] != i:
				x = A[i]
				while A[x] != -1 and A[x] != x:
					y = A[x]
					A[x] = x
					x = y
				A[x] = x
				if A[i] != i:
					A[i] = -1
		return A


class Solution:

	def modifyArray(self, arr, n):
		s = set(arr)
		l = []
		for i in range(0, len(arr)):
			if i in s:
				l.append(i)
			else:
				m = -1
				l.append(m)
		return l


class Solution:

	def modifyArray(self, arr, n):
		ht = {}
		for i in arr:
			if i in ht:
				ht[i] += 1
			else:
				ht[i] = 1
		ans = [-1] * n
		for i in range(0, n):
			if i in ht:
				ans[i] = i
		return ans


class Solution:

	def modifyArray(self, arr, n):
		size = max(arr)
		ans = [-1] * n
		for i in range(n):
			if arr[i] >= 0:
				ans[arr[i]] = arr[i]
		return ans


class Solution:

	def modifyArray(self, arr, n):
		x = {}
		for i in arr:
			x[i] = 1
		arr1 = []
		for i in range(n):
			if i in x:
				arr1.append(i)
			else:
				arr1.append(-1)
		return arr1


class Solution:

	def modifyArray(self, arr, n):
		i = 0
		while i < n:
			correct = arr[i]
			if arr[i] >= 0 and arr[i] != arr[correct]:
				temp = arr[i]
				arr[i] = arr[correct]
				arr[correct] = temp
			else:
				i += 1
		return arr
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.modifyArray(arr, n)
	print(*res)


class Solution:

	def modifyArray(self, arr, n):
		m = {}
		for i in arr:
			m[i] = 1
		c = []
		for i in range(n):
			if i in m:
				c.append(i)
			else:
				c.append(-1)
		return c
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.modifyArray(arr, n)
	print(*res)


class Solution:

	def modifyArray(self, arr, n):
		gg = {}
		for i in arr:
			if i not in gg:
				gg[i] = 1
		for i in range(n):
			if i not in gg:
				arr[i] = -1
			else:
				arr[i] = i
		return arr


class Solution:

	def modifyArray(self, arr, n):
		for i in range(0, n):
			if arr[i] == i:
				continue
			elif arr[i] == -1:
				continue
			else:
				(arr[arr[i]], arr[i]) = (arr[i], arr[arr[i]])
				while True:
					if arr[i] == -1 or arr[i] == i:
						break
					(arr[arr[i]], arr[i]) = (arr[i], arr[arr[i]])
		return arr


class Solution:

	def modifyArray(self, arr, n):
		arr.sort()
		if arr[0] != -1:
			return arr
		final = [None] * n
		for i in range(0, n):
			if arr[i] is not -1:
				final[arr[i]] = arr[i]
		for i in range(0, n):
			if final[i] == None:
				final[i] = -1
		return final


class Solution:

	def modifyArray(self, arr, n):
		a2 = [-1] * n
		for i in range(0, n):
			if arr[i] != -1:
				a2[arr[i]] = arr[i]
		return a2


class Solution:

	def modifyArray(self, arr, n):
		m = len(arr)
		li = [-1] * m
		for i in range(m):
			if arr[i] != -1:
				li[arr[i]] = arr[i]
		return li


from collections import OrderedDict

class Solution:

	def modifyArray(self, A, n):
		s = set()
		for i in range(len(A)):
			s.add(A[i])
		for i in range(len(A)):
			if i in s:
				A[i] = i
			else:
				A[i] = -1
		return A


class Solution:

	def modifyArray(self, a, n):
		i = 0
		while i < len(a):
			if a[i] > -1 and a[i] != i:
				(a[a[i]], a[i]) = (a[i], a[a[i]])
			else:
				i += 1
		return a


class Solution:

	def modifyArray(self, arr, n):
		d = {}
		for e in arr:
			if e not in d:
				d[e] = 1
			else:
				d[e] += 1
		res = [0] * n
		for i in range(n):
			if i in d and d[i] != 0:
				res[i] = i
				d[i] -= 1
			else:
				res[i] = -1
		return res