Given an unsorted array Arr of N positive and negative numbers. Your task is to create an array of alternate positive and negative numbers without changing the relative order of positive and negative numbers.
Note: Array should start with a positive number and 0 (zero) should be considered a positive element.
 
Example 1:
Input: 
N = 9
Arr[] = {9, 4, -2, -1, 5, 0, -5, -3, 2}
Output:
9 -2 4 -1 5 -5 0 -3 2
Explanation : Positive elements : 9,4,5,0,2
Negative elements : -2,-1,-5,-3
As we need to maintain the relative order of
postive elements and negative elements we will pick
each element from the positive and negative and will
store them. If any of the positive and negative numbers
are completed. we will continue with the remaining signed
elements.The output is 9,-2,4,-1,5,-5,0,-3,2.
Example 2:
Input:
N = 10
Arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
Output:
5 -5 2 -2 4 -8 7 1 8 0
Explanation : Positive elements : 5,2,4,7,1,8,0
Negative elements : -5,-2,-8
As we need to maintain the relative order of
postive elements and negative elements we will pick
each element from the positive and negative and will
store them. If any of the positive and negative numbers
are completed. we will continue with the remaining signed
elements.The output is 5,-5,2,-2,4,-8,7,1,8,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 of integers arr[] and n as parameters. You need to modify the array itself.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{7}
-10^{6} ≤ Arr[i] ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def rearrange(self,arr, n):

        # code here

Solutions:
class Solution:

	def rearrange(self, arr, n):
		pn = []
		nn = []
		for i in arr:
			if i < 0:
				nn.append(i)
			else:
				pn.append(i)
		i = 0
		pn.reverse()
		nn.reverse()
		while len(pn) != 0 and len(nn) != 0:
			p = pn.pop()
			arr[i] = p
			n = nn.pop()
			i += 1
			arr[i] = n
			i += 1
		if len(pn) != 0:
			while len(pn) > 0:
				p = pn.pop()
				arr[i] = p
				i += 1
		if len(nn) != 0:
			while len(nn) > 0:
				n = nn.pop()
				arr[i] = n
				i += 1


class Solution:

	def rearrange(self, arr, n):
		e = []
		o = []
		for i in range(len(arr)):
			if arr[i] >= 0:
				e.append(arr[i])
			else:
				o.append(arr[i])
		res = []
		for i in range(min(len(e), len(o))):
			res.append(e[i])
			res.append(o[i])
		if len(e) < len(o):
			for i in range(len(e), len(o)):
				res.append(o[i])
		else:
			for i in range(len(o), len(e)):
				res.append(e[i])
		for i in range(len(arr)):
			arr[i] = res[i]


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i >= 0:
				pos.append(i)
			else:
				neg.append(i)
		r = []
		for i in range(min(len(pos), len(neg))):
			r.append(pos[i])
			r.append(neg[i])
		idx = min(len(pos), len(neg))
		r += pos[idx:]
		r += neg[idx:]
		for i in range(len(arr)):
			arr[i] = r[i]
		return r


class Solution:

	def rearrange(self, arr, n):
		POS = []
		NEG = []
		for k in arr:
			if k < 0:
				NEG.append(k)
			else:
				POS.append(k)
		res = []
		i = 0
		j = 0
		while i < len(POS) and j < len(NEG):
			res.append(POS[i])
			res.append(NEG[j])
			i += 1
			j += 1
		while i < len(POS):
			res.append(POS[i])
			i += 1
		while j < len(NEG):
			res.append(NEG[j])
			j += 1
		for l in range(len(res)):
			arr[l] = res[l]
		return arr


class Solution:

	def rearrange(self, arr, n):
		p = []
		n = []
		for i in arr:
			if i < 0:
				n.append(i)
			else:
				p.append(i)
		x = min(len(p), len(n))
		for j in range(x):
			arr[2 * j] = p[j]
			arr[2 * j + 1] = n[j]
		arr[2 * x:] = p[x:] if len(p) > len(n) else n[x:]
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for val in arr:
			if val < 0:
				neg.append(val)
			else:
				pos.append(val)
		commonIdx = min(len(pos), len(neg))
		for idx in range(commonIdx):
			arr[2 * idx] = pos[idx]
			arr[2 * idx + 1] = neg[idx]
		arr[2 * commonIdx:] = pos[commonIdx:] if len(pos) > len(neg) else neg[commonIdx:]
		return arr


class Solution:

	def rearrange(self, arr, n):
		(pos, neg) = ([], [])
		(indx, flag) = (0, True)
		for elem in arr:
			if elem >= 0:
				pos.append(elem)
			else:
				neg.append(elem)
		while len(pos) and len(neg):
			if flag:
				arr[indx] = pos.pop(0)
			else:
				arr[indx] = neg.pop(0)
			indx += 1
			flag = not flag
		while len(pos):
			arr[indx] = pos.pop(0)
			indx += 1
		while len(neg):
			arr[indx] = neg.pop(0)
			indx += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		(pos, neg) = ([], [])
		for item in arr:
			if item < 0:
				neg.append(item)
			else:
				pos.append(item)
		if len(pos) < len(neg):
			for i in range(len(pos)):
				arr[2 * i] = pos[i]
				arr[2 * i + 1] = neg[i]
			index = len(pos) * 2
			for i in range(len(pos), len(neg)):
				arr[index] = neg[i]
				index += 1
		else:
			for i in range(len(neg)):
				arr[2 * i] = pos[i]
				arr[2 * i + 1] = neg[i]
			index = len(neg) * 2
			for i in range(len(neg), len(pos)):
				arr[index] = pos[i]
				index += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		res = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		i = 0
		j = 0
		for i in range(n):
			if i < len(pos):
				res.append(pos[i])
				i += 1
			if j < len(neg):
				res.append(neg[j])
				j += 1
		for k in range(n):
			arr[k] = res[k]


class Solution:

	def rearrange(self, arr, n):
		pos = [i for i in arr if i >= 0]
		neg = [i for i in arr if i < 0]
		pos_index = 0
		neg_index = 0
		positive_flag = True if pos else False
		for i in range(n):
			if positive_flag and pos_index < len(pos):
				arr[i] = pos[pos_index]
				pos_index += 1
				if neg_index < len(neg):
					positive_flag = False
			elif not positive_flag and neg_index < len(neg):
				arr[i] = neg[neg_index]
				neg_index += 1
				if pos_index < len(pos):
					positive_flag = True
		return arr


class Solution:

	def rearrange(self, arr, n):
		postive = []
		Negative = []
		for a in range(n):
			if arr[a] >= 0:
				postive.append(arr[a])
			else:
				Negative.append(arr[a])
		i = 0
		j = 0
		k = 0
		while i < len(postive) and j < len(Negative):
			arr[k] = postive[i]
			i += 1
			k += 1
			arr[k] = Negative[j]
			j += 1
			k += 1
		while i < len(postive):
			arr[k] = postive[i]
			i += 1
			k += 1
		while j < len(Negative):
			arr[k] = Negative[j]
			j += 1
			k += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		b = []
		c = []
		for i in range(0, len(arr)):
			if arr[i] >= 0:
				b.append(arr[i])
			else:
				c.append(arr[i])
		arr.clear()
		i = 0
		j = 0
		flag = 1
		v = []
		while i != len(b) and j != len(c):
			if flag == 1:
				arr.append(b[i])
				i += 1
				flag = 0
			else:
				arr.append(c[j])
				j += 1
				flag = 1
		if i == len(b):
			while j < len(c):
				arr.append(c[j])
				j += 1
		if j == len(c):
			while i < len(b):
				arr.append(b[i])
				i += 1


class Solution:

	def rearrange(self, arr, n):
		positive = []
		negative = []
		for num in arr:
			if num >= 0:
				positive.append(num)
			else:
				negative.append(num)
		p_i = 0
		n_i = 0
		i = 0
		while p_i < len(positive) and n_i < len(negative):
			if i & 1 == 0:
				arr[i] = positive[p_i]
				p_i += 1
			else:
				arr[i] = negative[n_i]
				n_i += 1
			i += 1
		while p_i < len(positive):
			arr[i] = positive[p_i]
			p_i += 1
			i += 1
		while n_i < len(negative):
			arr[i] = negative[n_i]
			n_i += 1
			i += 1


class Solution:

	def rearrange(self, arr, n):
		(pos, neg) = ([], [])
		(plen, nlen, res) = (0, 0, [])
		for i in arr:
			if i >= 0:
				pos.append(i)
				plen += 1
			else:
				neg.append(i)
				nlen += 1
		idx = 0
		(p, n, posl) = (0, 0, 0)
		while p < plen and n < nlen:
			(arr[posl], arr[posl + 1]) = (pos[p], neg[n])
			(p, n, posl) = (p + 1, n + 1, posl + 2)
		while n < nlen:
			arr[posl] = neg[n]
			(n, posl) = (n + 1, posl + 1)
		while p < plen:
			arr[posl] = pos[p]
			(p, posl) = (p + 1, posl + 1)


class Solution:

	def rearrange(self, arr, nn):
		neg = []
		pos = []
		i = 0
		(p, n) = (0, 0)
		for element in arr:
			if element >= 0:
				pos.append(element)
			else:
				neg.append(element)
		while p < len(pos) and n < len(neg):
			arr[i] = pos[p]
			i += 1
			p += 1
			arr[i] = neg[n]
			i += 1
			n += 1
		while p < len(pos):
			arr[i] = pos[p]
			i += 1
			p += 1
		while n < len(neg):
			arr[i] = neg[n]
			i += 1
			n += 1


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		arr.clear()
		i = 0
		j = 0
		flag = 1
		while i != len(pos) and j != len(neg):
			if flag == 1:
				arr.append(pos[i])
				i += 1
				flag = 0
			else:
				arr.append(neg[j])
				j += 1
				flag = 1
		if i == len(pos):
			while j < len(neg):
				arr.append(neg[j])
				j += 1
		if j == len(neg):
			while i < len(pos):
				arr.append(pos[i])
				i += 1


class Solution:

	def rearrange(self, arr, n):
		c = []
		pos = []
		neg = []
		for i in arr:
			if i >= 0:
				pos.append(i)
			else:
				neg.append(i)
		leng = min(len(pos), len(neg))
		for i in range(leng):
			c.append(pos[i])
			c.append(neg[i])
		if len(pos) > leng:
			c.extend(pos[leng:])
		else:
			c.extend(neg[leng:])
		arr[:] = c[:]
		return c


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for num in arr:
			if num < 0:
				neg.append(num)
			else:
				pos.append(num)
		f = arr[0]
		arr.clear()
		for i in range(len(neg) if len(neg) < len(pos) else len(pos)):
			arr.append(pos[0])
			pos.pop(0)
			arr.append(neg[0])
			neg.pop(0)
		if len(pos) == 0:
			arr.extend(neg)
		else:
			arr.extend(pos)


class Solution:

	def rearrange(self, arr, n):
		from collections import deque
		positiveQ = deque()
		negativeQ = deque()
		for num in arr:
			if num >= 0:
				positiveQ.append(num)
			else:
				negativeQ.append(num)
		i = 0
		while positiveQ and negativeQ:
			arr[i] = positiveQ.popleft()
			arr[i + 1] = negativeQ.popleft()
			i += 2
		while positiveQ:
			arr[i] = positiveQ.popleft()
			i += 1
		while negativeQ:
			arr[i] = negativeQ.popleft()
			i += 1


class Solution:

	def rearrange(self, arr, n):
		arr_p = []
		arr_n = []
		for i in arr:
			if i < 0:
				arr_n.append(i)
			else:
				arr_p.append(i)
		i = 0
		ni = 0
		n_l = len(arr_n)
		p_l = len(arr_p)
		pi = 0
		start = 0
		if len(arr_p):
			arr[0] = arr_p[0]
			pi = 1
			start = 1
		for i in range(start, n):
			if arr[i - 1] < 0 and pi < p_l:
				data = arr_p[pi]
				pi += 1
			elif arr[i - 1] >= 0 and ni < n_l:
				data = arr_n[ni]
				ni += 1
			elif ni == n_l and pi < p_l:
				data = arr_p[pi]
				pi += 1
			elif pi == p_l and ni < n_l:
				data = arr_n[ni]
				ni += 1
			arr[i] = data
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i < 0:
				neg.append(i)
			else:
				pos.append(i)
		i = 0
		while i < min(len(pos), len(neg)):
			arr[2 * i] = pos[i]
			arr[2 * i + 1] = neg[i]
			i += 1
		t = 2 * i
		while t < n and i < len(pos):
			arr[t] = pos[i]
			t += 1
			i += 1
		while t < n and i < len(neg):
			arr[t] = neg[i]
			t += 1
			i += 1


class Solution:

	def rearrange(self, arr, n):
		list1 = []
		list2 = []
		list3 = []
		for i in arr:
			if i >= 0:
				list1.append(i)
			else:
				list2.append(i)
		c = min(len(list1), len(list2))
		for i in range(c):
			list3.append(list1[i])
			list3.append(list2[i])
		if len(list1) > c:
			list3.extend(list1[c:])
		elif len(list2) > c:
			list3.extend(list2[c:])
		arr[:] = list3[:]
		return list3


class Solution:

	def rearrange(self, arr, n):
		posarray = []
		negarray = []
		for val in arr:
			if val >= 0:
				posarray.append(val)
			else:
				negarray.append(val)
		i = 0
		j = 0
		k = 0
		while k < n:
			if i < len(posarray):
				arr[k] = posarray[i]
				i += 1
				k += 1
			if j < len(negarray):
				arr[k] = negarray[j]
				j += 1
				k += 1


class Solution:

	def rearrange(self, arr, n):
		ans = []
		i = 0
		j = 0
		flag = True
		while i < n:
			if arr[i] >= 0:
				break
			i += 1
		while j < n:
			if arr[j] < 0:
				break
			j += 1
		while i < n and j < n:
			if flag:
				ans.append(arr[i])
				i += 1
				while i < n:
					if arr[i] >= 0:
						break
					i += 1
				flag = False
			else:
				ans.append(arr[j])
				j += 1
				while j < n:
					if arr[j] < 0:
						break
					j += 1
				flag = True
		while i < n:
			if arr[i] >= 0:
				ans.append(arr[i])
			i += 1
		while j < n:
			if arr[j] < 0:
				ans.append(arr[j])
			j += 1
		for i in range(len(arr)):
			arr[i] = ans[i]


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		ans = []
		(n, p) = (0, 0)
		for i in arr:
			if i >= 0:
				pos.append(i)
				p += 1
			else:
				neg.append(i)
				n += 1
		i = 0
		(x, y) = (0, 0)
		while x < p and y < n:
			if i % 2 == 0:
				arr[i] = pos[x]
				x += 1
			else:
				arr[i] = neg[y]
				y += 1
			i += 1
		while x < p:
			arr[i] = pos[x]
			x += 1
			i += 1
		while y < n:
			arr[i] = neg[y]
			y += 1
			i += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		res = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		i = 0
		j = 0
		n = len(pos)
		m = len(neg)
		while i < n and j < m:
			res.append(pos[i])
			i += 1
			res.append(neg[j])
			j += 1
		while i < n:
			res.append(pos[i])
			i += 1
		while j < m:
			res.append(neg[j])
			j += 1
		for i in range(len(arr)):
			arr[i] = res[i]


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		new = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		(pi, ni) = (0, 0)
		count = 0
		while pi < len(pos) and ni < len(neg):
			arr[count] = pos[pi]
			count += 1
			arr[count] = neg[ni]
			count += 1
			pi += 1
			ni += 1
		if pi < len(pos):
			while pi < len(pos):
				arr[count] = pos[pi]
				count += 1
				pi += 1
		if ni < len(neg):
			while ni < len(neg):
				arr[count] = neg[ni]
				count += 1
				ni += 1


class Solution:

	def rearrange(self, arr, n):
		p = []
		ne = []
		c = []
		j = 0
		k = 0
		for i in range(n):
			if arr[i] >= 0:
				p.append(arr[i])
			else:
				ne.append(arr[i])
		lenp = len(p)
		lenn = len(ne)
		if lenp >= lenn:
			for i in range(0, lenn):
				c.append(p[i])
				c.append(ne[i])
			for i in range(lenn, lenp):
				c.append(p[i])
		else:
			for i in range(0, lenp):
				c.append(p[i])
				c.append(ne[i])
			for i in range(lenp, lenn):
				c.append(ne[i])
		for i in range(len(arr)):
			arr[i] = c[i]


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i < 0:
				neg.append(i)
			else:
				pos.append(i)
		arr.clear()
		for i in range(n):
			if i % 2 == 0:
				if pos:
					arr.append(pos.pop(0))
				elif neg:
					arr.append(neg.pop(0))
			elif neg:
				arr.append(neg.pop(0))
			elif pos:
				arr.append(pos.pop(0))


class Solution:

	def rearrange(self, arr, n):
		pos = []
		plen = 0
		neg = []
		nlen = 0
		for i in range(n):
			if arr[i] < 0:
				neg.append(arr[i])
				nlen += 1
			else:
				pos.append(arr[i])
				plen += 1
		(p, n, pos1) = (0, 0, 0)
		while p < plen and n < nlen:
			(arr[pos1], arr[pos1 + 1]) = (pos[p], neg[n])
			(p, n, pos1) = (p + 1, n + 1, pos1 + 2)
		while n < nlen:
			arr[pos1] = neg[n]
			(n, pos1) = (n + 1, pos1 + 1)
		while p < plen:
			arr[pos1] = pos[p]
			(p, pos1) = (p + 1, pos1 + 1)


class Solution:

	def rearrange(self, arr, n):
		A = []
		B = []
		C = []
		for i in range(n):
			if arr[i] >= 0:
				A.append(arr[i])
			else:
				B.append(arr[i])
		i = 0
		while i < len(A) and i < len(B):
			C.append(A[i])
			C.append(B[i])
			i += 1
		if i < len(A):
			for i in range(i, len(A)):
				C.append(A[i])
		else:
			for i in range(i, len(B)):
				C.append(B[i])
		for i in range(n):
			arr[i] = C[i]


class Solution:

	def rearrange(self, arr, n):
		po = []
		ne = []
		for i in range(n):
			if arr[i] < 0:
				ne.append(arr[i])
			else:
				po.append(arr[i])
		i = 0
		j = 0
		k = 0
		while i < len(po) and j < len(ne):
			arr[k] = po[i]
			k += 1
			i += 1
			arr[k] = ne[j]
			k += 1
			j += 1
		while i < len(po):
			arr[k] = po[i]
			k += 1
			i += 1
		while j < len(ne):
			arr[k] = ne[j]
			k += 1
			j += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		arr.clear()
		pos_l = len(pos)
		neg_l = len(neg)
		j = 0
		for i in range(n):
			if pos_l != 0:
				arr.append(pos[j])
				pos_l -= 1
			if neg_l != 0:
				arr.append(neg[j])
				neg_l -= 1
			j += 1


class Solution:

	def rearrange(self, arr, n):
		ans = []
		pos = []
		neg = []
		for element in arr:
			if element < 0:
				neg.append(element)
			else:
				pos.append(element)
		min_len = min(len(pos), len(neg))
		max_len = max(len(pos), len(neg))
		for i in range(min_len):
			ans.append(pos[i])
			ans.append(neg[i])
		for i in range(min_len, max_len):
			if len(pos) == min_len:
				ans.append(neg[i])
			else:
				ans.append(pos[i])
		for i in range(len(ans)):
			arr[i] = ans[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		arr2 = [None] * n
		pi = 0
		pj = n
		for i in arr:
			if i >= 0:
				arr2[pi] = i
				pi += 1
			else:
				pj -= 1
				arr2[pj] = i
		arr.clear()
		pk = n
		for i in range(pi):
			arr.append(arr2[i])
			if n > pj and pk > pj:
				pk -= 1
				arr.append(arr2[pk])
		arr.extend(arr2[pj:pk][::-1])


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		for i in range(n):
			arr.pop()
		i = 0
		j = 0
		while len(arr) < n:
			if i < len(pos) and j < len(neg):
				arr.append(pos[i])
				i += 1
				arr.append(neg[j])
				j += 1
			elif i < len(pos):
				arr.append(pos[i])
				i += 1
			elif j < len(neg):
				arr.append(neg[j])
				j += 1
		arr = arr


class Solution:

	def rearrange(self, arr, n):
		negative = []
		positive = []
		sorted = []
		for i in range(n):
			if arr[i] < 0:
				negative.append(arr[i])
			else:
				positive.append(arr[i])
		(p, n) = (len(positive), len(negative))
		arr.clear()
		if p == n:
			for i in range(p):
				arr.append(positive[i])
				arr.append(negative[i])
		elif p < n:
			for i in range(p):
				arr.append(positive[i])
				arr.append(negative[i])
			for i in range(p, n):
				arr.append(negative[i])
		else:
			for i in range(n):
				arr.append(positive[i])
				arr.append(negative[i])
			for i in range(n, p):
				arr.append(positive[i])


class Solution:

	def rearrange(self, arr, n):
		postive_hold = []
		negative_hold = []
		for i in range(len(arr)):
			if arr[i] >= 0:
				postive_hold.append(arr[i])
			elif arr[i] < 0:
				negative_hold.append(arr[i])
		chance = 1
		over_neg = 0
		over_pos = 0
		for i in range(len(arr)):
			if chance == 1:
				if len(postive_hold) > 0:
					arr[i] = postive_hold.pop(0)
					chance = 0
				else:
					over_pos = 1
			elif chance == 0:
				if len(negative_hold) > 0:
					arr[i] = negative_hold.pop(0)
					chance = 1
				else:
					over_neg = 1
			if over_pos == 1:
				n = len(negative_hold)
				pos = i
				for i in range(n):
					arr[pos] = negative_hold.pop(0)
					pos += 1
				break
			if over_neg == 1:
				n = len(postive_hold)
				pos = i
				for i in range(n):
					arr[pos] = postive_hold.pop(0)
					pos += 1
				break
		return arr


class Solution:

	def rearrange(self, arr, n):
		poz_prvky = []
		neg_prvky = []
		for prv in arr:
			if prv >= 0:
				poz_prvky.append(prv)
			else:
				neg_prvky.append(prv)
		poz = 0
		neg = 0
		pointer = 0
		while pointer < n:
			if len(poz_prvky) > poz:
				arr[pointer] = poz_prvky[poz]
				pointer += 1
				poz += 1
			if len(neg_prvky) > neg:
				arr[pointer] = neg_prvky[neg]
				pointer += 1
				neg += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		(pos, neg) = ([], [])
		for i in arr:
			if i >= 0:
				pos.append(i)
			else:
				neg.append(i)
		(p, n) = (len(pos), len(neg))
		arr.clear()
		if p == n:
			for i in range(p):
				arr.append(pos[i])
				arr.append(neg[i])
		elif p < n:
			for i in range(p):
				arr.append(pos[i])
				arr.append(neg[i])
			for i in range(p, n):
				arr.append(neg[i])
		else:
			for i in range(n):
				arr.append(pos[i])
				arr.append(neg[i])
			for i in range(n, p):
				arr.append(pos[i])


class Solution:

	def rearrange(self, arr, n):
		pos = [i for i in arr if i > -1]
		neg = [i for i in arr if i < 0]
		(i, p, n) = (0, 0, 0)
		while p < len(pos) and n < len(neg):
			arr[i] = pos[p]
			i += 1
			p += 1
			arr[i] = neg[n]
			i += 1
			n += 1
		while p < len(pos):
			arr[i] = pos[p]
			p += 1
			i += 1
		while n < len(neg):
			arr[i] = neg[n]
			n += 1
			i += 1


class Solution(object):

	def rearrange(self, arr, n):
		(posNums, negNums) = ([], [])
		for num in arr:
			if num >= 0:
				posNums.append(num)
			else:
				negNums.append(num)
		posNum = negNum = index = 0
		(posSize, negSize) = (len(posNums), len(negNums))
		while index < n:
			if posNum < posSize:
				arr[index] = posNums[posNum]
				posNum += 1
				index += 1
			if negNum < negSize:
				arr[index] = negNums[negNum]
				negNum += 1
				index += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = [i for i in arr if i >= 0][::-1]
		neg = [i for i in arr if i < 0][::-1]
		arr.clear()
		for i in range(n):
			if len(pos) > 0:
				arr.append(pos.pop())
			if len(neg) > 0:
				arr.append(neg.pop())


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i < 0:
				neg.append(i)
			else:
				pos.append(i)
		i = 0
		j = 0
		k = 0
		while i < len(pos) and j < len(neg):
			arr[k] = pos[i]
			i += 1
			k += 1
			arr[k] = neg[j]
			j += 1
			k += 1
		while i < len(pos):
			arr[k] = pos[i]
			k += 1
			i += 1
		while j < len(neg):
			arr[k] = neg[j]
			k += 1
			j += 1


class Solution:

	def rearrange(self, arr, n):
		l1 = []
		l2 = []
		c = 1
		import numpy as np
		for i in arr:
			if i >= 0:
				l1.append(i)
			elif i < 0:
				l2.append(i)
		if len(l1) == 0 or len(l2) == 0:
			return
		if len(l1) == len(l2):
			for i in range(n):
				if i % 2 == 0:
					arr[i] = l1[i // 2]
				if i % 2 != 0:
					arr[i] = l2[i - c]
					c = c + 1
		elif len(l1) < len(l2):
			for i in range(2 * len(l1)):
				if i % 2 == 0:
					arr[i] = l1[i // 2]
				if i % 2 != 0:
					arr[i] = l2[i - c]
					c = c + 1
			for i in range(len(l1), len(l2)):
				arr[i + len(l1)] = l2[i]
		elif len(l2) < len(l1):
			for i in range(2 * len(l2)):
				if i % 2 == 0:
					arr[i] = l1[i // 2]
				if i % 2 != 0:
					arr[i] = l2[i - c]
					c = c + 1
			for i in range(len(l2), len(l1)):
				arr[i + len(l2)] = l1[i]


class Solution:

	def rearrange(self, arr, n):
		neg = []
		pos = []
		for i in range(n):
			if arr[i] < 0:
				neg.append(arr[i])
			elif arr[i] >= 0:
				pos.append(arr[i])
		(i, j, idx) = (0, 0, 0)
		while i < len(pos) and j < len(neg):
			arr[idx] = pos[i]
			idx += 1
			i += 1
			arr[idx] = neg[j]
			idx += 1
			j += 1
		if len(pos) > len(neg):
			arr[idx:] = pos[i:]
		elif len(pos) < len(neg):
			arr[idx:] = neg[j:]
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = {}
		neg = {}
		(l, m) = (0, 0)
		for i in arr:
			if i < 0:
				neg[m] = i
				m += 1
			else:
				pos[l] = i
				l += 1
		(a, b) = (0, 0)
		for i in range(n):
			if l != 0 and m != 0 and (i % 2 == 0):
				arr[i] = pos[a]
				a += 1
				l -= 1
			elif m != 0 and l != 0 and (i % 2 != 0):
				arr[i] = neg[b]
				b += 1
				m -= 1
			elif l != 0 and m == 0:
				arr[i] = pos[a]
				a += 1
				l -= 1
			elif m != 0 and l == 0:
				arr[i] = neg[b]
				b += 1
				m -= 1


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i >= 0:
				pos.append(i)
			else:
				neg.append(i)
		if len(pos) > len(neg):
			for i in range(0, len(neg)):
				arr[2 * i] = pos[i]
				arr[2 * i + 1] = neg[i]
			ind = len(neg) * 2
			for i in range(len(neg), len(pos)):
				arr[ind] = pos[i]
				ind += 1
		else:
			for i in range(0, len(pos)):
				arr[2 * i] = pos[i]
				arr[2 * i + 1] = neg[i]
			ind = len(pos) * 2
			for i in range(len(pos), len(neg)):
				arr[ind] = neg[i]
				ind += 1


class Solution:

	def rearrange(self, arr, n):
		poss = []
		negs = []
		for i in range(n):
			if arr[i] >= 0:
				poss.append(arr[i])
			else:
				negs.append(arr[i])
		total_pos = len(poss)
		total_negs = len(negs)
		mineles = min(total_pos, total_negs)
		for i in range(mineles):
			arr[i * 2] = poss[i]
			arr[i * 2 + 1] = negs[i]
		leftin = poss if total_pos > total_negs else negs
		extraele = max(total_pos, total_negs) - mineles
		for i in range(1, extraele + 1):
			arr[-i] = leftin[-i]


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		pos_len = len(pos)
		neg_len = len(neg)
		index_ = 0
		min_ = min(pos_len, neg_len)
		for i in range(min_):
			arr[index_] = pos[i]
			index_ += 1
			arr[index_] = neg[i]
			index_ += 1
		if min_ < pos_len:
			for i in range(min_, len(pos)):
				arr[index_] = pos[i]
				index_ += 1
		else:
			for i in range(min_, len(neg)):
				arr[index_] = neg[i]
				index_ += 1
		return arr
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		(p, n, position) = (0, 0, 0)
		while p < len(pos) and n < len(neg):
			(arr[position], arr[position + 1]) = (pos[p], neg[n])
			p += 1
			n += 1
			position += 2
		while n < len(neg):
			arr[position] = neg[n]
			n += 1
			position += 1
		while p < len(pos):
			arr[position] = pos[p]
			p += 1
			position += 1


class Solution:

	def rearrange(self, arr, n):
		p = []
		n = []
		for i in arr:
			if i >= 0:
				p.append(i)
			else:
				n.append(i)
		ans = []
		for i in range(min(len(p), len(n))):
			ans.append(p[i])
			ans.append(n[i])
		if len(p) > len(n):
			ans += p[len(n):len(p)]
		else:
			ans += n[len(p):len(n)]
		arr[:] = ans[:]


class Solution:

	def rearrange(self, A, n):
		pos = []
		neg = []
		for i in A:
			if i < 0:
				neg.append(i)
			else:
				pos.append(i)
		if len(pos) < len(neg):
			for i in range(len(pos)):
				A[2 * i] = pos[i]
				A[2 * i + 1] = neg[i]
			index = len(pos) * 2
			for i in range(len(pos), len(neg), 1):
				A[index] = neg[i]
				index += 1
		else:
			for i in range(len(neg)):
				A[2 * i] = pos[i]
				A[2 * i + 1] = neg[i]
			index = len(neg) * 2
			for i in range(len(neg), len(pos), 1):
				A[index] = pos[i]
				index += 1


class Solution:

	def rearrange(self, arr, n):
		li = []
		for ele in arr:
			if ele < 0:
				li.append(ele)
		li1 = []
		for ele in arr:
			if ele >= 0:
				li1.append(ele)
		if len(li1) == n or len(li) == n:
			return
		if len(li) < len(li1):
			j = 0
			for i in range(len(li)):
				arr[j] = li1[i]
				j += 1
				arr[j] = li[i]
				j += 1
			for i in range(len(li), len(li1)):
				arr[j] = li1[i]
				j += 1
		else:
			j = 0
			for i in range(len(li1)):
				arr[j] = li1[i]
				j += 1
				arr[j] = li[i]
				j += 1
			for i in range(len(li1), len(li)):
				arr[j] = li[i]
				j += 1


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		ans = []
		for i in arr:
			if i >= 0:
				pos.append(i)
			else:
				neg.append(i)
		for i in range(n):
			if i % 2 == 0:
				if len(pos) == 0:
					ans.extend(neg)
					break
				ele = pos[0]
				pos.remove(ele)
				ans.append(ele)
			else:
				if len(neg) == 0:
					ans.extend(pos)
					break
				ele = neg[0]
				neg.remove(ele)
				ans.append(ele)
		arr[0:] = ans


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i < 0:
				neg.append(i)
			else:
				pos.append(i)
		l = []
		m = neg.copy()
		for i in range(len(pos)):
			l.append(pos[0])
			pos.pop(0)
			if i < len(m):
				l.append(neg[0])
				neg.pop(0)
		l = l + pos + neg
		for i in range(len(arr)):
			arr[i] = l[i]


class Solution:

	def rearrange(self, arr, n):
		b = []
		a = []
		p = 0
		k = 0
		for i in range(n):
			if arr[i] >= 0:
				a.append(arr[i])
			else:
				b.append(arr[i])
		for i in range(n):
			if p >= len(a):
				arr[i] = b[k]
				k = k + 1
			elif k >= len(b):
				arr[i] = a[p]
				p = p + 1
			elif i % 2 == 0:
				arr[i] = a[p]
				p = p + 1
			else:
				arr[i] = b[k]
				k = k + 1


class Solution:

	def rearrange(self, arr, n):
		n = []
		p = []
		res = []
		for i in arr:
			if i < 0:
				n.append(i)
			else:
				p.append(i)
		c = min(len(p), len(n))
		for i in range(c):
			res.append(p[i])
			res.append(n[i])
		if len(p) > c:
			res.extend(p[c:])
		elif len(n) > c:
			res.extend(n[c:])
		arr[:] = res[:]
		return res


class Solution:

	def rearrange(self, arr, n):
		a = []
		b = []
		ne = 0
		p = 0
		for i in arr:
			if i < 0:
				ne += 1
				b.append(i)
			else:
				p += 1
				a.append(i)
		if p == 0 or ne == 0:
			return
		elif len(b) == len(a):
			k = 0
			for i in range(len(a)):
				arr[k] = a[i]
				k += 1
				arr[k] = b[i]
				k += 1
		elif len(b) < len(a):
			k = 0
			for j in range(len(b)):
				arr[k] = a[j]
				k += 1
				arr[k] = b[j]
				k += 1
			arr[k:] = a[j + 1:]
		else:
			k = 0
			for j in range(len(a)):
				arr[k] = a[j]
				k += 1
				arr[k] = b[j]
				k += 1
			arr[k:] = b[j + 1:]


class Solution:

	def rearrange(self, arr, n):
		if n == 1:
			return arr
		arrp = []
		arrn = []
		for i in range(n):
			if arr[i] > -1:
				arrp.append(arr[i])
			else:
				arrn.append(arr[i])
		arr.clear()
		i = 0
		while i < len(arrp) and i < len(arrn):
			arr.append(arrp[i])
			arr.append(arrn[i])
			i += 1
		while i < len(arrp):
			arr.append(arrp[i])
			i += 1
		while i < len(arrn):
			arr.append(arrn[i])
			i += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		poss_arr = []
		neg_arr = []
		for i in arr:
			if i >= 0:
				poss_arr.append(i)
			else:
				neg_arr.append(i)
		i = 0
		j = 0
		new_arr = []
		while i < len(poss_arr) and j < len(neg_arr):
			new_arr.append(poss_arr[i])
			i += 1
			new_arr.append(neg_arr[j])
			j += 1
		if i < len(poss_arr):
			new_arr.extend(poss_arr[i:])
		if j < len(neg_arr):
			new_arr.extend(neg_arr[j:])
		arr[:] = list(new_arr)


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		x = 0
		y = 0
		z = 0
		for i in range(n):
			if z == 0:
				if x < len(pos):
					arr[i] = pos[x]
					x += 1
					z = 1
				else:
					arr[i] = neg[y]
					y += 1
					z = 1
			elif y < len(neg):
				arr[i] = neg[y]
				y += 1
				z = 0
			else:
				arr[i] = pos[x]
				x += 1
				z = 0


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in range(n):
			if arr[i] >= 0:
				pos.append(arr[i])
			else:
				neg.append(arr[i])
		j = 0
		p = 0
		ne = 0
		while j < n:
			if j % 2 != 0:
				if ne >= len(neg) and p < len(pos):
					arr[j] = pos[p]
					p += 1
					j += 1
				else:
					arr[j] = neg[ne]
					ne += 1
					j += 1
			elif p >= len(pos) and ne < len(neg):
				arr[j] = neg[ne]
				ne += 1
				j += 1
			else:
				arr[j] = pos[p]
				p += 1
				j += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		for i in arr:
			if i >= 0:
				pos.append(i)
			else:
				neg.append(i)
		j = 0
		k = 0
		if pos == [] or neg == []:
			return arr
		for i in range(n):
			if (i % 2 == 0 or k >= len(neg)) and j < len(pos):
				arr[i] = pos[j]
				j += 1
			else:
				arr[i] = neg[k]
				k += 1
		return arr


class Solution:

	def rearrange(self, arr, n):
		pos = []
		neg = []
		res = []
		for el in arr:
			if el >= 0:
				pos.append(el)
			else:
				neg.append(el)
		if len(pos) >= len(neg):
			for i in range(len(neg)):
				res.append(pos[i])
				res.append(neg[i])
			res.extend(pos[len(neg):])
		else:
			for i in range(len(pos)):
				res.append(pos[i])
				res.append(neg[i])
			res.extend(neg[len(pos):])
		arr.clear()
		arr.extend(res[0:])
		return arr


class Solution:

	def rearrange(self, arr, n):
		neg = [i for i in arr if i < 0]
		pos = [i for i in arr if i >= 0]
		n = min(len(pos), len(neg))
		arr.clear()
		for i in range(n):
			arr.append(pos[i])
			arr.append(neg[i])
		if len(pos) > n:
			arr.extend(pos[n:])
		elif len(neg) > n:
			arr.extend(neg[n:])


class Solution:

	def rearrange(self, arr, n):
		p = []
		ng = []
		for i in arr:
			if i < 0:
				ng.append(i)
			else:
				p.append(i)
		i = 0
		j = 0
		res = []
		if len(p) == 0 or len(ng) == 0:
			return
		else:
			while i < len(p) and j < len(ng):
				res.append(p[i])
				i = i + 1
				res.append(ng[j])
				j = j + 1
			while i < len(p):
				res.append(p[i])
				i = i + 1
			while j < len(ng):
				res.append(ng[j])
				j = j + 1
			arr[:] = res[:]