Codility - Brackets

Solution to Codility lesson5 Brackets problem, link to Codility problem and complete solution at the end of the post.

Definitions:
\{N \in \mathbb{N}\ |\ 0\leq N \leq 200,000\}

Properly nested string S:

  • S is empty;
  • S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
  • S has the form "VW" where V and W are properly nested strings.

Problem:
Define a function solution with input S , such that solution returns 1 if string S is properly nested and 0 otherwise.

  • Expected worst-case time complexity is O(N);
  • Expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Analysis:

This problem is very similar to the Nesting problem. Only here we are going to use an actual stack to stack the characters. And similar to the Nesting problem, '(', '{', '[' will be a push, and ')', '}', ']' will be a pop. But here we will have to analyse the return of the pop operation, and it will have to be the inverse of the symbol used for pop. If it is not we can return 0. We can also return 0 if we pop an empty stack or if at the end of the iteration there still elements at the stack. Otherwise we can return 1.
Visiting every element of S gives us a time complexity of O(N).
For the space complexity we have O(N). In the worst case the stack size will be N//2 because in a properly nested string the numbers of elements '(', '{', '[' is equal to half the size of the string. And since we push for every '(', '{', '[', this can be the maximum size of the stack.

Complete Solution:

Time Complexity O(N)
Space Complexity O(N)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/