Validate Properly Nested Brackets

Question

The candidate is asked to write a function that checks if the brackets in a given string are properly nested and closed.

Codemia · Accepted Answer

To solve the problem of validating properly nested brackets, I will use a stack data structure. The idea is to push each opening bracket onto the stack and pop from the stack when a closing bracket is encountered. If the brackets match, we continue; otherwise, the string is invalid. Finally, if the stack is empty at the end of the process, the brackets are properly nested.

1. Initialize an empty stack.
2. Iterate through each character in the string:
   - If the character is an opening bracket ('(', '{', or '['), push it onto the stack.
   - If it is a closing bracket (')', '}', or ']'), check if the stack is not empty and if the top of the stack matches the closing bracket. If it does, pop the stack; if not, return false.
3. After processing all characters, return true if the stack is empty; otherwise, return false.

The time complexity of this algorithm is O(n), where n is the length of the input string, because we traverse the string once. The space complexity is O(n) in the worst case when all characters are opening brackets, and we store them in the stack.

```python
def is_valid_parentheses(s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in bracket_map.values():
            stack.append(char)
        elif char in bracket_map.keys():
            if stack == [] or bracket_map[char] != stack.pop():
                return False
    return stack == []
```
This code defines a function that checks if the input string has valid parentheses.

It's important to consider edge cases such as an empty string, which should return true, or strings with no brackets, which should also return true. Additionally, handling mismatched brackets and ensuring that the order of brackets is correct is crucial for a robust solution.

Validate Properly Nested Brackets

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string