# Reduce Array by replacing adjacent opposite sign pairs with their absolute maximum

Given an array arr[] of size Nthe task is to find the final array by repeatedly performing the following operations if two elements of opposite signs are adjacent:

• Remove both opposite signed elements from the array and insert the element having maximum absolute value along with its sign.
• If both the elements have the same absolute value, both will be removed from the array.

Examples:

Input: arr[] = {10, -5, -8, 2, -5}
Output: 10
Explaination:
At Index 0 : Elemment 10 has positive sign.
At Index 1 : -5 has lesser absolute value than 10. Replace both of them with 10.
At Index 2 : -8 has lesser absolute value than 10. Replace both of them with 10.
At Index 3 : 2 has postive sign. So it will be in the array.
At Index 4 : -5 has greater absolute value than 2. Replace both of them with 5.
Now -5 has lesser absolute value than 10. Replace both of them with 10.

Input: arr[] = {5, -5, -2, -10}
Output: -2 -10
Explaination: 1st and 2nd element gets discarded because
Both elements have the same values ​​but opposite sign.
3rd and 4th elements have the same sign. So both will be in the array.

Approach: The problem can be solved by using the following idea:

At any moment the previous elements can also be required, so a stack data structure can be used to hold the elements, and smaller elements can be popped efficiently from the stack due to its last-in-first-out property.

Look at the below illustration for a better understanding:

Consider array arr[] = {10, -5, -8, 2, -5}.

Initially stack is empty, st = { }

At 0th index:
=> arr = 10
=> st = {}
=> Push 10 into the stack
=> The stack is st = {10}

At 1st index:
=> arr = -5
=> st = {10}
=> The top most element of stack is positive and arr is negative.
=> As arr has lesser absolute value ie 5 than top most element of stack so no changes in stack.
=> The stack is st = {10}

At 2nd index:
=> arr = -8
=> st = {10}
=> The top most element of stack is positive and arr is negative.
=> As arr has lesser absolute value ie 8 than top most element of stack so no changes in stack.
=> The stack is st = {10}

At 3rd index:
=> arr = 2
=> The top most element of stack is positive and arr is also positive.
=> Push 2 in the stack.
=> The stack is st = {10, 2}

At 4th index:
=> arr = -5
=> st = {10, 2}
=> The top most element of stack is positive and arr is negative.
=> As arr has greater absolute value ie 5 than top most element of stack, pop the top most element of stack.
=> The stack changes from st = {10, 2} to st = {10}
=> Now again, the top most element of stack is positive and arr is negative.
=> arr has lesser absolute value ie 5 than top most element. So no changes in stack.
=> The stack remains st = {10}

The elements finally remaining in the stack are the final elements of the array.

So the elements remaining in the array are arr = {10}

Follow the steps mentioned below to implement the approach:

• Declare a stack to hold the array elements.
• Traverse the array, If the element is positive, directly push onto the stack.
• Else if current arr[i] is negative, then
• Try popping all the smaller elements from the stack which are positivestating that the element having smaller absolute value has been discarded.
• If the current element and top of the stack are equal and the top of the stack is positive then pop from the stack, stating that both elements with equal values ​​but the opposite sign has been discarded.
• Lastly, If the stack is empty or the last element is negative, then push the current arr[i] element on the stack. As all remaining elements will have a negative sign.
• Finally, return the stack, showing the remaining elements.

Below is the implementation of the above approach:

## Python3

 ` ` `class` `Solution:` `    ` `    ``def` `solve(``self``, arr):` ` ` `        ` `        ``stack ``=` `[]` ` ` `        ` `        ``for` `element ``in` `arr:` ` ` `            ` `            ` `            ``if` `(element >``=` `0``):` `                ``stack.append(element)` ` ` `            ``else``:` `                ` `                ` `                ``while``(stack ``and` `stack[``-``1``] >``=` `0` `                      ``and` `abs``(element) > stack[``-``1``]):` `                    ``stack.pop()` ` ` `                ` `                ` `                ` `                ``if` `(stack ``and` `stack[``-``1``] >``=` `0` `                    ``and` `stack[``-``1``] ``=``=` `abs``(element)):` `                    ``stack.pop()` ` ` `                ` `                ` `                ` `                ``elif``(``len``(stack) ``=``=` `0` `                     ``or` `stack[``-``1``] < ``0``):` `                    ``stack.append(element)` ` ` `        ` `        ``return` `stack` ` ` `if` `__name__ ``=``=` `'__main__'``:` `    ``obj ``=` `Solution()` `    ``arr ``=` `[``5``, ``-``5``, ``-``2``, ``-``10``]` `    ``ans ``=` `obj.solve(arr)` `    ``for` `x ``in` `ans:` `        ``print``(x, end ``=` `" "``)`

Time Complexity: O(N)
Auxiliary Space: O(N)