Watch 8 video solutions for Check if There Is a Valid Parentheses String Path, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by codingMohan has 1,346 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |