How to Solve Valid Parentheses in an Interview

The best way to solve Valid Parentheses in an interview is to use the stack data structure to implement a one-pass (O(N)) solution. This problem cannot be reduced below O(N) time complexity.

The problem says that a string is valid if it matches the following criteria:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

For the first and third points, let us confirm with the interviewer what “closed” looks like. Brackets are closed if you have 1 open and 1 close bracket of the same type: () [] {}. Write this in the comments.

The second point, “Open brackets must be closed in the correct order,” is not very descriptive. Ask the interviewer what the correct order is. If your interviewer does not fully define the correct order for you, keep asking questions until you both agree. This should be a quick and engaging process.

The correct bracket order on Leetcode is any order where the most recent open bracket is closed by the most recent close bracket. In other words, the last open bracket you read is the first open bracket used to validate closed-ness. This is known as Last-in, First-out (LIFO) ordering. Write out these conclusions in the comments.

Tell your interviewer you believe a Stack will be a helpful data structure given the LIFO ordering. The last element pushed to a stack is the first element allowed to leave the stack. Depending on your programming language, you may have a specific implementation for a stack, or you may have to use a list in a conceptually similar way.

Before you begin coding, walk through a few iterations of a valid test case. I’ve walked through a more complex test case that will eventually cover more code, but you can start with a simpler one. The point of this step is to show how your algorithm will process the input.

Every iteration, draw your for-loop pointer to the character. If the character is an open bracket, draw the character onto the stack.

If the character is a close bracket, say out loud if you can close the bracket or not. In the valid case, show the open bracket being removed from the stack when you match it with the close bracket.

It will also help to walk through iterations of an invalid test case. When you complete your code, you will validate whether your algorithm does what you want it to do.

I find it helpful to translate your concept to pseudocode comments. This will demonstrate what you want your code to do. This will also make it easier for your interviewer to follow your thinking. Depending on your interviewer, they may stop your solution here. If not, implement your solution in your language

At this point, you should hopefully know your language’s syntax to solve this problem.

Depending on your interviewer, this step may not be necessary.