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 avalid parentheses string path in the grid. Otherwise, return false.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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 ')'.

Solution

Method 1 – Dynamic Programming with Balance Tracking

Intuition

We need to find a path from the top-left to the bottom-right of the grid such that the parentheses string formed is valid. Since we can only move right or down, and the string must be valid at every step, we can use dynamic programming to track the possible balances (number of open minus close parentheses) at each cell.

Reasoning

At each cell, the only information that matters is the current balance (open - close) and the position. We can use a set to track all possible balances at each cell, propagating from the top-left to the bottom-right. If a balance of 0 is possible at the end, then a valid path exists. The balance must never be negative (more ‘)’ than ‘(’ at any point), and the final balance must be 0.

Approach

  1. Let m and n be the grid dimensions. The path length is m + n - 1.
  2. If the path length is odd, return false (cannot form a valid parentheses string).
  3. Use a DP table where dp[i][j] is a set of possible balances at cell (i, j).
  4. Initialize dp[0][0] with 1 if grid[0][0] == ‘(’, else -1 (invalid if negative).
  5. For each cell, propagate possible balances from the top and left neighbors, updating the balance according to the current cell’s value. Only keep balances >= 0.
  6. At the end, check if a balance of 0 is possible at the bottom-right cell.

Edge cases:

  • Path length is odd: impossible.
  • More ‘)’ than ‘(’ at any point: impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if ((m + n - 1) % 2) return false;
        vector<vector<unordered_set<int>>> dp(m, vector<unordered_set<int>>(n));
        dp[0][0].insert(grid[0][0] == '(' ? 1 : -1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int d : {0, 1}) {
                    int ni = i - d, nj = j - (1 - d);
                    if (ni >= 0 && nj >= 0) {
                        for (int bal : dp[ni][nj]) {
                            int nb = bal + (grid[i][j] == '(' ? 1 : -1);
                            if (nb >= 0) dp[i][j].insert(nb);
                        }
                    }
                }
            }
        }
        return dp[m-1][n-1].count(0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def has_valid_path(self, grid: list[list[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        if (m + n - 1) % 2:
            return False
        dp = [[set() for _ in range(n)] for _ in range(m)]
        dp[0][0].add(1 if grid[0][0] == '(' else -1)
        for i in range(m):
            for j in range(n):
                for ni, nj in ((i-1, j), (i, j-1)):
                    if 0 <= ni < m and 0 <= nj < n:
                        for bal in dp[ni][nj]:
                            nb = bal + (1 if grid[i][j] == '(' else -1)
                            if nb >= 0:
                                dp[i][j].add(nb)
        return 0 in dp[m-1][n-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        if ((m + n - 1) % 2 != 0) return false;
        Set<Integer>[][] dp = new HashSet[m][n];
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) dp[i][j] = new HashSet<>();
        dp[0][0].add(grid[0][0] == '(' ? 1 : -1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] d : new int[][]{{-1,0},{0,-1}}) {
                    int ni = i + d[0], nj = j + d[1];
                    if (ni >= 0 && nj >= 0) {
                        for (int bal : dp[ni][nj]) {
                            int nb = bal + (grid[i][j] == '(' ? 1 : -1);
                            if (nb >= 0) dp[i][j].add(nb);
                        }
                    }
                }
            }
        }
        return dp[m-1][n-1].contains(0);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun hasValidPath(grid: Array<CharArray>): Boolean {
        val m = grid.size; val n = grid[0].size
        if ((m + n - 1) % 2 != 0) return false
        val dp = Array(m) { Array(n) { mutableSetOf<Int>() } }
        dp[0][0].add(if (grid[0][0] == '(') 1 else -1)
        for (i in 0 until m) for (j in 0 until n) {
            for ((di, dj) in listOf(-1 to 0, 0 to -1)) {
                val ni = i + di; val nj = j + dj
                if (ni in 0 until m && nj in 0 until n) {
                    for (bal in dp[ni][nj]) {
                        val nb = bal + if (grid[i][j] == '(') 1 else -1
                        if (nb >= 0) dp[i][j].add(nb)
                    }
                }
            }
        }
        return 0 in dp[m-1][n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn has_valid_path(grid: Vec<Vec<char>>) -> bool {
        let m = grid.len();
        let n = grid[0].len();
        if (m + n - 1) % 2 != 0 {
            return false;
        }
        let mut dp = vec![vec![std::collections::HashSet::new(); n]; m];
        dp[0][0].insert(if grid[0][0] == '(' { 1 } else { -1 });
        for i in 0..m {
            for j in 0..n {
                for (di, dj) in [(-1, 0), (0, -1)] {
                    let ni = i as isize + di;
                    let nj = j as isize + dj;
                    if ni >= 0 && nj >= 0 {
                        for &bal in &dp[ni as usize][nj as usize] {
                            let nb = bal + if grid[i][j] == '(' { 1 } else { -1 };
                            if nb >= 0 {
                                dp[i][j].insert(nb);
                            }
                        }
                    }
                }
            }
        }
        dp[m-1][n-1].contains(&0)
    }
}

Complexity

  • ⏰ Time complexity: O(m * n * k), where k is the number of possible balances (at most m+n), as we track all possible balances at each cell.
  • 🧺 Space complexity: O(m * n * k), as we store possible balances for each cell.