Remove the balls

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Remove balls in pairs of same color, count remaining.

See our study guide for structured GFG and LeetCode practice.

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?