Codility ‘Brackets’ Solution

Short Problem Definition:

Determine whether a given string of parentheses is properly nested.




expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)


Put every opening bracket on a stack. If a closing bracket is not the same as the top stack bracket, the string is not properly nested.

def isValidPair(left, right):
    if left == '(' and right == ')':
        return True
    if left == '[' and right == ']':
        return True  
    if left == '{' and right == '}':
        return True    
    return False

def solution(S):
    stack = []
    for symbol in S:
        if symbol == '[' or symbol == '{' or symbol == '(':
            if len(stack) == 0:
                return 0
            last = stack.pop()
            if not isValidPair(last, symbol):
                return 0
    if len(stack) != 0:
        return 0
    return 1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

  • Sonal Aggarwal

    Elegant solution!

    • thanks! Enjoy coding 🙂

  • Michiel van der Blonk

    I don’t think you need stacks. All you need are three counters. When encountering an opening bracket, increase the appropriate counter. When encountering a closing bracket, decrease the counter. When any counter < 0 during processing, you have an invalid string. When at the end, all counters should be 0.