Opposite Sign Pair Reduction

Time: O(n)

Space: O(n)

Intuition

Use a stack to represent the already-reduced prefix. When a new value arrives, only the stack top can interact with it first if signs are opposite. Resolve that conflict by absolute values, and keep going until either the incoming value is destroyed or no more opposite-sign top exists.

Algorithm

1Initialize an empty stack.
2For each value x in the array, repeatedly compare with stack top while signs are opposite.
3If |x| > |top|, pop top and continue (x may collide again).
4If |x| < |top|, x is destroyed (stop processing current x).
5If |x| == |top|, pop top and destroy x (both removed).
6If x survives all collisions, push x into stack.
7At the end, stack content (bottom to top) is the reduced array.

Example Walkthrough

Input: arr = [5, 10, -5, -20, 7]

1.Push 5, push 10. Stack: [5, 10].
2.x = -5 collides with 10. |10| > |5|, so -5 is removed. Stack unchanged.
3.x = -20 collides with 10, then 5. Since |-20| is larger, both get popped. Push -20. Stack: [-20].
4.x = 7 collides with -20. |-20| > |7|, so 7 is removed.
5.Final stack is [-20].

Output: [-20]

Common Pitfalls

•Do not compare non-adjacent elements directly; collision order is strictly with current stack top.
•Continue the while-loop after popping weaker top values; one element can trigger multiple removals.
•Handle equal magnitudes correctly: both elements must be removed.

Opposite Sign Pair Reduction.java

Java


import java.util.*;

class Solution {
    // Approach: Stack-based collision simulation on opposite-sign adjacent survivors.
    // Time: O(n) Space: O(n)

    public ArrayList<Integer> reducePairs(int[] arr) {
        Stack<Integer> st = new Stack<>();
        ArrayList<Integer> ans = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            int x = arr[i];
            boolean p = true;
            while (!st.isEmpty() && ((st.peek() < 0 && x > 0) || (st.peek() > 0 && x < 0))) {
                int a = Math.abs(x);
                int b = Math.abs(st.peek());
                if (a > b) {
                    st.pop();
                } else if (b > a) {
                    x = st.peek();
                    st.pop();
                } else {
                    st.pop();
                    p = false;
                    break;
                }
            }
            if (p) {
                st.push(x);
            }
        }

        while (!st.isEmpty()) {
            ans.add(st.peek());
            st.pop();

        }

        Collections.reverse(ans);

        return ans;
    }
}

Was this solution helpful?