Remove the balls

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Remove balls in pairs of same color, count remaining. Stack-based simulation.

Algorithm

1Stack: push ball. If top equals current: pop (they cancel). Count remaining stack size.

Common Pitfalls

•Similar to LC 1047 (remove all adjacent duplicates). Stack simulation O(n). Final stack size is answer.

Remove the balls.java

Java

// Approach: Stack simulation. Push colored balls; pop when top matches current color, otherwise push.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int findLength(int[] color, int[] radius) {
        int n = color.length;
        Stack<Pair> st = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (!st.isEmpty() && st.peek().col == color[i] && st.peek().rad == radius[i])
                st.pop();
            else
                st.push(new Pair(color[i], radius[i]));
        }

        return st.size();
    }

    class Pair {
        int col;
        int rad;

        public Pair(int col, int rad) {
            this.col = col;
            this.rad = rad;
        }
    }
}

Was this solution helpful?