Interview Questions/Coding/Safe Bracket Corridor

Safe Bracket Corridor

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Safe Bracket Corridor

A robot crosses a grid from the top-left cell to the bottom-right cell. It may only move one cell down or one cell right. Each visited cell writes one bracket character, either ( or ), onto the robot's audit tape. A route is accepted only if the full tape is a valid bracket sequence. That means every prefix of the tape must have at least as many opening brackets as closing brackets, and the complete tape must end with equal counts of opening and closing brackets. Input Format: You are given an array grid of strings, where each character is either ( or ). Output Format: Return true if at least one accepted route exists, otherwise return false.

Examples

Example 1
Input:
grid = ["(()", "())"]
Output:
true

Explanation: One valid route is (0,0) -> (1,0) -> (1,1) -> (1,2), forming "(())". It is balanced, so the output is true.

Approach hint

The route length is fixed.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp