Opening and Closing Gates Validation Algorithm

The opening-and-closing-gates problem asks one question: given a sequence of gate events, is every open matched by a corresponding close in the correct order?

Problem Statement

A water-reservation system uses gates to control flow. Each gate event is either an opening ( or a closing ). People downstream are safe only if:

• Every opening gate eventually gets a matching closing gate.
• No closing gate appears before an unmatched opening gate precedes it.
• At the end of the sequence, zero gates remain open.

If all conditions hold, return the number of valid open-close pairs. Otherwise return -1.

This is the balanced-parentheses problem dressed in a real-world scenario. The algorithm is identical.

Core Insight: Balanced Parentheses

Map every gate event to a bracket:

• Opening gate = (
• Closing gate = )

Validity reduces to two invariants:

• Prefix invariant: at every position in the string, the count of opens seen so far is greater than or equal to the count of closes. A violation means a gate closed before any gate was open.
• Terminal invariant: at the end, opens equal closes. A violation means some gate was left open.

A single integer counter tracks the difference (opens minus closes). It starts at 0, increments on (, decrements on ). If it ever drops below 0, return -1 immediately. If it is non-zero at the end, return -1. Otherwise, the total valid pairs equal half the string length (since each pair consumes two characters).

Algorithm: Counter Approach

• Initialise counter = 0 and pairs = 0.
• For each character in the input:
  • If (: increment counter.
  • If ): check if counter > 0. If yes, decrement counter and increment pairs. If no, return -1.
• After the loop, if counter == 0, return pairs. Otherwise return -1.

This runs in O(n) time and O(1) space.

Python Implementation

def validate_gates(gates: str) -> int:
    """Return count of valid gate pairs, or -1 if unbalanced."""
    counter = 0
    pairs = 0

    for ch in gates:
        if ch == '(':
            counter += 1
        elif ch == ')':
            if counter > 0:
                counter -= 1
                pairs += 1
            else:
                return -1

    return pairs if counter == 0 else -1

Test it against a few inputs:

• validate_gates("()()") returns 2
• validate_gates("(()") returns -1 (one gate left open)
• validate_gates(")(") returns -1 (close before any open)
• validate_gates("") returns 0 (trivially balanced)

Python’s list-as-stack approach works too, but for single-type brackets, the counter is simpler and avoids the O(n) memory overhead. If you are building a collection of solved Python programs for revision, the Python basic programs reference covers a broad set of patterns including loops, conditionals, and string manipulation that pair well with this exercise.

C++ Implementation

#include <iostream>
#include <string>

int validateGates(const std::string& gates) {
    int counter = 0;
    int pairs = 0;

    for (char ch : gates) {
        if (ch == '(') {
            counter++;
        } else if (ch == ')') {
            if (counter > 0) {
                counter--;
                pairs++;
            } else {
                return -1;
            }
        }
    }

    return (counter == 0) ? pairs : -1;
}

int main() {
    std::string test1 = "(())()";
    std::cout << validateGates(test1) << std::endl;  // Output: 3

    std::string test2 = "())";
    std::cout << validateGates(test2) << std::endl;  // Output: -1

    return 0;
}

The logic mirrors the Python version character-for-character. Both compile to the same O(n) scan with a single integer of state. The same incremental-state technique applies to expression evaluation problems like building a calculator program in Python where operators and operands must pair correctly.

Edge Cases and Testing

Input	Expected Output	Reason
""	0	Empty string, trivially balanced
"()"	1	Single valid pair
"(((("	-1	All opens, no closes
"))))"	-1	Close before any open (fails at first char)
")("	-1	Close appears before a matching open
"(())()"	3	Nested + sequential, all matched
"(()()"	-1	3 opens but only 2 closes

Each test case exercises a distinct failure path or success condition. For placement coding rounds, demonstrating awareness of these edge cases often matters as much as the core logic. The character-by-character inspection here is the same pattern used in character classification problems where you route logic based on input type.

Time and Space Complexity

Approach	Time	Space	When to Use
Counter	O(n)	O(1)	Single bracket type (this problem)
Stack	O(n)	O(n)	Multiple bracket types or index tracking needed

Both approaches make exactly one pass over the input. The counter is strictly better for single-type matching because it avoids allocating a data structure entirely. In placement interviews, mention both and explain why you chose the counter for this specific problem. It signals you understand the trade-off rather than defaulting to the textbook stack solution every time a bracket-matching problem appears on screen.

From Bracket Matching to Parsing in AI Systems

The counter-based scan above is the simplest form of a parser: read tokens left to right, maintain state, reject on violation. Tokenisers inside large language models use the same structural idea at a more complex scale, matching opening and closing delimiters across context windows of thousands of tokens. If the shift from placement-style bracket problems to understanding how parsers work inside AI systems interests you, TinkerLLM (starting at ₹299) lets you experiment with tokenisation, prompt structure, and model behaviour hands-on. The counter logic you just wrote is the conceptual ancestor of the delimiter-matching that keeps LLM outputs syntactically valid.