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[0] = 10
=> st = {}
=> Push 10 into the stack
=> The stack is st = {10}

At 1st index:
=> arr[1] = -5
=> st = {10}
=> The top most element of stack is positive and arr[1] is negative.
=> As arr[1] 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[2] = -8
=> st = {10}
=> The top most element of stack is positive and arr[2] is negative.
=> As arr[2] 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[3] = 2
=> The top most element of stack is positive and arr[3] is also positive.
=> Push 2 in the stack.
=> The stack is st = {10, 2}

At 4th index:
=> arr[4] = -5
=> st = {10, 2}
=> The top most element of stack is positive and arr[4] is negative.
=> As arr[4] 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[4] is negative.
=> arr[4] 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)

Leave a Comment