Scale Engineer

Check if There Is a Valid Parentheses String Path

Hard
#2065Time: 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`.
Patterns
Dynamic Programming
Data structures
ArrayMatrix

Prompt

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:

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.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is either '(' or ')'.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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.

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;    }}

Complexity

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`.

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem