Tasks Details
easy
1.
Nesting
Determine whether a given string of parentheses (single type) is properly nested.
Task Score
100%
Correctness
100%
Performance
100%
A string S consisting of N characters is called properly nested if:
- S is empty;
- S has the form "(U)" where U is a properly nested string;
- S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.
Write a function:
function solution(S);
that, given a string S consisting of N characters, returns 1 if string 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..1,000,000];
- string S is made only of the characters '(' and/or ')'.
Copyright 2009–2023 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used JavaScript
Total time used 37 minutes
Effective time used 37 minutes
Notes
not defined yet
Task timeline
Code: 02:00:37 UTC,
java,
autosave
Code: 02:04:40 UTC,
js,
autosave
function solution(S) {
// write your code in JavaScript (Node.js 8.9.4)
let progress = true
let index = 0
let stack = []
let error = false
while (index < S.length) {
if (stack.length === 0) {
if (S[index] === ')' ) {
return 0
} else {
stack.push(S[index])
}
}
else if (is_properly_nested(stack[stack.length-1],S[index])) {
stack.pop(stack[stack.length-1])
} else {
if (S[index] === ')' ) {
return 0
}
else {
stack.push(S[index])
}
}
index ++
}
if (stack.length === 0) {
return 1
} else {
return 0
}
}
function is_properly_nested(a,b){
if (a === '(' && b === ')') {
return true
}
else {
return false
}
}
Code: 02:04:40 UTC,
js,
verify,
result: Passed
function solution(S) {
// write your code in JavaScript (Node.js 8.9.4)
let progress = true
let index = 0
let stack = []
let error = false
while (index < S.length) {
if (stack.length === 0) {
if (S[index] === ')' ) {
return 0
} else {
stack.push(S[index])
}
}
else if (is_properly_nested(stack[stack.length-1],S[index])) {
stack.pop(stack[stack.length-1])
} else {
if (S[index] === ')' ) {
return 0
}
else {
stack.push(S[index])
}
}
index ++
}
if (stack.length === 0) {
return 1
} else {
return 0
}
}
function is_properly_nested(a,b){
if (a === '(' && b === ')') {
return true
}
else {
return false
}
}
Analysis
Code: 02:04:44 UTC,
js,
verify,
result: Passed
function solution(S) {
// write your code in JavaScript (Node.js 8.9.4)
let progress = true
let index = 0
let stack = []
let error = false
while (index < S.length) {
if (stack.length === 0) {
if (S[index] === ')' ) {
return 0
} else {
stack.push(S[index])
}
}
else if (is_properly_nested(stack[stack.length-1],S[index])) {
stack.pop(stack[stack.length-1])
} else {
if (S[index] === ')' ) {
return 0
}
else {
stack.push(S[index])
}
}
index ++
}
if (stack.length === 0) {
return 1
} else {
return 0
}
}
function is_properly_nested(a,b){
if (a === '(' && b === ')') {
return true
}
else {
return false
}
}
Analysis
Code: 02:36:33 UTC,
js,
verify,
result: Passed
function solution(S) {
// write your code in JavaScript (Node.js 8.9.4)
let progress = true
let index = 0
let stack = []
let error = false
while (index < S.length) {
if (stack.length === 0) {
if (S[index] === ')' ) {
return 0
} else {
stack.push(S[index])
}
}
else if (is_properly_nested(stack[stack.length-1],S[index])) {
stack.pop(stack[stack.length-1])
} else {
if (S[index] === ')' ) {
return 0
}
else {
stack.push(S[index])
}
}
index ++
}
if (stack.length === 0) {
return 1
} else {
return 0
}
}
function is_properly_nested(a,b){
if (a === '(' && b === ')') {
return true
}
else {
return false
}
}
Analysis
Code: 02:36:36 UTC,
js,
final,
score:
100
function solution(S) {
// write your code in JavaScript (Node.js 8.9.4)
let progress = true
let index = 0
let stack = []
let error = false
while (index < S.length) {
if (stack.length === 0) {
if (S[index] === ')' ) {
return 0
} else {
stack.push(S[index])
}
}
else if (is_properly_nested(stack[stack.length-1],S[index])) {
stack.pop(stack[stack.length-1])
} else {
if (S[index] === ')' ) {
return 0
}
else {
stack.push(S[index])
}
}
index ++
}
if (stack.length === 0) {
return 1
} else {
return 0
}
}
function is_properly_nested(a,b){
if (a === '(' && b === ')') {
return true
}
else {
return false
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.068 s
OK
2.
0.068 s
OK
1.
0.068 s
OK
1.
0.068 s
OK
2.
0.068 s
OK
3.
0.068 s
OK
1.
0.072 s
OK
2.
0.068 s
OK
3.
0.068 s
OK
expand all
Performance tests
1.
0.076 s
OK
2.
0.076 s
OK
3.
0.068 s
OK
1.
0.104 s
OK
2.
0.068 s
OK
multiple_full_binary_trees
sequence of full trees of the form T=(TT), depths [1..10..1], with/without unmatched ')' at the end, length=49K+
sequence of full trees of the form T=(TT), depths [1..10..1], with/without unmatched ')' at the end, length=49K+
✔
OK
1.
0.076 s
OK
2.
0.076 s
OK
3.
0.068 s
OK
broad_tree_with_deep_paths
string of the form (TTT...T) of 300 T's, each T being '(((...)))' nested 200-fold, length=1 million
string of the form (TTT...T) of 300 T's, each T being '(((...)))' nested 200-fold, length=1 million
✔
OK
1.
0.092 s
OK
2.
0.068 s
OK