#  Check if There Is a Valid Parentheses String Path
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-there-is-a-valid-parentheses-string-path)
Canonical: https://scaleengineer.com/dsa/problems/check-if-there-is-a-valid-parentheses-string-path
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## Problem
A parentheses string is a **non-empty** string consisting only of `'('` and `')'`. It is **valid** if **any** of the following conditions is **true**:

* It is `()`.
* It can be written as `AB` (`A` concatenated with `B`), where `A` and `B` are valid parentheses strings.
* It can be written as `(A)`, where `A` is a valid parentheses string.

You are given an `m x n` matrix of parentheses `grid`. A **valid parentheses string path** in the grid is a path satisfying **all** of the following conditions:

* The path starts from the upper left cell `(0, 0)`.
* The path ends at the bottom-right cell `(m - 1, n - 1)`.
* The path only ever moves **down** or **right**.
* The resulting parentheses string formed by the path is **valid**.

Return `true` _if there exists a **valid parentheses string path** in the grid._ Otherwise, return `false`.

**Example 1:**

![](https://assets.glich.co/dsa/check-if-there-is-a-valid-parentheses-string-path/image0.png) 

**Input:** grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
**Output:** true
**Explanation:** The above diagram shows two possible paths that form valid parentheses strings.
The first path shown results in the valid parentheses string "()(())".
The second path shown results in the valid parentheses string "((()))".
Note that there may be other valid parentheses string paths.

**Example 2:**

![](https://assets.glich.co/dsa/check-if-there-is-a-valid-parentheses-string-path/image1.png) 

**Input:** grid = [[")",")"],["(","("]]
**Output:** false
**Explanation:** The two possible paths form the parentheses strings "))(" and ")((". Since neither of them are valid parentheses strings, we return false.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 100`
* `grid[i][j]` is either `'('` or `')'`.

# Approaches
## Brute-Force Recursion (Backtracking)
This approach uses a standard backtracking algorithm to explore all possible paths from the top-left to the bottom-right corner. For each path, it constructs the corresponding parenthesis string and checks its validity on the fly by maintaining a balance counter.
**Time:** O(2^(m+n))

The number of paths from `(0,0)` to `(m-1,n-1)` is given by the binomial coefficient `C(m+n-2, m-1)`. In the worst case, the algorithm explores all of them, leading to an exponential time complexity. · **Space:** O(m + n)

The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the length of a path from `(0,0)` to `(m-1,n-1)`. The path length is `m + n - 1`.
**Pros:** Simple to conceptualize and implement.; Correct for small grid sizes.
**Cons:** Extremely inefficient due to re-computation of states for overlapping subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on larger grids.
### Explanation
The core idea is to use a recursive function that traverses the grid. The function keeps track of the current position `(row, col)` and the running balance of parentheses. The balance is defined as the number of open parentheses minus the number of closed parentheses.

A path is valid only if the balance never drops below zero at any point and is exactly zero at the end of the path. The recursion explores moving down and right from the current cell. If a move takes it out of bounds or makes the balance negative, that path is abandoned. If the destination is reached, we check if the final balance is zero.

```java
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // Initial checks for immediate failure
        if ((m + n - 1) % 2 != 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {
            return false;
        }
        return solve(grid, 0, 0, 0);
    }

    private boolean solve(char[][] grid, int r, int c, int balance) {
        int m = grid.length;
        int n = grid[0].length;

        // Check if out of bounds
        if (r >= m || c >= n) {
            return false;
        }

        // Update balance
        balance += (grid[r][c] == '(') ? 1 : -1;

        // Pruning: if balance is negative, this path is invalid
        if (balance < 0) {
            return false;
        }

        // Base case: reached the destination
        if (r == m - 1 && c == n - 1) {
            return balance == 0;
        }

        // Explore down and right
        if (solve(grid, r + 1, c, balance) || solve(grid, r, c + 1, balance)) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
1. Perform initial checks:
   - The path length `m + n - 1` must be even. If not, return `false`.
   - The starting cell `grid[0][0]` must be `'('`.
   - The ending cell `grid[m-1][n-1]` must be `')'`.
2. Define a recursive function `solve(row, col, balance)` that explores paths from `(row, col)`.
3. In the recursive function:
   - Update the current `balance` based on the character at `grid[row][col]`. Increment for `'('` and decrement for `')'`.
   - **Pruning:** If `balance` becomes negative, the path is invalid. Return `false` immediately.
   - **Base Case:** If the current cell is the destination `(m-1, n-1)`:
     - Return `true` if `balance` is exactly 0, otherwise `false`.
   - **Recursive Step:**
     - Explore the path by moving down: call `solve(row + 1, col, balance)`.
     - Explore the path by moving right: call `solve(row, col + 1, balance)`.
     - If either of the recursive calls returns `true`, it means a valid path was found, so return `true`.
4. If both paths lead to dead ends, return `false`.
5. The initial call is `solve(0, 0, 0)`.

## Dynamic Programming with Memoization
The brute-force approach is slow because it repeatedly solves the same subproblems. We can optimize this using memoization, a form of dynamic programming. We store the result for each state `(row, col, balance)` so that we only compute it once.
**Time:** O(m * n * (m+n))

The number of states is `m * n * (m+n)`. Each state is computed once, and the computation involves constant time work. · **Space:** O(m * n * (m+n))

The space is dominated by the memoization table of size `m * n * (m+n)`. The recursion stack depth adds `O(m+n)`.
**Pros:** Significantly faster than brute-force.; Guaranteed to run in polynomial time.; Passes the given constraints.
**Cons:** Requires a large amount of memory for the 3D memoization table, which can be a concern for very large constraints.
### Explanation
We define a state by the current cell `(r, c)` and the current parenthesis `balance`. The function `solve(r, c, balance)` will return `true` if there's a valid path from `(r, c)` to the destination, given the balance accumulated so far. We use a 3D array `memo[r][c][balance]` to cache the results.

When the function is called for a state, it first checks the memo table. If the result is already there, it's returned directly. Otherwise, the result is computed recursively, stored in the table, and then returned. This avoids redundant computations and drastically reduces the time complexity.

```java
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if ((m + n - 1) % 2 != 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {
            return false;
        }
        // memo[r][c][balance]: 0 = not computed, 1 = true, -1 = false
        int[][][] memo = new int[m][n][m + n];
        return solve(grid, 0, 0, 0, memo);
    }

    private boolean solve(char[][] grid, int r, int c, int balance, int[][][] memo) {
        int m = grid.length;
        int n = grid[0].length;

        if (r >= m || c >= n) {
            return false;
        }

        balance += (grid[r][c] == '(') ? 1 : -1;

        int remainingSteps = (m - 1 - r) + (n - 1 - c);
        if (balance < 0 || balance > remainingSteps) {
            return false;
        }

        if (memo[r][c][balance] != 0) {
            return memo[r][c][balance] == 1;
        }

        if (r == m - 1 && c == n - 1) {
            boolean result = (balance == 0);
            memo[r][c][balance] = result ? 1 : -1;
            return result;
        }

        if (solve(grid, r + 1, c, balance, memo) || solve(grid, r, c + 1, balance, memo)) {
            memo[r][c][balance] = 1;
            return true;
        }

        memo[r][c][balance] = -1;
        return false;
    }
}
```
### Algorithm
1. The state of a subproblem can be uniquely identified by `(row, col, balance)`.
2. Create a 3D memoization table, `memo[m][n][m+n]`, to store the results of computed subproblems. Initialize it with a value indicating 'not computed' (e.g., 0).
3. Implement the same recursive function `solve(row, col, balance)` as in the brute-force approach.
4. Before computing the result for a state `(row, col, balance)`, check if `memo[row][col][balance]` has already been computed. If so, return the stored result.
5. After computing the result for a state, store it in the memoization table before returning.
6. Add an additional pruning step: if the current `balance` is greater than the number of remaining steps in the path, it's impossible to reduce the balance to zero. The path can be pruned.

## Optimized Dynamic Programming with Balance Range
This is the most efficient approach, which optimizes the dynamic programming state. Instead of storing a set of all possible balances at each cell, we observe that these balances form a continuous range with a fixed step. Thus, we only need to store the minimum and maximum of this range, reducing the state space significantly.
**Time:** O(m * n)

We iterate through each cell of the `m x n` grid once, and the work done at each cell is constant time. · **Space:** O(m * n)

The space complexity is for the `dp` table of size `m * n * 2`.
**Pros:** Optimal time complexity.; Optimal space complexity.; Very fast for the given constraints.
**Cons:** The logic is more complex and less intuitive to derive and implement correctly compared to the previous approaches.
### Explanation
The core optimization comes from realizing that we don't need to store every single possible balance. At any cell `(i, j)`, all achievable balances will have the same parity, determined by the path length `i+j+1`. Furthermore, if balances `b1` and `b2` are achievable, all intermediate balances with the same parity are also achievable. This allows us to represent all possible balances with just a `[min, max]` range.

We use a 2D DP table where `dp[i][j]` stores this `[min, max]` range. We iterate through the grid, and for each cell `(i, j)`, we calculate its `[min, max]` range based on the ranges from the cells above `(i-1, j)` and to the left `(i, j-1)`. After calculating the new range, we must apply some adjustments: the balance cannot be negative, and it must have the correct parity. If the resulting `min` becomes greater than `max`, it means no valid balance is possible for this cell.

Finally, we check the range at the destination `(m-1, n-1)`. A valid path exists if and only if this cell is reachable and its minimum possible balance is 0.

```java
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        if ((m + n - 1) % 2 != 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {
            return false;
        }

        // dp[i][j] stores {min_balance, max_balance}. {-1, -1} means unreachable.
        int[][][] dp = new int[m][n][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = new int[]{-1, -1};
            }
        }

        dp[0][0] = new int[]{1, 1}; // After visiting (0,0), balance is 1

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                int change = (grid[i][j] == '(') ? 1 : -1;
                
                int min_b = Integer.MAX_VALUE;
                int max_b = Integer.MIN_VALUE;

                // From top
                if (i > 0 && dp[i - 1][j][0] != -1) {
                    min_b = Math.min(min_b, dp[i - 1][j][0] + change);
                    max_b = Math.max(max_b, dp[i - 1][j][1] + change);
                }
                // From left
                if (j > 0 && dp[i][j - 1][0] != -1) {
                    min_b = Math.min(min_b, dp[i][j - 1][0] + change);
                    max_b = Math.max(max_b, dp[i][j - 1][1] + change);
                }

                if (min_b == Integer.MAX_VALUE) continue; // Unreachable

                int pathLen = i + j + 1;
                
                if (max_b < 0) continue; // Cannot form a valid prefix
                min_b = Math.max(0, min_b);
                
                // Adjust for parity
                if (min_b % 2 != pathLen % 2) min_b++;
                if (max_b % 2 != pathLen % 2) max_b--;

                if (min_b <= max_b) {
                    dp[i][j][0] = min_b;
                    dp[i][j][1] = max_b;
                }
            }
        }

        return dp[m - 1][n - 1][0] == 0;
    }
}
```
### Algorithm
1. **Key Insight:** At any cell `(i, j)`, the set of all possible valid balances for paths from `(0,0)` to `(i,j)` forms a continuous arithmetic progression with a step of 2 (e.g., `{b, b+2, b+4, ...}`). This is because swapping between a `down-right` and `right-down` move at any point changes the balance by -2, 0, or 2. Therefore, we only need to track the minimum and maximum possible balances.
2. **DP State:** Let `dp[i][j]` be an array of two integers, `{min_balance, max_balance}`, representing the range of possible balances after visiting cell `(i, j)`.
3. **Initialization:**
   - Perform the same initial checks as before.
   - Create a `dp` table of size `m x n x 2`. Initialize unreachable states.
   - For the starting cell `(0,0)`, `dp[0][0] = {1, 1}` since `grid[0][0]` is `'('`.
4. **Transition:** Iterate through the grid from `(0,0)` to `(m-1, n-1)`. For each cell `(i, j)`:
   - Determine the possible range of balances by taking the union of ranges from the top cell `(i-1, j)` and the left cell `(i, j-1)`.
   - `min_b = min(dp[i-1][j][0], dp[i][j-1][0]) + change`
   - `max_b = max(dp[i-1][j][1], dp[i][j-1][1]) + change` where `change` is +1 for `'('` and -1 for `')'`.
   - **Adjust Range:**
     - If `max_b < 0`, the cell is unreachable with a valid prefix. Mark it as such.
     - Clamp the minimum balance: `min_b = max(0, min_b)`.
     - Adjust `min_b` and `max_b` to have the correct parity for the path length to `(i,j)`. The balance `b` and path length `i+j+1` must have the same parity. If `min_b` has the wrong parity, increment it. If `max_b` has the wrong parity, decrement it.
     - If `min_b > max_b` after adjustments, the cell is unreachable. Mark it.
     - Otherwise, store `dp[i][j] = {min_b, max_b}`.
5. **Final Result:** A valid path exists if the destination `(m-1, n-1)` is reachable and the final balance can be 0. This is true if `dp[m-1][n-1][0]` is 0.

# Solutions
### Java

```java
class Solution { private boolean [][][] vis ; private char [][] grid ; private int m ; private int n ; public boolean hasValidPath ( char [][] grid ) { m = grid . length ; n = grid [ 0 ]. length ; this . grid = grid ; vis = new boolean [ m ][ n ][ m + n ]; return dfs ( 0 , 0 , 0 ); } private boolean dfs ( int i , int j , int t ) { if ( vis [ i ][ j ][ t ]) { return false ; } vis [ i ][ j ][ t ] = true ; t += grid [ i ][ j ] == '(' ? 1 : - 1 ; if ( t < 0 ) { return false ; } if ( i == m - 1 && j == n - 1 ) { return t == 0 ; } int [] dirs = { 0 , 1 , 0 }; for ( int k = 0 ; k < 2 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x < m && y < n && dfs ( x , y , t )) { return true ; } } return false ; } }
```

### CPP

```cpp
bool vis [ 100 ][ 100 ][ 200 ]; int dirs [ 3 ] = { 1 , 0 , 1 }; class Solution { public: bool hasValidPath ( vector < vector < char >>& grid ) { memset ( vis , 0 , sizeof ( vis )); return dfs ( 0 , 0 , 0 , grid ); } bool dfs ( int i , int j , int t , vector < vector < char >>& grid ) { if ( vis [ i ][ j ][ t ]) return false ; vis [ i ][ j ][ t ] = true ; t += grid [ i ][ j ] == '(' ? 1 : - 1 ; if ( t < 0 ) return false ; int m = grid . size (), n = grid [ 0 ]. size (); if ( i == m - 1 && j == n - 1 ) return t == 0 ; for ( int k = 0 ; k < 2 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x < m && y < n && dfs ( x , y , t , grid )) return true ; } return false ; } };
```

### Python

```python
class Solution : def hasValidPath ( self , grid : List [ List [ str ]]) -> bool : @ cache def dfs ( i , j , t ): if grid [ i ][ j ] == '(' : t += 1 else : t -= 1 if t < 0 : return False if i == m - 1 and j == n - 1 : return t == 0 for x , y in [( i + 1 , j ), ( i , j + 1 )]: if x < m and y < n and dfs ( x , y , t ): return True return False m , n = len ( grid ), len ( grid [ 0 ]) return dfs ( 0 , 0 , 0 )
```