Validate that brackets are balanced

I've done a test for a job (which I failed) and I'd like to know in which ways my code could've been better.

Here are the questions and my answers, it's not very long.


1) Make a program that checks if a string has balanced parentheses or
brackets.

• Braces: (), [], <>

• For every closing brace, there must've been an opening, and for every open there must be a closure

• return 1 if it's balanced, or 0 if it isn't

My code:

const verify = (string) => {

    // Array of the type of braces
    var braces = ["(", ")", "[", "]", ""];
    // Array half the length of braces Array
    var balanced = Array.apply(null, {length: braces.length/2}).map(function() { return 0; });

    for(let i = 0; i < string.length; ++i) {
        let char = string[i], braceIndex = braces.indexOf(char);

        if ( braceIndex == -1 ) { 
            // If current char is not any type of brace, continue.
            continue;
        }

        // Get the index of the brace found halved and floored
        let braceBalancingIndex = braceIndex / 2, braceFloor = Math.floor( braceBalancingIndex );

        // If the halved index is equal to the index, then it must be an opening, else it must be a closing
        if (braceBalancingIndex == braceFloor) {
            balanced[braceFloor]++;
        }
        else {
            balanced[braceFloor]--;
        }

        // If at any type being, the balance is negative, there was a closing without opening
        for(let j = 0; j < balanced.length; ++j) {
            if (balanced[j] < 0) return 0;
        }

    }

    // If at the end the string is not balanced, there where more openings than closings
    for(let i = 0; i < balanced.length; ++i) {
        if (balanced[i] != 0) return 0;
    }

    return 1;
}

At its heart, this is a stack problem. You can get O(n) worst-case performance and O(n) space complexity by simply iterating the string in place, pushing opening brackets onto a stack and when encountering a closing bracket, popping the last item off stack to compare against.

You need to end up with an empty stack, and you can never have a case where you try to read out of an empty stack. This in addition, of course to making sure items you are comparing out of the stack match appropriately. So, there are three failure scenarios.

The solution I present might technically be optimized by hard-coding the opening and closing bracket values into conditionals and such, but I find this solution more flexible and easier to maintain from a code standpoint, as you have decoupled the bracket "configuration" from the code logic.

var balanced = '({[test string](test [string])})';
var unbalanced = '{()}]';
var empty = '';

var bracketConfig = [
    { left: '{', right: '}' },
    { left: '[', right: ']' },
    { left: '(', right: ')' }
];

function isBalanced(subject, bracketConfig) {
    // not shown - perhaps validate subject as string and error out if failing

    // build bracket arrays from config
    var openingChars = [];
    var closingChars = [];
    bracketConfig.forEach( (item) => {
        openingChars.push(item.left);
        closingChars.push(item.right);
    });

    var stack = [];
    for (var i = 0, len = subject.length; i  -1) {
            stack.push(openIdx);
        } else if (closeIdx > -1) {            
            if (stack.length === 0) return 0;
            lastIdx = stack.pop();
            if(lastIdx !== closeIdx) return 0;
        }
    }

    if (stack.length !== 0) return 0;
    return 1;     
}

// run tests
console.log(isBalanced(balanced, bracketConfig));
console.log(isBalanced(unbalanced, bracketConfig));
console.log(isBalanced(empty, bracketConfig));

JSFiddle of this example

My guess is that, for your interview, they were really looking to see that you could identify this as a stack problem and come up with a reasonable implementation.

StackExchange Code Review Q#147259, answer score: 7