Opposite Sign Pair Reduction

Problem Summary

You’re given an array of integers (positive + negative).

You repeatedly:

• Look at adjacent elements

• If they have opposite signs, you:

  • Compare absolute values

  • Keep the stronger one (or remove both if equal)

Continue until no more operations can be done.

Key Insight

This behaves exactly like a collision problem (similar to asteroid collision 🚀).

Why stack?
Because:

• Every new element interacts only with the previous one

• After resolving, the result may again interact with earlier elements

Core Idea (Stack Approach)

We process elements one by one:

Rules:

Let:

top = stack.peek()
curr = current element

If signs are opposite:

• abs(top) > abs(curr) → keep top

• abs(top) < abs(curr) → remove top, continue checking

• abs(top) == abs(curr) → remove both

If signs are same:

• Just push

Example Walkthrough

Input:

arr = [10, -5, -8, 2, -5]

Step-by-step:

• Step: 10
  Stack: [10]
  Action: push

• Step: -5
  Stack: [10]
  Action: 10 vs -5 → 10 wins

• Step: -8
  Stack: [10]
  Action: 10 vs -8 → 10 wins

• Step: 2
  Stack: [10, 2]
  Action: same sign → push

• Step: -5
  Stack: [10, 5]
  Action: 2 vs -5 → 5 wins

• Stack: [10]
  Action: 10 vs -5 → 10 wins

Output:

[10]

Another Example

arr = [5, -5, -2, -10]

• 5 & -5 → equal → both removed

• remaining → [-2, -10]

Output:

[-2, -10]

Algorithm

• Create an empty stack

• Traverse array:

  • Try resolving with stack top if opposite signs

  • Keep resolving until:

    • no conflict OR stack empty

  • Push remaining element if needed

• Convert stack → result

Java Code

import java.util.*;

class Solution {
    public ArrayList<Integer> reducePairs(int[] arr) {
        Stack<Integer> stack = new Stack<>();

        for (int num : arr) {
            boolean removed = false;

            while (!stack.isEmpty() && stack.peek() * num < 0) {
                int top = stack.peek();

                if (Math.abs(top) > Math.abs(num)) {
                    removed = true;
                    break;
                } 
                else if (Math.abs(top) < Math.abs(num)) {
                    stack.pop();
                } 
                else {
                    stack.pop();
                    removed = true;
                    break;
                }
            }

            if (!removed) {
                stack.push(num);
            }
        }

        return new ArrayList<>(stack);
    }
}

Complexity

• Time Complexity: O(n)
  Each element is pushed/popped at most once

• Space Complexity: O(n)
  Stack used

Key Takeaways

• This is a stack + simulation problem

• Think of it like collisions

• Always compare with the previous surviving element

Same pattern appears in:

• Asteroid collision problems

• Expression reduction

• Adjacent elimination problems