You are given an array of size N. Rearrange the given array in-place such that all the negative numbers occur before all non-negative numbers.
(Maintain the order of all -ve and non-negative numbers as given in the original array).
Example 1:
Input:
N = 4
Arr[] = {-3, 3, -2, 2}
Output:
-3 -2 3 2
Explanation:
In the given array, negative numbers
are -3, -2 and non-negative numbers are 3, 2. 
Example 2:
Input:
N = 4
Arr[] = {-3, 1, 0, -2}
Output:
-3 -2 1 0
Explanation:
In the given array, negative numbers
are -3, -2 and non-negative numbers are 1, 0.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function Rearrange() which takes the array Arr[] and its size N as inputs and returns the array after rearranging with spaces between the elements of the array.
Expected Time Complexity: O(N. Log(N))
Expected Auxiliary Space: O(Log(N))
Constraints:
1 ≤ N ≤ 10^{5}
-10^{9} ≤ Elements of array ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: 
from typing import List


class Solution:
    def Rearrange(self, n : int, arr : List[int]) -> None:
        # code here
        


Solutions:
def Rearrange(a, n):
	neg = 0
	for i in range(n):
		if a[i] < 0:
			c = a.pop(i)
			a.insert(neg, c)
			neg += 1
	return a


def Rearrange(a, n):
	neg = []
	pos = []
	for i in a:
		if i < 0:
			neg.append(i)
		else:
			pos.append(i)
	neg = neg + pos
	for i in range(n):
		a[i] = neg[i]


def Rearrange(a, n):
	list1 = list()
	list2 = list()
	for i in a:
		if i < 0:
			list1.append(i)
		else:
			list2.append(i)
	hello = list1 + list2
	for i in range(n):
		a[i] = hello[i]
	return a


def Rearrange(a, n):
	l1 = list()
	l2 = list()
	for i in a:
		if i < 0:
			l1.append(i)
		else:
			l2.append(i)
	h = l1 + l2
	for i in range(n):
		a[i] = h[i]
	return a


def Rearrange(a, n):
	b = []
	c = []
	for i in a:
		if i < 0:
			b.append(i)
		else:
			c.append(i)
	d = b + c
	a[:] = d[:]


def Rearrange(a, n):
	list1 = []
	list2 = []
	for i in a:
		if i < 0:
			list1.append(i)
		else:
			list2.append(i)
	ans = list1 + list2
	for i in range(n):
		a[i] = ans[i]
	return a


def Rearrange(a, n):
	l = list()
	l1 = list()
	for i in a:
		if i < 0:
			l.append(i)
		else:
			l1.append(i)
	he = l + l1
	for i in range(n):
		a[i] = he[i]
	return a


def Rearrange(a, n):
	negative = list()
	positive = list()
	for i in a:
		if i < 0:
			negative.append(i)
		else:
			positive.append(i)
	temp = negative + positive
	for i in range(n):
		a[i] = temp[i]
	return a


def Rearrange(a, n):
	list = []
	for i in a:
		if i < 0:
			list.append(i)
	for i in a:
		if i >= 0:
			list.append(i)
	for i in range(n):
		a[i] = list[i]


def Rearrange(a, n):
	ans = []
	for i in a:
		if i < 0:
			ans.append(i)
	for i in a:
		if i >= 0:
			ans.append(i)
	for i in range(n):
		a[i] = ans[i]


def Rearrange(arr, n):
	negative = []
	positive = []
	for i in range(n):
		if arr[i] < 0:
			negative.append(arr[i])
		else:
			positive.append(arr[i])
	negative.extend(positive)
	arr[:] = negative[:]


def Rearrange(A, n):

	def merge(L, R):
		if L == R:
			if A[L] < 0:
				return (L, L + 1, R + 1)
			else:
				return (L, L, R + 1)
		m = (L + R) // 2
		(Lns, Lne, Lpe) = merge(L, m)
		(Rns, Rne, Rpe) = merge(m + 1, R)
		A[Lne:Lpe] = reversed(A[Lne:Lpe])
		A[Rns:Rne] = reversed(A[Rns:Rne])
		A[Lne:Rne] = reversed(A[Lne:Rne])
		return (L, L + (Lne - Lns + Rne - Rns), R + 1)
	merge(0, n - 1)
	return A


def Rearrange(arr, n):
	current_index = 0
	ar = []
	for i in range(n):
		if arr[i] < 0:
			p = arr[i]
			arr[i] = arr[current_index]
			arr[current_index] = p
			current_index += 1
		else:
			ar.append(arr[i])
	count = 0
	for j in range(current_index, n):
		arr[j] = ar[count]
		count += 1
	return arr


def Rearrange(a, n):
	pos = []
	neg = []
	for i in a:
		if i < 0:
			neg.append(i)
		else:
			pos.append(i)
	lst = neg + pos
	a[:] = lst[:]
	return a


def Rearrange(a, n):
	l = []
	l.extend(a)
	k = []
	z = []
	a.clear()
	for i in l:
		if i < 0:
			z.append(i)
		else:
			k.append(i)
	z.extend(k)
	a.extend(z)


def Rearrange(a, n):
	ne = []
	p = []
	for i in a:
		if i < 0:
			ne.append(i)
		else:
			p.append(i)
	i = 0
	m = len(ne)
	j = 0
	while i < n and j < m:
		a[i] = ne[j]
		i += 1
		j += 1
	q = len(p)
	j = 0
	while i < n and j < q:
		a[i] = p[j]
		i += 1
		j += 1
	return a


def Rearrange(a, n):
	l = []
	for i in a:
		if i < 0:
			l.append(i)
	for i in a:
		if i >= 0:
			l.append(i)
	for i in range(n):
		a[i] = l[i]


def Rearrange(a, n):
	x = []
	x[:] = a[:]
	a.clear()
	index = 0
	for i in range(len(x)):
		if x[i] < 0:
			a.insert(index, x[i])
			index += 1
		else:
			a.append(x[i])


def Rearrange(a, n):
	negin = 0
	posin = 0
	while posin < n:
		if a[posin] < 0:
			a.insert(negin, a.pop(posin))
			posin += 1
			negin += 1
		else:
			posin += 1


def Rearrange(a, n):
	plus = []
	minus = []
	for v in a:
		if v < 0:
			minus.append(v)
		else:
			plus.append(v)
	arr = minus + plus
	for (i, v) in enumerate(arr):
		a[i] = v


def Rearrange(a, n):
	n1 = []
	for i in a:
		if i < 0:
			n1.append(i)
	for i in a:
		if i >= 0:
			n1.append(i)
	for i in range(n):
		a[i] = n1[i]
	return a


def Rearrange(a, n):
	p = []
	ne = []
	for i in a:
		if i < 0:
			ne += [i]
		else:
			p += [i]
	b = ne + p
	for i in range(n):
		a[i] = b[i]


def Rearrange(a, n):
	stack = []
	for i in range(n - 1, -1, -1):
		if a[i] >= 0:
			stack.append(a[i])
	k = 0
	for i in range(n):
		if a[i] < 0:
			a[k] = a[i]
			k += 1
	while len(stack) > 0:
		a[k] = stack.pop()
		k += 1
	return a


def Rearrange(a, n):
	m = []
	p = []
	for i in range(0, n):
		if a[i] < 0:
			m.append(a[i])
		else:
			p.append(a[i])
	c = m + p
	for i in range(0, n):
		a[i] = c[i]


def Rearrange(a, n):
	p = []
	n = []
	for i in range(len(a)):
		if a[i] >= 0:
			p.append(a[i])
		else:
			n.append(a[i])
	for i in range(len(n)):
		a[i] = n[i]
	for i in range(len(p)):
		a[len(n) + i] = p[i]


def Rearrange(a, n):
	b = []
	c = []
	for i in a:
		if i < 0:
			b.append(i)
	for j in a:
		if j >= 0:
			b.append(j)
	for i in range(n):
		a[i] = b[i]
	return a


def Rearrange(a, n):
	neg = []
	pos = []
	for i in range(n):
		if a[i] < 0:
			neg.append(a[i])
		else:
			pos.append(a[i])
	ans = neg + pos
	for (i, v) in enumerate(ans):
		a[i] = v
	return a


def Rearrange(a, n):
	l1 = []
	l2 = []
	for i in range(n):
		if a[i] < 0:
			l1.append(a[i])
		if a[i] >= 0:
			l2.append(a[i])
	x = l1 + l2
	for i in range(len(x)):
		a[i] = x[i]


def Rearrange(a, n):
	lp = []
	ln = []
	for i in a:
		if i < 0:
			ln.append(i)
		else:
			lp.append(i)
	ln.extend(lp)
	a.clear()
	for i in ln:
		a.append(i)
	return a


def Rearrange(a, n):
	l1 = []
	for i in a:
		if i < 0:
			l1.append(i)
	for i in a:
		if i >= 0:
			l1.append(i)
	for i in range(n):
		a[i] = l1[i]


def merge(arr, l, m, r):
	(i, j, k) = (0, 0, 0)
	n1 = m - l + 1
	n2 = r - m
	L = [arr[l + i] for i in range(n1)]
	R = [arr[m + 1 + j] for j in range(n2)]
	i = 0
	j = 0
	k = l
	while i < n1 and L[i] < 0:
		arr[k] = L[i]
		k += 1
		i += 1
	while j < n2 and R[j] < 0:
		arr[k] = R[j]
		k += 1
		j += 1
	while i < n1:
		arr[k] = L[i]
		k += 1
		i += 1
	while j < n2:
		arr[k] = R[j]
		k += 1
		j += 1

def RearrangePosNeg(arr, l, r):
	if l < r:
		m = l + (r - l) // 2
		RearrangePosNeg(arr, l, m)
		RearrangePosNeg(arr, m + 1, r)
		merge(arr, l, m, r)

def Rearrange(arr, n):
	RearrangePosNeg(arr, 0, n - 1)


def Rearrange(a, n):
	po = []
	ne = []
	for k in a:
		if k >= 0:
			po.append(k)
		else:
			ne.append(k)
	np = ne + po
	for i in range(n):
		a[i] = np[i]
	return a


def Rearrange(a, n):
	p = []
	n = []
	for k in a:
		if k >= 0:
			p.append(k)
		else:
			n.append(k)
	for k in range(len(n)):
		a[k] = n[k]
	for k in range(len(p)):
		a[len(n) + k] = p[k]
	return a


def Rearrange(a, n):
	l = []
	r = []
	for i in a:
		if i < 0:
			l.append(i)
		else:
			r.append(i)
	x = len(l)
	for i in range(n):
		if i < x:
			a[i] = l[i]
		else:
			a[i] = r[i - x]


def Rearrange(arr, n):
	pos = list()
	neg = list()
	for i in range(n):
		if arr[i] < 0:
			neg.append(arr[i])
		else:
			pos.append(arr[i])
	i = 0
	while neg:
		arr[i] = neg.pop(0)
		i += 1
	while pos:
		arr[i] = pos.pop(0)
		i += 1
	return arr


def Rearrange(a, n):
	p = []
	n = []
	for i in a:
		if i >= 0:
			p.append(i)
		elif i < 0:
			n.append(i)
	c = n + p
	for i in range(len(a)):
		a[i] = c[i]
	return a


def Rearrange(a, n):
	arr = []
	for i in a:
		if i < 0:
			arr.append(i)
	for i in a:
		if i >= 0:
			arr.append(i)
	for i in range(len(a)):
		a[i] = arr[i]


def Rearrange(a, n):
	flag = False
	neg = []
	pos = []
	for i in range(n):
		if a[i] < 0:
			neg.append(a[i])
		else:
			pos.append(a[i])
	temp = neg + pos
	for i in range(n):
		a[i] = temp[i]


def Rearrange(a, n):
	po = []
	ne = []
	for i in range(n):
		if a[i] < 0:
			ne.append(a[i])
		else:
			po.append(a[i])
	for i in range(n):
		if i < len(ne):
			a[i] = ne[i]
		else:
			a[i] = po[i - len(ne)]


def Rearrange(a, n):
	lp = []
	ln = []
	for i in range(n):
		if a[i] < 0:
			ln.append(a[i])
		else:
			lp.append(a[i])
	r = ln + lp
	for (i, v) in enumerate(r):
		a[i] = v


def Rearrange(a, n):
	b = []
	c = []
	i = 0
	while i < n:
		if a[i] >= 0:
			b.append(a[i])
		else:
			c.append(a[i])
		i += 1
	j = 0
	for i in c:
		a[j] = i
		j += 1
	for i in b:
		a[j] = i
		j += 1


def Rearrange(a, n):
	d = []
	e = []
	for i in range(n):
		if a[i] < 0:
			d.append(a[i])
		else:
			e.append(a[i])
	a[:] = d[:] + e[:]
	return a


def Merge(a, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = [a[l + i] for i in range(n1)]
	R = [a[m + 1 + i] for i in range(n2)]
	i = 0
	j = 0
	k = l
	while i < n1:
		if L[i] < 0:
			a[k] = L[i]
			k += 1
		i += 1
	while j < n2:
		if R[j] < 0:
			a[k] = R[j]
			k += 1
		j += 1
	i = 0
	j = 0
	while i < n1:
		if L[i] >= 0:
			a[k] = L[i]
			k += 1
		i += 1
	while j < n2:
		if R[j] >= 0:
			a[k] = R[j]
			k += 1
		j += 1

def Reag(a, l, r):
	if l < r:
		m = int((l + r) / 2)
		Reag(a, l, m)
		Reag(a, m + 1, r)
		Merge(a, l, m, r)

def Rearrange(a, n):
	Reag(a, 0, n - 1)


def Rearrange(a, n):
	n = []
	p = []
	for i in a:
		if i < 0:
			n.append(i)
		else:
			p.append(i)
	a.clear()
	a[:] = n + p


def Rearrange(a, n):
	Pos = []
	Neg = []
	for i in a:
		if i >= 0:
			Pos.append(i)
		else:
			Neg.append(i)
	a.clear()
	a.extend(Neg)
	a.extend(Pos)


def Rearrange(arr, N):
	p = []
	n = []
	for i in range(N):
		if arr[i] >= 0:
			p.append(arr[i])
		else:
			n.append(arr[i])
	for i in range(len(n)):
		arr[i] = n[i]
	for i in range(len(p)):
		arr[i + len(n)] = p[i]
	return arr


def Rearrange(a, n):
	pos = []
	neg = []
	for i in a:
		if i < 0:
			neg.append(i)
		else:
			pos.append(i)
	a.clear()
	for i in range(len(neg)):
		a.append(neg[i])
	for i in range(len(pos)):
		a.append(pos[i])
	return a


def Rearrange(a, n):
	negative = []
	positive = []
	for i in a:
		if i < 0:
			negative.append(i)
		else:
			positive.append(i)
	a[:] = negative + positive


def Rearrange(a, n):
	p = []
	n1 = []
	for i in a:
		if i >= 0:
			p.append(i)
		else:
			n1.append(i)
	for j in range(len(p)):
		n1.append(p[j])
	for i in range(len(a)):
		a[i] = n1[i]
	return a


def Rearrange(a, n):
	ng = []
	p = []
	for i in range(n):
		if a[i] < 0:
			ng.append(a[i])
		elif a[i] >= 0:
			p.append(a[i])
	ng = ng + p
	a[:] = ng[:]


def Rearrange(a, n):
	(pos, neg) = ([], [])
	for i in a:
		if i < 0:
			neg.append(i)
		else:
			pos.append(i)
	a.clear()
	a.extend(neg + pos)


def Rearrange(a, n):
	l = []
	x = []
	for i in a:
		if i < 0:
			l.append(i)
		else:
			x.append(i)
	b = []
	b.extend(l)
	b.extend(x)
	for i in range(0, len(b)):
		a[i] = b[i]
	return a