Equal Point in Brackets

Time: O(n)

Space: O(1)

Intuition

The equal point is a split position where the number of opening brackets before the split equals the number of closing brackets after the split. Instead of recomputing both sides for every index, count all closing brackets once, then move the split from left to right. When the split passes an opening bracket, the left-open count increases; when it passes a closing bracket, the right-close count decreases.

Algorithm

1Count the total number of closing brackets in the string and store it as close.
2Initialize open = 0.
3For each split index i from 0 to n inclusive, first check whether open == close.
4If the counts match, return i as the equal point.
5If i is still inside the string, consume s[i]: increment open for an opening bracket, otherwise decrement close for a closing bracket.
6If no split matches, return -1.
7Time Complexity: O(n), because the string is scanned once to count closings and once to move the split.
8Space Complexity: O(1), because only counters are stored.

Example Walkthrough

Input: s = "(()))("

1.Initially open = 0 and close = 3 because the string has three closing brackets.
2.At split 0, counts are 0 and 3, so they do not match. Pass character 0: open becomes 1.
3.At split 1, counts are 1 and 3. Pass character 1: open becomes 2.
4.At split 2, counts are 2 and 3. Pass character 2, which is a closing bracket, so close becomes 2.
5.At split 3, open == close == 2, so the equal point is 3.

Output: 3

Common Pitfalls

•Check the split before consuming s[i]; index i represents the boundary before character i.
•Include split n, the position after the last character.
•Closing brackets on the left should be removed from the right-close count when the split passes them.

Equal Point in Brackets.java

Java

// Approach: Count all closing brackets first, then scan every split index while tracking
// openings on the left and closings remaining on the right. The first index where both
// counts match is the required equal point.
// Time: O(n) Space: O(1)

class Solution {

    public int findIndex(String s) {
        int n = s.length();

        int open = 0, close = 0;
        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                close++;
            }
        }

        for (int i = 0; i <= n; i++) {
            if (open == close) {
                return i;
            }

            if (i < n) {
                if (s.charAt(i) == '(') {
                    open++;
                } else {
                    close--;
                }
            }
        }
        return -1;
    }
}

Was this solution helpful?