The Brackets challenge from Codility was a fun exercise.<\/p>\n\n\n\n
A solution with O(N) complexity requires a single run of the array. <\/p>\n\n\n\n
At each step, we operate on a stack following three cases:<\/p>\n\n\n\n
function solution(S) {\n \/\/ write your code in JavaScript (Node.js 8.9.4)\n let progress = true\n let index = 0\n let stack = []\n let error = false\n while (index < S.length) {\n if (stack.length === 0) {\n if (S[index] === ')' || S[index] === ']' || S[index] === '}') {\n return 0\n } else {\n stack.push(S[index])\n }\n }\n else if (is_properly_nested(stack[stack.length-1],S[index])) {\n stack.pop(stack[stack.length-1])\n } else {\n if (S[index] === ')' || S[index] === ']' || S[index] === '}') {\n return 0\n }\n else {\n stack.push(S[index])\n }\n }\n index ++\n }\n\n if (stack.length === 0) {\n return 1\n } else {\n return 0\n }\n}\n\nfunction is_properly_nested(a,b){\n if ( (a === '(' && b === ')') || (a === '[' && b === ']') || (a === '{' && b === '}')) {\n return true\n }\n else {\n return false\n }<\/code><\/pre>\n\n\n\n