Make the array beautiful

Time: O(n)

Space: O(n)

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?