Solving Valid Parentheses in Go: Step-by-Step Guide

Introduction to Valid Parentheses

The Valid Parentheses problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. The problem statement is deceptively simple: given a string containing only the characters (, ), {, }, [, and ], determine if the input string is valid. A string is considered valid when every opening bracket has a corresponding closing bracket of the same type, and the brackets are closed in the correct order.

In this tutorial, we will walk through solving this problem using the Go programming language. We will cover the underlying data structure, the algorithm, a complete implementation, edge cases, complexity analysis, and best practices to keep in mind when writing production-ready Go code.

Why This Problem Matters

At first glance, validating parentheses might seem like a trivial exercise. However, this problem is foundational because it teaches several critical concepts that appear repeatedly in real-world software engineering:

• Stack data structure: The problem is the canonical example of when to use a stack, reinforcing Last-In-First-Out (LIFO) thinking.
• Compiler design: Parsers and lexers use bracket matching to validate syntax in programming languages, JSON, XML, and HTML.
• Expression evaluation: Mathematical expressions and code editors rely on balanced delimiters to detect malformed input.
• Interview readiness: It is one of the most frequently asked questions at companies like Amazon, Google, and Microsoft because it tests both data structure knowledge and attention to edge cases.

Mastering this problem gives you a mental model you can apply to more complex parsing and validation tasks.

Understanding the Problem

Before writing any code, let us clearly define what makes a string valid. Consider the following examples:

• "()" — valid, each opening parenthesis has a matching closing one.
• "()[]{}" — valid, multiple pairs in sequence.
• "(]" — invalid, mismatched bracket types.
• "([)]" — invalid, brackets are not closed in the correct order.
• "{[]}" — valid, nested brackets closed in proper order.
• "" — valid, an empty string is trivially balanced.
• "(" — invalid, an unclosed opening bracket.

The key insight is that the most recently opened bracket must be the first one closed. This Last-In-First-Out behavior is exactly what a stack provides.

The Algorithm: Stack-Based Approach

The algorithm can be summarized in a few clear steps:

• Initialize an empty stack to hold opening brackets.
• Iterate through each character in the string.
• If the character is an opening bracket ((, {, [), push it onto the stack.
• If the character is a closing bracket (), }, ]), check the top of the stack. If the stack is empty or the top does not match the corresponding opening bracket, return false. Otherwise, pop the top element.
• After processing all characters, return true only if the stack is empty (no unclosed brackets remain).

This approach guarantees that we validate both the matching type and the correct nesting order.

Implementing the Solution in Go

Go does not have a built-in generic stack type in its standard library, but we can easily simulate one using a slice. Slices in Go are dynamic arrays that allow efficient append and pop operations from the end, which is perfect for stack behavior.

Basic Implementation

Here is a clean, readable implementation of the Valid Parentheses solution:

package main

import "fmt"

func isValid(s string) bool {
    // Map closing brackets to their corresponding opening brackets
    matching := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    // Use a slice as a stack
    stack := []rune{}

    for _, char := range s {
        // If it is a closing bracket
        if open, isClosing := matching[char]; isClosing {
            // Stack must not be empty and top must match
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            // Pop from the stack
            stack = stack[:len(stack)-1]
        } else {
            // It is an opening bracket, push onto stack
            stack = append(stack, char)
        }
    }

    // Valid only if stack is empty
    return len(stack) == 0
}

func main() {
    testCases := []string{
        "()",
        "()[]{}",
        "(]",
        "([)]",
        "{[]}",
        "",
        "(",
        "((()))",
        "((())",
    }

    for _, tc := range testCases {
        fmt.Printf("isValid(%q) = %v\n", tc, isValid(tc))
    }
}

When you run this program, you should see output confirming which strings are valid and which are not. The use of rune instead of byte ensures that the code handles Unicode characters correctly, even though the problem only involves ASCII brackets.

How the Code Works

Let us trace through the input "{[]}" to understand the flow:

• Character { is an opening bracket. Stack becomes ['{'].
• Character [ is an opening bracket. Stack becomes ['{', '['].
• Character ] is a closing bracket. Top of stack is '[', which matches. Pop it. Stack becomes ['{'].
• Character } is a closing bracket. Top of stack is '{', which matches. Pop it. Stack becomes [].
• Loop ends. Stack is empty, so return true.

Now consider the invalid input "([)]":

• Character ( pushed. Stack: ['('].
• Character [ pushed. Stack: ['(', '['].
• Character ) is closing. Top of stack is '[', but we expected '('. Mismatch detected, return false immediately.

Complexity Analysis

Understanding the performance characteristics of your solution is essential, especially in interview settings.

• Time Complexity: O(n) — We iterate through the string exactly once, and each push and pop operation on the slice-based stack takes O(1) amortized time.
• Space Complexity: O(n) — In the worst case, such as the input "(((((", every character is an opening bracket and gets pushed onto the stack, requiring space proportional to the input size.

This is optimal for this problem. You cannot do better than O(n) time because you must examine every character, and you cannot do better than O(n) space in the worst case because you may need to store all opening brackets.

Handling Edge Cases

A robust solution must handle edge cases gracefully. Here are the scenarios to consider:

• Empty string: Should return true, as there are no unmatched brackets.
• Single opening bracket: Should return false because it is never closed.
• Single closing bracket: Should return false because the stack is empty when we try to match.
• Only opening brackets: Should return false because the stack is non-empty at the end.
• Only closing brackets: Should return false on the first character because the stack is empty.
• Very long strings: The solution scales linearly, so it handles large inputs efficiently.

Our implementation handles all of these correctly. The check len(stack) == 0 before accessing the top element prevents index-out-of-range panics, and the final len(stack) == 0 check catches any unclosed brackets.

Best Practices for Go Implementations

Use a Map for Bracket Pairs

Using a map to associate closing brackets with their opening counterparts makes the code clean and easy to extend. If you ever need to support additional bracket types, such as angle brackets < and >, you simply add another entry to the map.

Prefer Slices Over Custom Stack Types for Simplicity

For a problem this small, building a custom stack struct is overkill. Go slices provide all the operations you need with minimal boilerplate. However, if you find yourself using stacks across multiple files, consider defining a reusable type:

package main

type Stack struct {
    data []rune
}

func (s *Stack) Push(r rune) {
    s.data = append(s.data, r)
}

func (s *Stack) Pop() (rune, bool) {
    if len(s.data) == 0 {
        return 0, false
    }
    top := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return top, true
}

func (s *Stack) Peek() (rune, bool) {
    if len(s.data) == 0 {
        return 0, false
    }
    return s.data[len(s.data)-1], true
}

func (s *Stack) IsEmpty() bool {
    return len(s.data) == 0
}

func isValidWithStack(s string) bool {
    matching := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    stack := &Stack{}

    for _, char := range s {
        if open, isClosing := matching[char]; isClosing {
            top, ok := stack.Peek()
            if !ok || top != open {
                return false
            }
            stack.Pop()
        } else {
            stack.Push(char)
        }
    }

    return stack.IsEmpty()
}

This approach improves readability and reusability when your codebase grows.

Use Runes for Character Iteration

Always iterate over strings using range, which yields rune values, rather than indexing with s[i], which yields byte values. This avoids subtle bugs with multi-byte Unicode characters and is idiomatic Go.

Write Table-Driven Tests

Go's testing conventions favor table-driven tests. Here is an example test file that validates the solution thoroughly:

package main

import "testing"

func TestIsValid(t *testing.T) {
    tests := []struct {
        name     string
        input    string
        expected bool
    }{
        {"simple pair", "()", true},
        {"multiple pairs", "()[]{}", true},
        {"mismatched", "(]", false},
        {"wrong order", "([)]", false},
        {"nested valid", "{[]}", true},
        {"empty string", "", true},
        {"single open", "(", false},
        {"single close", ")", false},
        {"deeply nested", "(((())))", true},
        {"unclosed nested", "((()", false},
        {"extra closing", "())", false},
        {"mixed valid", "({[]})", false},
        {"long valid", "(((((())))))[]{}{}", true},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            result := isValid(tt.input)
            if result != tt.expected {
                t.Errorf("isValid(%q) = %v, expected %v",
                    tt.input, result, tt.expected)
            }
        })
    }
}

Run the tests with go test -v to see detailed output for each case. Table-driven tests make it trivial to add new cases as you discover edge cases in production.

Avoid Premature Optimization

It might be tempting to add an early exit check, such as returning false if the string length is odd. While this is a valid optimization, it only helps in specific cases and adds a tiny amount of complexity. In most real-world scenarios, the linear scan is fast enough, and clarity should take priority. Only add such optimizations if profiling shows they are necessary.

Common Mistakes to Avoid

• Forgetting to check if the stack is empty before popping: This causes a panic in Go when you access stack[len(stack)-1] on an empty slice.
• Returning true immediately when the stack is empty at the end of a closing bracket: You must process every character before deciding validity.
• Using byte instead of rune: While it works for ASCII brackets, it is not idiomatic and can cause issues if the input ever contains non-ASCII characters.
• Not handling the empty string: Some implementations incorrectly return false for empty input. An empty string is valid by definition.
• Confusing the direction of the map: Mapping opening brackets to closing ones versus closing to opening changes how you write the matching logic. Pick one convention and stick with it consistently.

Extending the Solution

Once you understand the basic solution, you can extend it to handle more complex scenarios. For example, you might want to ignore non-bracket characters in the input, effectively validating only the bracket structure of a string that contains other text:

func isValidWithNoise(s string) bool {
    matching := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    opening := map[rune]bool{
        '(': true,
        '{': true,
        '[': true,
    }

    stack := []rune{}

    for _, char := range s {
        if opening[char] {
            stack = append(stack, char)
        } else if open, isClosing := matching[char]; isClosing {
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        }
        // Ignore all other characters
    }

    return len(stack) == 0
}

This variant is useful when validating brackets in source code snippets or configuration files where other characters are present.

Conclusion

The Valid Parentheses problem is a perfect introduction to stack-based thinking and remains one of the most valuable algorithms to master. By using a Go slice as a stack, a map to define bracket pairs, and careful edge-case handling, you can write a solution that is both efficient and easy to understand. The O(n) time and space complexity is optimal, and the patterns you learn here transfer directly to more advanced parsing problems, compiler design, and expression evaluation. Whether you are preparing for a coding interview or building a real-world validator, the principles covered in this guide will serve as a reliable foundation for your Go programming toolkit.