Today, I’d like to present a small algorithmic problem and some solutions I have come up with.

The problem is as follows: Given a string, determine if the parentheses are balanced.

Balanced parentheses mean that for every ( found, there must be a corresponding ) to balance it.

Input and output#

It is guarantee that any given string will contain at least one parenthesis.

in: "(hello"
out: false

in: "(hello()world)()"
out: true

in: "hello()(())"
out: true

in: "()"
out: true

in: "("
out: false

Solutions#

Using a Hash Table (Dictionary)#

Let’s try a simple approach using a hash table.

We know that we need to have the same number of left and right parentheses at the end of a string traversal. If this doesn’t happen, then we can be sure that the string doesn’t have balanced parentheses.

We could use a hash table to count the occurrences of the left and right parentheses in the given string. Then we compare both results.

With this idea let’s implement a solution:

func balancedParentheses(_ str: String) -> Bool {
    var dic = [String: Int]()
    
    str.forEach { char in
        if char == "(" || char == ")" {
            // What does default do?
            // If the key doesn't exist add the key with an initial default value
            dic[String(char), default: 0] += 1
        }
    }
    
    return dic["("] == dic[")"]
}

This solution has a time complexity of $O(n)$.

The spatial complexity is $O(1)$, because we are always storing only two key-value pairs.

Discarding the hash table#

The previous solution works for the given problem but we are creating an extra data structure that can add unwanted complexity, maybe using a hash table for this specific problem is overkill.

Let’s try a simpler approach.

func balancedParentheses(_ str: String) -> Bool {
    var counter = 0
    
    str.forEach { char in
        if char == "("  {
            counter += 1
        } else if char == ")" {
            counter -= 1
        }
    }
    
    return counter == 0
}

Now we are using an Int to keep a count of the parentheses. We add 1 for a left one and subtract 1 for the right one. If the number of left and right parentheses is equal, then we can be sure that the parentheses are balanced and the final count should be 0.

By eliminating the hash table, we archive a code that is simpler to reason about by avoiding unnecessary layers.

The time and space complexity remains the same.

Using Stacks#

Another solution involves the use of Stacks, which can help us explore more advanced algorithmic techniques like backtracking.

Stacks are a common and useful data structure but are not implemented by default in Swift. They are typically implemented using an Array by restricting the insertion and deletion operations to the end of the structure.

To solve the given problem, we can use the Stack to store the left parentheses and popping only when a right parenthesis is found. As before, if the Stack finishes empty, then the parentheses in the string are balanced.

Stack Parentheses

Let’s start by implementing the Stack.

struct Stack<T> {
    private var storage: [T] = []

    var isEmpty: Bool {
        storage.isEmpty
    }

    mutating func push(_ element: T) {
        storage.append(element)
    }

    @discardableResult
    mutating func pop() -> T? {
        storage.popLast()
    }
}

We mark pop with @discardableResult because we want to tell the program that we don’t care for the returned value and this can be discarded safely if we don’t assign it to any variable.

Now let’s implement the solution.

func balancedParentheses(_ str: String) -> Bool {
    var stack = Stack<Character>()
    
    for char in str {
        if char == "("  {
            stack.push(char)
        } else if char == ")" {
            if stack.isEmpty {
                return false
            } else {
                stack.pop()
            }
        }
    }
    
    return stack.isEmpty
}

We are using Character instead of String because the for in returns a single char when traversing the string.

Let’s explain in more detail our solution.

As mentioned before we add to the Stack all ( found.

If we find a ) two possibilities can arise:

  • The Stack state is empty.
  • The Stack state is not empty.

In the first case we didn’t find a matching parenthesis so we can be certain that the parentheses in the string are not balanced.

In the second case, we can pop the previous right parenthesis and continue looking for the next parentheses.

Now let’s focus on the last return, we are checking for the state of the Stack because the case of the Stack containing orphaned ( can occur, in that case the parentheses in the string are also not balanced.

The time complexity is $O(n)$ because we traverse the array only once.

The space complexity is $O(n)$ because in the worse case we would get a string containing only (, creating a stack with the same length as the string.

Conclusion#

In this small problem, we’ve observed that using stacks can lead to an increase in memory consumption without providing significant benefits. In the case of hash tables, the complexity is similar to the counting approach.

For problems that are straightforward and don’t involve complex matching, a simpler approach often yields better results.

It’s essential to understand the constraints of the problem to weigh the advantages and disadvantages of our solutions and ensure that we select the most suitable option for the task at hand.

This way of thinking can help us avoid overengineering solutions that add unnecessary complexity without providing real benefits.