Make the array beautiful

Time: O(n)

Space: O(n)

Problem Overview

Two adjacent numbers with opposite signs can "cancel" each other out, leaving fewer elements.

Intuition

Two adjacent numbers with opposite signs can "cancel" each other out, leaving fewer elements. A stack naturally tracks which elements remain after each cancellation, and we process left-to-right to handle cascading cancellations.

Algorithm

1Create an empty stack.
2For each number in the array:
3 If stack is empty, push the number.
4 If number and stack top have opposite signs (one =0, one <0), pop the stack (cancel).
5 Otherwise, push the number onto the stack.
6Pop all elements from the stack into a result list (this reverses order).
7Reverse the result list to restore original order.
8Return the result list.

Example Walkthrough

Input: arr = [6, -3, 9, 7]

1. Push 6. Stack: [6].
2. Next -3: opposite sign to 6, pop 6. Stack: [].
3. Push 9. Stack: [9].
4. Push 7. Stack: [9, 7].
5. Pop to result: [7, 9]. Reverse: [9, 7].

Output: [9, 7]

Common Pitfalls

• Sign check must use =0 and <0, not > and <, to handle 0 correctly (0 cancels with both positive and negative).
• Remember to reverse the result at the end; popping from a stack inverts order.
• Check for empty stack before peeking; an empty stack means no cancellation applies.

Make the array beautiful.java

Java


import java.util.*;

// Approach: Stack-based sign elimination. If current number has opposite sign from stack top, pop (cancel).
// Otherwise, push current number. At the end, reverse the stack to restore original order.
// Time: O(n) Space: O(n)

class Solution {

    List<Integer> makeBeautiful(int[] arr) {
        // Create a stack to store the integers
        Stack<Integer> stack = new Stack<>();

        // Iterate over the input array
        for (int num : arr) {
            // If the stack is empty, push the integer onto the stack
            if (stack.empty()) {
                stack.push(num);
            } else {
                // If the integer has a different sign than the top of the stack, pop the top element
                if ((stack.peek() >= 0 && num < 0) || (stack.peek() < 0 && num >= 0)) {
                    stack.pop();
                } else {
                    // Otherwise, push the integer onto the stack
                    stack.push(num);
                }
            }
        }

        // Create a new ArrayList to store the result
        ArrayList<Integer> result = new ArrayList<>();

        // Pop the elements from the stack and add them to the result ArrayList
        while (!stack.empty()) {
            result.add(stack.peek());
            stack.pop();
        }

        // Reverse the order of the elements in the result ArrayList
        Collections.reverse(result);

        // Return the result ArrayList
        return result;
    }
}

Was this solution helpful?