Tasks Details
easy
1.
Brackets
Determine whether a given string of parentheses (multiple types) is properly nested.
Task Score
100%
Correctness
100%
Performance
100%
A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
- 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.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
def solution(S)
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..200,000];
- string S is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 1 minutes
Notes
not defined yet
Code: 09:10:21 UTC,
java,
autosave
Code: 09:10:32 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
def solution(S):
"""
Idea is to use stack concept
Used array [] as stack
Keep adding item in stack until open brackets found, Keep popping up item if closing bracket found.
On each pop of item check popped item it should match with the opposite bracket as explained in example else not balanced.
4 push 4 pop
{[()()]}
push {
push [
push (
pop )
push (
pop )
pop ]
pop }
gets empty
2 push 1 pop
([)()]
(
[
) - not matching with [ so not balanced
"""
stack = []
for bracket in S:
# open bracket found push in to stack, used array as stack append item at top
if bracket == "{" or bracket == "[" or bracket == "(":
stack.append(bracket)
# any closing bracket found and stack is not empty remote item from stack top
elif bracket == "}" and stack:
pop_item = stack.pop()
# check popped item, if it is not similar( ie. opposite or open) as bracket then this S can not be balanced
if pop_item != "{":
return 0
elif bracket == "]" and stack:
pop_item = stack.pop()
if pop_item != "[":
return 0
elif bracket == ")" and stack:
pop_item = stack.pop()
if pop_item != "(":
return 0
# at any point if neither open nor close operation can be performed, stack is not balanced
else:
return 0
print(stack)
# if stack is empty stack, it is balanced ie. all push and pop operation on S is successful¬.
if not stack:
return 1
# S is not balanced
return 0
Code: 09:10:34 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
def solution(S):
"""
Idea is to use stack concept
Used array [] as stack
Keep adding item in stack until open brackets found, Keep popping up item if closing bracket found.
On each pop of item check popped item it should match with the opposite bracket as explained in example else not balanced.
4 push 4 pop
{[()()]}
push {
push [
push (
pop )
push (
pop )
pop ]
pop }
gets empty
2 push 1 pop
([)()]
(
[
) - not matching with [ so not balanced
"""
stack = []
for bracket in S:
# open bracket found push in to stack, used array as stack append item at top
if bracket == "{" or bracket == "[" or bracket == "(":
stack.append(bracket)
# any closing bracket found and stack is not empty remote item from stack top
elif bracket == "}" and stack:
pop_item = stack.pop()
# check popped item, if it is not similar( ie. opposite or open) as bracket then this S can not be balanced
if pop_item != "{":
return 0
elif bracket == "]" and stack:
pop_item = stack.pop()
if pop_item != "[":
return 0
elif bracket == ")" and stack:
pop_item = stack.pop()
if pop_item != "(":
return 0
# at any point if neither open nor close operation can be performed, stack is not balanced
else:
return 0
# print(stack)
# if stack is empty stack, it is balanced ie. all push and pop operation on S is successful¬.
if not stack:
return 1
# S is not balanced
return 0
Analysis
Code: 09:10:38 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
def solution(S):
"""
Idea is to use stack concept
Used array [] as stack
Keep adding item in stack until open brackets found, Keep popping up item if closing bracket found.
On each pop of item check popped item it should match with the opposite bracket as explained in example else not balanced.
4 push 4 pop
{[()()]}
push {
push [
push (
pop )
push (
pop )
pop ]
pop }
gets empty
2 push 1 pop
([)()]
(
[
) - not matching with [ so not balanced
"""
stack = []
for bracket in S:
# open bracket found push in to stack, used array as stack append item at top
if bracket == "{" or bracket == "[" or bracket == "(":
stack.append(bracket)
# any closing bracket found and stack is not empty remote item from stack top
elif bracket == "}" and stack:
pop_item = stack.pop()
# check popped item, if it is not similar( ie. opposite or open) as bracket then this S can not be balanced
if pop_item != "{":
return 0
elif bracket == "]" and stack:
pop_item = stack.pop()
if pop_item != "[":
return 0
elif bracket == ")" and stack:
pop_item = stack.pop()
if pop_item != "(":
return 0
# at any point if neither open nor close operation can be performed, stack is not balanced
else:
return 0
# print(stack)
# if stack is empty stack, it is balanced ie. all push and pop operation on S is successful¬.
if not stack:
return 1
# S is not balanced
return 0
Analysis
Code: 09:10:41 UTC,
py,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
def solution(S):
"""
Idea is to use stack concept
Used array [] as stack
Keep adding item in stack until open brackets found, Keep popping up item if closing bracket found.
On each pop of item check popped item it should match with the opposite bracket as explained in example else not balanced.
4 push 4 pop
{[()()]}
push {
push [
push (
pop )
push (
pop )
pop ]
pop }
gets empty
2 push 1 pop
([)()]
(
[
) - not matching with [ so not balanced
"""
stack = []
for bracket in S:
# open bracket found push in to stack, used array as stack append item at top
if bracket == "{" or bracket == "[" or bracket == "(":
stack.append(bracket)
# any closing bracket found and stack is not empty remote item from stack top
elif bracket == "}" and stack:
pop_item = stack.pop()
# check popped item, if it is not similar( ie. opposite or open) as bracket then this S can not be balanced
if pop_item != "{":
return 0
elif bracket == "]" and stack:
pop_item = stack.pop()
if pop_item != "[":
return 0
elif bracket == ")" and stack:
pop_item = stack.pop()
if pop_item != "(":
return 0
# at any point if neither open nor close operation can be performed, stack is not balanced
else:
return 0
# print(stack)
# if stack is empty stack, it is balanced ie. all push and pop operation on S is successful¬.
if not stack:
return 1
# S is not balanced
return 0Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
expand all
Performance tests
1.
0.084 s
OK
2.
0.036 s
OK
3.
0.040 s
OK
1.
0.040 s
OK
2.
0.036 s
OK
3.
0.044 s
OK
1.
0.084 s
OK
multiple_full_binary_trees
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
✔
OK
1.
0.048 s
OK
2.
0.048 s
OK
3.
0.048 s
OK
4.
0.048 s
OK
5.
0.036 s
OK
broad_tree_with_deep_paths
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
✔
OK
1.
0.060 s
OK
2.
0.060 s
OK