A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
().AB (A concatenated with B), where A and B are valid parentheses strings.(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:
(0, 0).(m - 1, n - 1).Return true if there exists a valid parentheses string path in the grid. Otherwise, return false.
Example 1:
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:
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.lengthn == grid[i].length1 <= m, n <= 100grid[i][j] is either '(' or ')'.Problem Overview: You are given an m x n grid containing only '(' and ')'. Starting at the top-left cell, move only right or down until you reach the bottom-right cell. The characters along the path must form a valid parentheses string. The task is to check if at least one such path exists.
Approach 1: Depth-First Search with Backtracking (O(2^(m+n)) time, O(m+n) space)
Run a recursive DFS from (0,0) while maintaining a running balance of parentheses. Increment the balance for '(' and decrement for ')'. If the balance ever becomes negative, stop exploring that path because a valid parentheses string can never have more closing brackets than opening ones at any prefix. Continue exploring by moving right or down until reaching (m-1,n-1). The path is valid only if the final balance equals zero. Backtracking explores all possible paths but pruning invalid balances removes many branches.
This approach is straightforward and useful for understanding the constraint that the prefix must always stay valid. However, many overlapping subproblems appear because the same cell can be reached with the same balance multiple times.
Approach 2: Dynamic Programming (O(m*n*(m+n)) time, O(m*n*(m+n)) space)
Dynamic programming avoids recomputing states by tracking possible balances at each grid cell. Let dp[r][c] store the set (or boolean states) of balances achievable when reaching cell (r,c). When moving from top or left, update the balance depending on whether the cell contains '(' or ')'. Discard any state where the balance becomes negative or exceeds the remaining path length. The final cell is valid if balance 0 can be reduced to exactly 0 at the end.
The key insight: a valid parentheses path depends only on the current position and the number of unmatched opening brackets. By caching these states, the algorithm converts exponential exploration into polynomial time. This technique combines grid traversal from a matrix with state tracking typical in dynamic programming problems. The grid itself is simply stored as an array.
Recommended for interviews: Start by explaining the DFS with balance pruning to show you understand the constraints of valid parentheses. Then move to the dynamic programming state (row, col, balance), which eliminates repeated work and achieves the expected polynomial complexity. Interviewers usually expect the DP formulation for a Hard grid + parentheses validation problem.
This approach involves using a depth-first search (DFS) strategy to explore the grid recursively. Maintain a counter to track the balance of parentheses at each cell from the start. The balance cannot be negative, and only a balance of zero should be reached at the last cell for a successful path. With DFS, we'll check each possible move (down or right) recursively until we reach the end or determine a path is invalid.
This C solution uses a recursive DFS to navigate the grid. A three-dimensional memoization array is used to store already computed balances for particular cells to avoid redundant calculations. The function moves down or right recursively while checking the balance of parentheses.
The time complexity is O(m * n * (m + n)) due to the use of memoization to limit evaluations of each state. The space complexity is O(m * n * (m + n)) due to the memoization table storing intermediate results.
This approach relies on dynamic programming (DP) to determine the possibility of forming a valid parentheses path. By using a three-dimensional DP table, track which balance might result in a valid progression at each cell. The DP solution builds up information iteratively and bases its decisions on prior results (moving right or down in the grid).
This C solution uses a dynamic programming approach. A 3D array keeps track of valid character balances, updating states from each cell's prior states both upwards and to the left. It builds potential valid paths through iteration.
Time complexity is O(m * n * (m + n)), where each DP transition is processed iteratively. Space complexity is O(m * n * (m + n)) due to the 3D DP table holding balance state information.
Let m be the number of rows and n be the number of columns in the matrix.
If m + n - 1 is odd, or the parentheses in the top-left and bottom-right corners do not match, then there is no valid path, and we directly return false.
Otherwise, we design a function dfs(i, j, k), which represents whether there is a valid path starting from (i, j) with the current balance of parentheses being k. The balance k is defined as the number of left parentheses minus the number of right parentheses in the path from (0, 0) to (i, j).
If the balance k is less than 0 or greater than m + n - i - j, then there is no valid path, and we directly return false. If (i, j) is the bottom-right cell, then there is a valid path only if k = 0. Otherwise, we enumerate the next cell (x, y) of (i, j). If (x, y) is a valid cell and dfs(x, y, k) is true, then there is a valid path.
The time complexity is O(m times n times (m + n)), and the space complexity is O(m times n times (m + n)). Here, m and n are the number of rows and columns in the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search with Backtracking | The time complexity is O(m * n * (m + n)) due to the use of memoization to limit evaluations of each state. The space complexity is O(m * n * (m + n)) due to the memoization table storing intermediate results. |
| Approach 2: Dynamic Programming | Time complexity is O(m * n * (m + n)), where each DP transition is processed iteratively. Space complexity is O(m * n * (m + n)) due to the 3D DP table holding balance state information. |
| DFS + Pruning | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search with Backtracking | O(2^(m+n)) | O(m+n) | Useful for understanding path exploration and parentheses balance constraints |
| Dynamic Programming (State: row, col, balance) | O(m*n*(m+n)) | O(m*n*(m+n)) | Preferred approach for large grids; removes repeated subproblems |
Weekly Leetcode Contest 292 | 2267. Check if There Is a Valid Parentheses String Path • codingMohan • 1,346 views views
Watch 7 more video solutions →Practice Check if There Is a Valid Parentheses String Path with our built-in code editor and test cases.
Practice on FleetCode