Katkat
Back

Validate Properly Nested Brackets

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests understanding of basic data structures—specifically stacks—to validate balanced and nested bracket sequences in linear time.

Validate Properly Nested Brackets

Given a string s containing only the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.

An input string is valid if and only if:

  1. Open brackets are closed by the same type of brackets.
  2. Open brackets are closed in the correct, last-opened first-closed order.
  3. Every close bracket has a corresponding open bracket of the same type.
  4. An empty string is considered valid.

Function Signature

def is_valid(s: str) -> bool:
    pass

Constraints

  • 0 <= len(s) <= 10^5
  • s consists solely of the characters '(', ')', '{', '}', '[', and ']'.

Examples

Example 1:

Input: s = "()[]{}"
Output: True
Explanation: Each bracket is closed by its matching counterpart immediately or in proper sequence.

Example 2:

Input: s = "([)]"
Output: False
Explanation: The square bracket is closed before the round bracket that was opened after it, violating nesting order.

Example 3:

Input: s = "{[]}"
Output: True
Explanation: The inner square brackets are closed before the outer curly brackets are closed.

Edge Cases to Consider

  • The empty string "" should return True.
  • A string with an odd length can never be fully balanced.
  • Strings starting with a closing bracket (e.g., "]") or ending with unmatched open brackets (e.g., "(()").

Hints

Hint 1

Notice that the most recently opened bracket must be the first one closed, which matches a Last-In, First-Out (LIFO) pattern.

Hint 2

Use a stack to store opening brackets and a hash map to quickly look up matching pairs when you see a closing bracket.

Hint 3

Remember to verify that the stack is completely empty after processing all characters to catch unclosed opening brackets.

Follow-up questions

  • How would you adapt the solution if the string also contains arbitrary non-bracket characters, like in a math equation?
  • How would you handle a rule where brackets must adhere to strict nesting hierarchies (e.g., curly brackets can contain square brackets, but square brackets cannot contain curly brackets)?
  • If the input were provided as a stream of billions of characters, how would you optimize memory usage or validate chunks in parallel?