Given an array of elements of length N, ranging from 0 to N-1, your task is to write a program that rearranges the elements of the array. 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 : A[] = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : -1 1 2 3 4 -1 6 -1 -1 9
Explanation:
Here We can see there are 10 elements. So, the sorted array
will look like {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} but in our
array we are not having 0, 5, 7 and 8. So, at there places
we will be printing -1 and otherplaces will be having elements.
Example 2:
Input : A[] = {2, 0, 1} 
Output : 0 1 2
 
 
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 Rearrange() that takes an array (arr), sizeOfArray (n), and return the array after rearranging it. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
0 ≤ N ≤ 10^{5}
-1 ≤ A[] ≤ N-1
All values are unique other than -1.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



def Rearrange (arr,  n) : 

    #Complete the function



Solutions:
def Rearrange(arr, n):
	output = [-1] * n
	for element in arr:
		if element != -1:
			output[element] = element
	return output


def Rearrange(arr, n):
	n = len(arr)
	j = 0
	while j < n:
		if arr[j] == -1 or arr[j] == j:
			j += 1
		else:
			while True:
				res = arr[j]
				temp = arr[res]
				arr[res] = arr[j]
				arr[j] = temp
				if arr[j] == j or arr[j] == -1:
					break
			j += 1
	return arr


def Rearrange(arr, n):
	from bisect import bisect_left
	arr_sorted = sorted(arr)
	b = [i for i in range(n)]
	for i in range(n):
		idx = bisect_left(arr_sorted, i)
		if idx == len(arr_sorted) or arr_sorted[idx] != i:
			b[i] = -1
	return b


def Rearrange(arr, n):
	p = 0
	while p < n:
		if arr[p] != p and arr[p] != -1:
			target = arr[p]
			replaced = arr[target]
			arr[target] = target
			arr[p] = replaced
		else:
			p = p + 1
	return arr


def Rearrange(arr, n):
	A = [-1 for i in range(n)]
	for j in arr:
		if j != -1:
			A[j] = j
	return A


def Rearrange(arr, n):
	i = 0
	while i < len(arr):
		if arr[i] == i or arr[i] == -1:
			i += 1
		else:
			temp = arr[arr[i]]
			arr[arr[i]] = arr[i]
			arr[i] = temp
	return arr


def Rearrange(arr, n):
	index_dict = {val: 1 for val in arr}
	result_arr = []
	for i in range(n):
		if i in index_dict:
			result_arr.append(i)
		else:
			result_arr.append(-1)
	return result_arr


def Rearrange(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 arr


def Rearrange(arr, n):
	hashset = {}
	for i in range(n):
		if arr[i] in hashset:
			hashset[arr[i]] += 1
		else:
			hashset[arr[i]] = 1
	for i in range(n):
		if i in hashset:
			arr[i] = i
		else:
			arr[i] = -1
	return arr


def Rearrange(arr, n):
	a = []
	for i in range(n + 1):
		a.append(-1)
	for i in range(n):
		try:
			a[arr[i]] = arr[i]
		except:
			pass
	return a[:-1]


def Rearrange(arr, n):
	i = 0
	while i < n:
		if arr[i] != i:
			if arr[i] == -1:
				i += 1
			else:
				ind = arr[i]
				arr[i] = arr[ind]
				arr[ind] = ind
		else:
			i += 1
	return arr


def Rearrange(arr, n):
	s = set(arr)
	lst = []
	for i in range(0, n):
		if i in s:
			lst.append(i)
		else:
			lst.append(-1)
	return lst


def Rearrange(arr, n):
	p = list(range(n))
	d = {elem: 0 for elem in arr}
	for index in range(n):
		if p[index] not in d:
			p[index] = -1
	return p


def Rearrange(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


def Rearrange(arr, n):
	arr.sort()
	for i in range(len(arr)):
		if arr[i] != -1:
			p = arr[arr[i]]
			arr[arr[i]] = arr[i]
			arr[i] = p
	return arr


def Rearrange(arr, n):
	new_arr = [-1] * n
	for (i, x) in enumerate(arr):
		if i != x and x != -1:
			new_arr[x] = x
		elif i == x:
			new_arr[x] = x
	return new_arr


def Rearrange(arr, n):
	new_arr = []
	new_arr_2 = []
	mod_arr = set(arr)
	for i in range(n):
		if i not in mod_arr:
			new_arr.append(-1)
			new_arr_2.append(-1)
		else:
			new_arr.append(i)
			new_arr_2.append(i)
	return new_arr


def Rearrange(A, n):
	list1 = list()
	seta = set(arr)
	for i in range(n):
		if i not in seta:
			list1.append(-1)
		else:
			list1.append(i)
	return list1


def Rearrange(arr, n):
	res = [-1] * n
	for i in arr:
		if i != -1:
			res[i] = i
	return res


def Rearrange(arr, n):
	setti = set(arr)
	output = [-1] * n
	for i in range(n):
		if i in setti:
			output[i] = i
	return output


from collections import defaultdict

def Rearrange(arr, n):
	hmap = defaultdict(int)
	for ele in arr:
		if ele not in hmap:
			hmap[ele] = 1
		else:
			hmap[ele] += 1
	res = []
	for i in range(0, n):
		if i in hmap:
			res.append(i)
		else:
			res.append(-1)
	return res


def Rearrange(arr, n):
	arr.sort()
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in range(n):
		if i in d:
			arr[i] = i
			d[i] -= 1
		else:
			arr[i] = -1
			d[-1] -= 1
	return arr


def Rearrange(arr, n):
	l = [0] * len(arr)
	for i in arr:
		if i != -1:
			l[i] += 1
	for i in range(len(arr)):
		if l[i] == 0:
			l[i] = -1
		else:
			l[i] = i
	return l


def Rearrange(arr, n):
	k = 0
	while k < n:
		i = k
		while arr[i] != -1 and arr[i] != i:
			m = arr[i]
			(arr[i], arr[m]) = (arr[m], arr[i])
		k += 1
	return arr


def Rearrange(arr, n):
	s = set(arr)
	arr = [i for i in range(n)]
	j = 0
	while j < n:
		if j not in s:
			arr[j] = -1
		j += 1
	return arr


def Rearrange(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


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


def Rearrange(arr, n):
	pointer = 0

	def swap(arr, source, target):
		(arr[source], arr[target]) = (arr[target], arr[source])
	while pointer < n:
		if arr[pointer] == -1:
			pointer += 1
		elif arr[pointer] == pointer:
			pointer += 1
		else:
			swap(arr, pointer, arr[pointer])
	return arr


def Rearrange(array, n):
	idx = 0
	while idx < n:
		if array[idx] == -1 or array[idx] == idx:
			idx += 1
		else:
			temp = array[idx]
			array[idx] = array[temp]
			array[temp] = temp
	return array


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


def Rearrange(arr, n):
	count = 0
	while count != n:
		if arr[count] != count and arr[count] != -1:
			if arr[count] == arr[arr[count]]:
				arr[arr[count]] = -1
				count += 1
			else:
				temp = arr[arr[count]]
				arr[arr[count]] = arr[count]
				arr[count] = temp
		elif arr[count] == -1:
			arr[count] = -1
			count += 1
		else:
			count += 1
	return arr


def Rearrange(arr, n):
	i = 0
	while i < n:
		while arr[i] != i and arr[i] != -1:
			swapValue = arr[i]
			(arr[i], arr[swapValue]) = (arr[swapValue], arr[i])
		i += 1
	return arr


def Rearrange(arr, n):
	for i in range(n):
		if arr[i] != -1 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


def Rearrange(arr, n):
	i = 0
	while i < n:
		if arr[i] != -1 and arr[i] != arr[arr[i]]:
			swap(arr, i, arr[i])
		else:
			i += 1
	return arr

def swap(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp


def Rearrange(arr, n):
	for i in range(n):
		if arr[i] not in {-1, i}:
			temp = arr[arr[i]]
			arr[arr[i]] = arr[i]
			arr[i] = -1
			while arr[temp] != temp and temp != -1:
				c = arr[temp]
				arr[temp] = temp
				temp = c
	return arr


def Rearrange(arr, n):
	hmp = [-1 for i in range(n)]
	for i in arr:
		if i != -1:
			hmp[i] = i
	for i in range(n):
		arr[i] = hmp[i]
	return arr


def Rearrange(arr, n):
	temp = []
	for i in range(0, n):
		temp.append(-1)
	for i in range(0, n):
		if arr[i] >= 0:
			temp[arr[i]] = arr[i]
	return temp


def Rearrange(arr, n):
	b = [-1] * n
	out = set(arr)
	for i in out:
		if i != -1:
			b[i] = i
	return b


def Rearrange(arr, n):
	a = arr
	b = [-1] * len(a)
	l = set(a)
	for i in l:
		if i != -1:
			b[i] = i
	return b


from collections import Counter

def Rearrange(arr, n):
	arr.sort()
	l = []
	a = Counter(arr)
	for i in range(n):
		if a[i] > 0:
			l.append(i)
		else:
			l.append(-1)
	return l


def Rearrange(arr, n):
	temp = arr.copy()
	for i in range(n):
		arr[i] = -1
	temp.sort()
	for i in temp:
		if i != -1:
			arr[i] = i
	return arr


def Rearrange(arr, n):
	arr.sort()
	temp = 0
	for i in range(len(arr)):
		if arr[i] != i and arr[i] >= 0:
			temp = arr[arr[i]]
			arr[arr[i]] = arr[i]
			arr[i] = temp
	return arr


def Rearrange(arr, n):
	count_arr = [0 for i in range(n)]
	for i in range(n):
		if arr[i] != -1:
			count_arr[arr[i]] += 1
	for i in range(n):
		val = count_arr[i]
		if val == 0:
			val = -1
		else:
			val = i
		arr[i] = val
	return arr


def Rearrange(arr, n):
	resutl_array = [-1] * n
	for i in arr:
		if i != -1:
			resutl_array[i] = i
	return resutl_array


def Rearrange(arr, n):
	s = set()
	li = []
	for i in arr:
		s.add(i)
	for i in range(0, len(arr)):
		if i in s:
			li.append(i)
		else:
			li.append(-1)
	return li


def Rearrange(arr, n):
	oArr = [-1] * n
	for i in range(n):
		if arr[i] >= 0 and arr[i] < n:
			oArr[arr[i]] = arr[i]
	return oArr


def Rearrange(arr, n):
	for i in range(n):
		if arr[i] != -1 and arr[i] != i:
			while arr[i] != -1 and arr[i] != i:
				tmp = arr[arr[i]]
				arr[arr[i]] = arr[i]
				arr[i] = tmp
	return arr


def Rearrange(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


from collections import defaultdict

def Rearrange(arr, n):
	map = defaultdict(int)
	for i in arr:
		map[i] += 1
	x = list(range(n))
	for i in range(n):
		if x[i] not in map:
			x[i] = -1
		else:
			continue
	return x


def Rearrange(arr, n):
	new_arr = []
	for i in range(n):
		new_arr.append(-1)
	for i in arr:
		if i != -1:
			new_arr[i] = i
	return new_arr


def Rearrange(arr, n):
	for i in range(n):
		if arr[i] != -1 and arr[i] != i:
			ele1 = arr[i]
			while arr[ele1] != -1 and arr[ele1] != ele1:
				ele2 = arr[ele1]
				arr[ele1] = ele1
				ele1 = ele2
			arr[ele1] = ele1
		if arr[i] != i:
			arr[i] = -1
	return arr


def Rearrange(arr, n):
	s = set()
	ans = []
	for i in arr:
		s.add(i)
	for i in range(n):
		if i in s:
			ans.append(i)
		else:
			ans.append(-1)
	return ans


def Rearrange(arr, n):
	arr = set(arr)
	res = []
	for i in range(0, n):
		if i not in arr:
			res.append(-1)
		else:
			res.append(i)
	return res


def Rearrange(arr, n):
	set_arr = set(arr)
	for i in range(len(arr)):
		if i in set_arr:
			arr[i] = i
		else:
			arr[i] = -1
	return arr