Check if There Is a Valid Parentheses String Path

Check if There Is a Valid Parentheses String Path

What is this problem about?

This "Hard" problem asks if there is a path from the top-left to the bottom-right of a matrix filled with '(' and ')' that forms a valid parentheses string. A valid string must have an equal number of opening and closing parentheses, and at no point should the number of closing parentheses exceed the number of opening ones.

Why is this asked in interviews?

Google uses this to test advanced Dynamic Programming and state-space reduction. It combines the rules of valid parentheses (stack-like behavior) with grid traversal. It evaluates your ability to prune impossible paths early (e.g., if the balance becomes negative or too high to ever return to zero).

Algorithmic pattern used

The pattern is Dynamic Programming with State Pruning. The state at each cell $(i, j)$ is the current "balance" (count of '(' minus count of ')'). dp[i][j][balance] is a boolean indicating if a balance of balance is reachable at cell $(i, j)$. Similar to the previous problem, the path length is $m+n-1$, which must be even. Also, the start must be '(' and the end must be ')'.

Example explanation

$3 imes 3$ Matrix: ( ( ) ( ) ( ) ) )

1. Path (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2).
2. Values: '(', '(', ')', ')', ')'.
3. Balances: 1, 2, 1, 0, -1.
4. Since the balance hit -1, this path is invalid even though it might end at 0 later. You must find if any path stays $\ge 0$ and ends at exactly 0.

Common mistakes candidates make

Candidates often forget the "never go negative" rule, which is the defining characteristic of valid parentheses. Another mistake is not recognizing that the maximum possible balance is limited by the remaining path length, allowing for significant state-space optimization. Some might try to use a stack in DFS, which leads to redundant work.

Interview preparation tip

Valid parentheses problems are almost always about "balance." If you can represent the state as a single integer (balance), you can often turn a complex string problem into a simple DP or reachability problem.