Given an array of negative and non-negative integers. You have to make the array beautiful. An array is beautiful if two adjacent integers, arr[i] and arr[i+1] are either negative or non-negative. And you can do the following operation any number of times until the array becomes beautiful.
	If two adjacent integers are different i.e. one of them is negative and other is non-negative, remove them.
Return the beautiful array after performing the above operation.
Note:An empty array is also a beautiful array. There can be many adjacent integers which are different as stated above. So remove different adjacent integers as described above from left to right.
Example 1:
Input: 4 2 -2 1
Output: 4 1
Explanation: As at indices 1 and 2 , 2 and -2 have
different sign, they are removed. And the  the final
array is: 4 1.
Example 2:
Input: 2 -2 1 -1
Output: []
Explanation: As at indices 0 and 1, 2 and -2 have
different sign, so they are removed. Now the array
is 1 -1.Now 1 and -1 are also removed as they have
different sign. So the final array is empty. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function makeBeautiful() which takes an array as an input parameter and returns an array.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 <= size of the array <= 10^{5}
-10^{5} <= arr[i] <= 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



from typing import List



class Solution:

    def makeBeautiful(self, arr: List[int]) -> List[int]:

        # code here

Solutions:
from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		st = []
		st.append(arr[0])
		for i in arr[1:]:
			if len(st) == 0:
				st.append(i)
			elif st[-1] >= 0 and i >= 0 or (st[-1] < 0 and i < 0):
				st.append(i)
			elif st and (st[-1] >= 0 and i < 0 or (st[-1] < 0 and i >= 0)):
				st.pop()
		return st


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		stack = []
		for i in range(len(arr)):
			if len(stack) == 0:
				stack.append(arr[i])
			elif stack[-1] < 0:
				if arr[i] >= 0:
					stack.pop()
				else:
					stack.append(arr[i])
			elif arr[i] < 0:
				stack.pop()
			else:
				stack.append(arr[i])
		return stack


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		if len(arr) == 1:
			return arr
		i = 0
		while i < len(arr) - 1 and len(arr) > 1:
			if arr[i] < 0 and arr[i + 1] < 0 or (arr[i] >= 0 and arr[i + 1] >= 0):
				i += 1
			else:
				arr.pop(i)
				arr.pop(i)
				if i > 0:
					i -= 1
		return arr


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		beautiful_array = [arr[0]]
		ptr = 0
		for i in range(1, len(arr)):
			if len(beautiful_array) == 0:
				beautiful_array.append(arr[i])
				ptr = 0
				continue
			if arr[i] >= 0 and beautiful_array[ptr] >= 0 or (arr[i] < 0 and beautiful_array[ptr] < 0):
				beautiful_array.append(arr[i])
				if len(beautiful_array) == 1:
					ptr = 0
				else:
					ptr = ptr + 1
			else:
				beautiful_array = beautiful_array[:-1]
				ptr = ptr - 1
		return beautiful_array


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		n = len(arr)
		beautiful = []
		top = -1
		beautiful.append(arr[0])
		top += 1
		for i in range(1, n):
			if len(beautiful) >= 1:
				if arr[i] >= 0 and beautiful[top] < 0 or (arr[i] < 0 and beautiful[top] >= 0):
					beautiful.pop()
					top = top - 1
				else:
					top += 1
					beautiful.append(arr[i])
			elif len(beautiful) == 0:
				top += 1
				beautiful.append(arr[i])
		if n == 1:
			return arr
		return beautiful


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		result = []
		for a in arr:
			if len(result) == 0:
				result.append(a)
				continue
			next_is_nonnegative = a >= 0
			cur_is_nonnegative = result[-1] >= 0
			if cur_is_nonnegative == next_is_nonnegative:
				result.append(a)
			else:
				result.pop()
		return result


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		oppositeSigns = lambda x, y: x ^ y < 0
		if len(arr) > 0:
			i = 1
			while i < len(arr):
				if oppositeSigns(arr[i], arr[i - 1]):
					arr.pop(i - 1)
					arr.pop(i - 1)
					if i != 1:
						i = i - 1
				else:
					i = i + 1
		return arr


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		stack = []
		for ele in arr:
			if len(stack) == 0:
				stack.append(ele)
			elif stack[-1] >= 0 and ele > 0:
				stack.append(ele)
			elif stack[-1] >= 0 and ele < 0 or (stack[-1] < 0 and ele >= 0):
				stack.pop()
			else:
				stack.append(ele)
		return stack


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		stack = []
		left = []
		for i in arr:
			if not stack:
				stack.append(i)
			elif stack and (stack[-1] >= 0 and i < 0 or (stack[-1] < 0 and i >= 0)):
				stack.pop()
			else:
				stack.append(i)
		return stack


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		i = len(arr) - 2
		arr.reverse()
		while i >= 0:
			if i >= len(arr) - 1:
				i = len(arr) - 2
			elif arr[i] < 0 and arr[i + 1] >= 0:
				arr.pop(i)
				arr.pop(i)
			elif arr[i] >= 0 and arr[i + 1] < 0:
				arr.pop(i)
				arr.pop(i)
			else:
				i -= 1
		arr.reverse()
		return arr


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		st = []
		for i in arr:
			if not st:
				st.append(i)
				continue
			if st[-1] >= 0 and i < 0 or (st[-1] < 0 and i >= 0):
				st.pop()
			else:
				st.append(i)
		return st


from typing import List

def sol(a):
	n = len(a)
	stack = [a[0]]
	for i in range(1, n):
		if stack and (a[i] < 0) ^ (stack[-1] < 0):
			stack.pop()
		else:
			stack.append(a[i])
	return stack

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		return sol(arr)


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		arr2 = []
		arr2.append(arr[0])
		top = 0
		for i in range(1, len(arr)):
			if top == -1:
				arr2.append(arr[i])
				top += 1
			elif arr2[top] < 0 and arr[i] >= 0:
				arr2.pop()
				top -= 1
			elif arr2[top] >= 0 and arr[i] < 0:
				arr2.pop()
				top -= 1
			else:
				arr2.append(arr[i])
				top += 1
		return arr2
ob = Solution()


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		s = []
		if len(arr) == 0:
			return arr
		s.append(arr[0])
		for i in range(1, len(arr)):
			if s:
				if s[-1] < 0 and arr[i] > 0 or (s[-1] > 0 and arr[i] < 0) or (s[-1] < 0 and arr[i] == 0) or (s[-1] == 0 and arr[i] < 0):
					s.pop()
				else:
					s.append(arr[i])
			else:
				s.append(arr[i])
		return s


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:

		def check(a, b):
			return a < 0 and b >= 0 or (a >= 0 and b < 0)
		st = []
		for i in range(len(arr)):
			if len(st) > 0 and check(st[-1], arr[i]):
				st.pop()
			else:
				st.append(arr[i])
		return st


from typing import List

class Solution:

	def sign(self, n):
		return (n >= 0) - (n < 0)

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		stk = []
		for i in arr:
			if stk and self.sign(stk[-1]) != self.sign(i):
				stk.pop()
			else:
				stk.append(i)
		return stk


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		n = len(arr)
		stack = []
		for i in range(n):
			flag = 0
			if stack and stack[-1] * arr[i] < 0:
				flag = 1
				stack.pop()
			elif stack and stack[-1] * arr[i] == 0 and (min(stack[-1], arr[i]) < 0):
				flag = 1
				stack.pop()
			if not flag:
				stack.append(arr[i])
		return stack


import numpy as np
from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		ni = 0
		while ni < len(arr) - 1:
			if np.sign(1 if arr[ni] == 0 else arr[ni]) != np.sign(1 if arr[ni + 1] == 0 else arr[ni + 1]):
				del arr[ni + 1]
				del arr[ni]
				ni = max(ni - 1, 0)
			else:
				ni = ni + 1
		return arr


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		result = []
		i = 0
		n = len(arr)
		while i < n:
			if len(result) == 0:
				result.append(arr[i])
			elif result[len(result) - 1] >= 0 and arr[i] < 0 or (result[len(result) - 1] < 0 and arr[i] >= 0):
				result.pop()
			else:
				result.append(arr[i])
			i += 1
		return result


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		l = []
		if len(arr) == 1:
			return arr
		d = 1
		while d == 1:
			if len(l) > 2:
				for i in range(0, len(l) - 1):
					if arr[i] < 0 and arr[i + 1] > 0 or (arr[i] > 0 and arr[i + 1] < 0):
						d = 1
						break
				else:
					d = 0
			else:
				d = 0
			for i in range(len(arr)):
				if len(l) != 0:
					if l[-1] >= 0 and arr[i] < 0:
						l.pop()
					elif l[-1] < 0 and arr[i] >= 0:
						l.pop()
					else:
						l.append(arr[i])
				else:
					l.append(arr[i])
		return l


from typing import List

class Solution:

	def makeBeautiful(self, arr: List[int]) -> List[int]:
		l = [arr[0]]
		for i in arr[1:]:
			if len(l) == 0:
				l.append(i)
				continue
			if l[-1] >= 0 and i >= 0:
				l.append(i)
			elif l[-1] < 0 and i < 0:
				l.append(i)
			else:
				del l[-1]
		return l