Print Bracket Number

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Number each bracket pair: opening bracket gets number, closing bracket gets matching number. Stack.

Algorithm

1counter=0, stack. On open bracket: push ++counter, print counter. On close: print top, pop.

Common Pitfalls

•Simple stack simulation. O(n). Track counter for numbering and stack for matching.

Print Bracket Number.java

Java

// Approach: Stack-based. Assign incrementing numbers to opening brackets; use stack to match closing brackets.
// Time: O(n) Space: O(n)
import java.util.ArrayList;

class Solution {
    ArrayList<Integer> bracketNumbers(String str) {
        ArrayList<Integer> ans = new ArrayList<>();
        numbers(str, ans);
        return ans;
    }

    static void numbers(String str, ArrayList<Integer> ans) {
        ArrayList<Integer> opens = new ArrayList<>();
        int n = str.length();
        int open = 0;
        int close = 0;
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) == '(') {
                open++;
                opens.add(open);
                ans.add(open);
            } else if (str.charAt(i) == ')') {
                close = opens.get(opens.size() - 1);
                ans.add(close);
                opens.remove(opens.size() - 1);
            }
        }
    }
};

Was this solution helpful?