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