DEV Community

StormyTalent
StormyTalent

Posted on

JavaScript Interview Coding Test Problem 7

Learn how to determine if brackets are balanced or not. This is an actual problem that software developers must occasionally solve and many dev tools have their own implementation of it. We’ll learn how a code editor can pick up our mistakes and highlight exactly which brackets don't match.
Instructions
Given a string, return true if it contains all balanced parentheses ( ) curly- brackets () , and square-brackets [].
Input: String
Output: Boolean
Examples
is8alanced("(x + y) - (4)”); // -> true is8alanced("(((10 ) (}) ((?)(:)))”); // -› true isBalanced("[{()}]”); // -› true is8alanced("(50)(”); // -> false
isBalanced("[{]}”); // -› false
Solution

2   const openstack = [];
3   const open = '([{';
4   const close = ')]}';
5   const matches - {
6   ')': '(',
7   ']': '[',
8   '}': '{'
9   };
10
11  for (let i - 0; i ‹ str.length; i++) (
12  const char  str[i]; 13
14  // If it's an open bracket, push it into our array
15      if(open.includes(char)) (   
16      openstack.push(char);   
17          
18      // If it's a close bracket  
19      } else if(close.includes(char)) (   
20      // pop an item from the open brackets array.    
21      const lastopenBracket   openStack.pop();    
22          
23      // If the open and close bracket don't match,   return false
24      if(matches[char] !== lastopenBracket) { 
25      return false;   
26          
27      

28      

29          
30      // Ensures there are no characters left on the stack    
31      return !openStack.length;   
32  }       

Enter fullscreen mode Exit fullscreen mode

How it Works
In our for-loop, we process every character. If the current character is an open bracket, we push it onto our openstack array.
If it’s not a bracket, we do nothing.
Once we’re done processing the string, we have to check to make sure there
are no open brackets left on our stack. If there are, our string is unbalanced.
Time
This is a solutiDn with a time complexity Df:
0(n).
Every character is prDcessed in a loop. Inside the lDop, we perform only count-time actions.
Space
The space complexity is:
0(n).
Characters are stored in an array, generally proportional to the size of the input.
Conclusion
There are many ways to skin this cat. Another solution wDuld have been to have two pointers, one at the beginning and one at the end, moving towards the middle. They would be checking to make sure that brackets matched until they met. This would also be an o(n) solution.

Top comments (0)