Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Check if There Is a Valid Parentheses String Path solution and explanation

HardArrayDynamic ProgrammingMatrix7 min read57.2% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Check if There Is a Valid Parentheses String Path
12:59
Weekly Leetcode Contest 292 | 2267. Check if There Is a Valid Parentheses String PathcodingMohan · 12:59 · 1K viewsWatch on YouTube
8 more videos on this problem
  1. Weekly Leetcode Contest 292 | 2267. Check if There Is a Valid Parentheses String PathcodingMohan · 12:59 · 1K views
  2. Check if There Is a Valid Parentheses String Path | Leetcode 2267 | Simple DFS | Live coding sessionCoding Decoded · 6:45 · 1K views
  3. 【每日一题】LeetCode 2267. Check if There Is a Valid Parentheses String PathHuifeng Guan · 31:33 · 928 views
  4. Leetcode 2267. Check if There Is Valid Parentheses String PathThinkCode · 8:47 · 909 views
  5. Check if There Is a Valid Parentheses String Path (Leetcode Weekly 292)Soumya Bhattacharjee · 6:10 · 490 views
  6. 2267. Check if There Is a Valid Parentheses String Path (Leetcode Hard)Programming Live with Larry · 23:40 · 397 views
  7. Leetcode weekly contest 292 - Check if There Is a Valid Parentheses String PathPrakhar Agrawal · 11:22 · 304 views
  8. Leetcode 2267. Check if There Is a Valid Parentheses String Path (dfs + memo)LetsCode · 14:39 · 50 views
  9. LeetCode Hard: 2267. Check if There Is a Valid Parentheses String Pathrobzingcod · 19:53 · 4 views

The 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:

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

Approach overview

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 1: Approach 1: Depth-First Search with Backtracking

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.

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        memo = [[[-1] * (m + n) for _ in range(n)] for _ in range(m)]

        def dfs(r, c, balance):
            if balance < 0:
                return False
            if r >= m or c >= n:
                return False
            balance += 1 if grid[r][c] == '(' else -1
            if r == m - 1 and c == n - 1:
                return balance == 0
            if memo[r][c][balance] != -1:
                return memo[r][c][balance]
            result = dfs(r + 1, c, balance) or dfs(r, c + 1, balance)
            memo[r][c][balance] = result
            return result

        return dfs(0, 0, 0)
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        Integer[][][] memo = new Integer[m][n][201];
        return dfs(grid, 0, 0, 0, memo);
    }

    private boolean dfs(char[][] grid, int r, int c, int bal, Integer[][][] memo) {
        if (bal < 0) return false;
        if (r >= grid.length || c >= grid[0].length) return false;
        bal += (grid[r][c] == '(') ? 1 : -1;
        if (r == grid.length - 1 && c == grid[0].length - 1) return bal == 0;
        if (memo[r][c][bal] != null) return memo[r][c][bal] == 1;
        boolean res = dfs(grid, r + 1, c, bal, memo) || dfs(grid, r, c + 1, bal, memo);
        memo[r][c][bal] = res ? 1 : 0;
        return res;
    }
}
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<vector<int>>> memo(m, vector<vector<int>>(n, vector<int>(201, -1)));
        return dfs(grid, memo, 0, 0, 0);
    }

private:
    bool dfs(vector<vector<char>>& grid, vector<vector<vector<int>>>& memo, int r, int c, int bal) {
        if (bal < 0) return false;
        if (r >= grid.size() || c >= grid[0].size()) return false;
        bal += (grid[r][c] == '(') ? 1 : -1;
        if (r == grid.size() - 1 && c == grid[0].size() - 1) return bal == 0;
        if (memo[r][c][bal] != -1) return memo[r][c][bal];
        bool res = dfs(grid, memo, r + 1, c, bal) || dfs(grid, memo, r, c + 1, bal);
        return memo[r][c][bal] = res;
    }
};
var hasValidPath = function(grid) {
    const m = grid.length, n = grid[0].length;
    const memo = Array.from({ length: m }, () => 
        Array.from({ length: n }, () => new Array(201).fill(-1)));

    const dfs = (r, c, balance) => {
        if (balance < 0) return false;
        if (r >= m || c >= n) return false;
        balance += (grid[r][c] === '(') ? 1 : -1;
        if (r === m - 1 && c === n - 1) return balance === 0;
        if (memo[r][c][balance] !== -1) return memo[r][c][balance] === 1;
        const result = dfs(r + 1, c, balance) || dfs(r, c + 1, balance);
        memo[r][c][balance] = result ? 1 : 0;
        return result;
    }

    return dfs(0, 0, 0);
};
#include <stdbool.h>
#include <string.h>
#include <stdio.h>

bool dfs(char** grid, int m, int n, int row, int col, int balance, bool*** memo) {
    if (row >= m || col >= n || balance < 0) return false;
    if (row == m - 1 && col == n - 1) return balance == 1;
    if (memo[row][col][balance] != -1) return memo[row][col][balance];
    balance += (grid[row][col] == '(') ? 1 : -1;
    bool result = dfs(grid, m, n, row + 1, col, balance, memo) || dfs(grid, m, n, row, col + 1, balance, memo);
    memo[row][col][balance] = result;
    return result;
}

bool hasValidPath(char** grid, int gridSize, int* gridColSize) {
    int n = gridColSize[0];
    bool*** memo = malloc(gridSize * sizeof(bool**));
    for (int i = 0; i < gridSize; i++) {
        memo[i] = malloc(n * sizeof(bool*));
        for (int j = 0; j < n; j++) {
            memo[i][j] = malloc(gridSize + n - 1 * sizeof(bool));
            memset(memo[i][j], -1, gridSize + n - 1);
        }
    }
    return dfs(grid, gridSize, n, 0, 0, 0, memo);
}
public class Solution {
    public bool HasValidPath(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[,,] memo = new int[m, n, 201];

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < 201; k++)
                    memo[i, j, k] = -1;

        bool DFS(int r, int c, int balance) {
            if (balance < 0 || r >= m || c >= n) return false;
            balance += (grid[r][c] == '(') ? 1 : -1;
            if (r == m - 1 && c == n - 1) return balance == 0;
            if (memo[r, c, balance] != -1) return memo[r, c, balance] == 1;
            bool res = DFS(r + 1, c, balance) || DFS(r, c + 1, balance);
            memo[r, c, balance] = res ? 1 : 0;
            return res;
        }

        return DFS(0, 0, 0);
    }
}

Python's implementation utilizes a DFS and memoization (3D list) to recursively ensure parentheses path validity. It explores all possible paths while maintaining balance constraints.

Complexity

The time complexity is O(m * n * (m + n)), and the space complexity is O(m * n * (m + n)) due to the size of the memoization structure which tracks balance counts per cell.

Try this approach in the editor

Approach 2: Approach 2: Dynamic Programming

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

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        dp = [[[False] * (m + n) for _ in range(n)] for _ in range(m)]
        dp[0][0][1] = grid[0][0] == '('
        dp[0][0][0] = grid[0][0] == ')'

        for i in range(m):
            for j in range(n):
                for k in range(i + j + 1):
                    if i > 0 and k - (1 if grid[i][j] == '(' else -1) >= 0:
                        dp[i][j][k] |= dp[i-1][j][k - (1 if grid[i][j] == '(' else -1)]
                    if j > 0 and k - (1 if grid[i][j] == '(' else -1) >= 0:
                        dp[i][j][k] |= dp[i][j-1][k - (1 if grid[i][j] == '(' else -1)]

        return dp[m-1][n-1][0]
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][][] dp = new boolean[m][n][m + n];
        dp[0][0][1] = grid[0][0] == '(';
        dp[0][0][0] = grid[0][0] == ')';

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= i + j + 1; k++) {
                    if (i > 0) {
                        if (k - (grid[i][j] == '(' ? 1 : -1) >= 0)
                            dp[i][j][k] |= dp[i-1][j][k - (grid[i][j] == '(' ? 1 : -1)];
                    }
                    if (j > 0) {
                        if (k - (grid[i][j] == '(' ? 1 : -1) >= 0)
                            dp[i][j][k] |= dp[i][j-1][k - (grid[i][j] == '(' ? 1 : -1)];
                    }
                }
            }
        }

        return dp[m-1][n-1][0];
    }
}
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<bool>>> dp(m, vector<vector<bool>>(n, vector<bool>(m + n)));
        dp[0][0][1] = grid[0][0] == '(';
        dp[0][0][0] = grid[0][0] == ')';

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= i + j + 1; k++) {
                    if (i > 0) {
                        dp[i][j][k] |= k > 0 ? dp[i-1][j][k - (grid[i][j] == '(' ? 1 : -1)] : 0;
                    }
                    if (j > 0) {
                        dp[i][j][k] |= k > 0 ? dp[i][j-1][k - (grid[i][j] == '(' ? 1 : -1)] : 0;
                    }
                }
            }
        }

        return dp[m-1][n-1][0];
    }
};
var hasValidPath = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dp = Array.from({ length: m }, () => 
        Array.from({ length: n }, () => new Array(m + n).fill(false)));
    dp[0][0][1] = grid[0][0] === '(';
    dp[0][0][0] = grid[0][0] === ')';

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k <= i + j; k++) {
                const diff = grid[i][j] === '(' ? 1 : -1;
                if (i > 0 && k - diff >= 0) {
                    dp[i][j][k] |= dp[i - 1][j][k - diff];
                }
                if (j > 0 && k - diff >= 0) {
                    dp[i][j][k] |= dp[i][j - 1][k - diff];
                }
            }
        }
    }

    return dp[m - 1][n - 1][0];
};
#include <stdbool.h>
#include <string.h>

bool hasValidPath(char** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    bool dp[m][n][m + n];
    memset(dp, false, sizeof(dp));
    dp[0][0][1] = grid[0][0] == '(';
    dp[0][0][0] = grid[0][0] == ')';

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k <= i + j + 1; ++k) {
                if (i > 0) {
                    dp[i][j][k] |= k > 0 ? dp[i-1][j][k - (grid[i][j] == '(' ? 1 : -1)] : 0;
                }
                if (j > 0) {
                    dp[i][j][k] |= k > 0 ? dp[i][j-1][k - (grid[i][j] == '(' ? 1 : -1)] : 0;
                }
            }
        }
    }
    return dp[m-1][n-1][0];
}
public class Solution {
    public bool HasValidPath(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        bool[,,] dp = new bool[m, n, m + n];
        dp[0, 0, 1] = grid[0][0] == '(';
        dp[0, 0, 0] = grid[0][0] == ')';

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= i + j; k++) {
                    int diff = (grid[i][j] == '(' ? 1 : -1);
                    if (i > 0 && k - diff >= 0)
                        dp[i, j, k] |= dp[i - 1, j, k - diff];
                    if (j > 0 && k - diff >= 0)
                        dp[i, j, k] |= dp[i, j - 1, k - diff];
                }
            }
        }

        return dp[m - 1, n - 1, 0];
    }
}

The Python implementation leverages DP over recursion for path validation. It builds valid path balance states iteratively, accounting for cell-to-cell transitions in parentheses grid evaluation.

Complexity

With O(m * n * (m + n)) time complexity and space complexity of O(m * n * (m + n)), it efficiently evaluates each possible valid path transition iteratively.

Try this approach in the editor

Approach 3: DFS + Pruning

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.

function hasValidPath(grid: string[][]): boolean {
    const m = grid.length,
        n = grid[0].length;

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

    const vis: boolean[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => Array(m + n).fill(false)),
    );
    const dirs = [1, 0, 1];

    const dfs = (i: number, j: number, k: number): boolean => {
        if (vis[i][j][k]) {
            return false;
        }

        vis[i][j][k] = true;
        k += grid[i][j] === '(' ? 1 : -1;

        if (k < 0 || k > m - i + n - j) {
            return false;
        }

        if (i === m - 1 && j === n - 1) {
            return k === 0;
        }

        for (let d = 0; d < 2; ++d) {
            const x = i + dirs[d],
                y = j + dirs[d + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && dfs(x, y, k)) {
                return true;
            }
        }

        return false;
    };

    return dfs(0, 0, 0);
}
func hasValidPath(grid [][]byte) bool {
	m, n := len(grid), len(grid[0])
	if (m+n-1)%2 == 1 || grid[0][0] == ')' || grid[m-1][n-1] == '(' {
		return false
	}
	vis := make([][][]bool, m)
	for i := range vis {
		vis[i] = make([][]bool, n)
		for j := range vis[i] {
			vis[i][j] = make([]bool, m+n)
		}
	}
	dirs := [3]int{1, 0, 1}
	var dfs func(i, j, k int) bool
	dfs = func(i, j, k int) bool {
		if vis[i][j][k] {
			return false
		}
		vis[i][j][k] = true
		if grid[i][j] == '(' {
			k++
		} else {
			k--
		}
		if k < 0 || k > m-i+n-j {
			return false
		}
		if i == m-1 && j == n-1 {
			return k == 0
		}
		for d := 0; d < 2; d++ {
			x, y := i+dirs[d], j+dirs[d+1]
			if x >= 0 && x < m && y >= 0 && y < n && dfs(x, y, k) {
				return true
			}
		}
		return false
	}
	return dfs(0, 0, 0)
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Depth-First Search with Backtracking

The time complexity is O(m * n * (m + n)), and the space complexity is O(m * n * (m + n)) due to the size of the memoization structure which tracks balance counts per cell.

Approach 2: Dynamic Programming

With O(m * n * (m + n)) time complexity and space complexity of O(m * n * (m + n)), it efficiently evaluates each possible valid path transition iteratively.

DFS + Pruning–

Complexity analysis

ApproachTimeSpaceWhen to Use
Depth-First Search with BacktrackingO(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

Frequently asked questions

Is Check if There Is a Valid Parentheses String Path easy or hard?

LeetCode classifies this problem as Hard. It combines grid traversal, parentheses validation, and state-based dynamic programming, which requires careful pruning and efficient state representation.

Check if There Is a Valid Parentheses String Path Python/Java solution

Most implementations maintain a balance counter while traversing the grid. Python solutions typically use DFS with memoization or DP sets, while Java solutions often use boolean DP arrays indexed by row, column, and balance.

How to solve Check if There Is a Valid Parentheses String Path in O(n)?

A strict O(n) solution does not exist because the algorithm must examine grid states and balance values along multiple paths. The closest efficient approach uses dynamic programming with state pruning, resulting in O(m*n*(m+n)) time.

What is the best approach for Check if There Is a Valid Parentheses String Path?

Dynamic programming with state tracking (row, column, balance) is the most efficient approach. It stores the number of unmatched '(' while traversing the grid and avoids recomputation of identical states. The complexity is O(m*n*(m+n)), which is significantly better than exploring all paths with DFS.

Is Check if There Is a Valid Parentheses String Path asked at Google/Amazon/Meta?

Grid dynamic programming and parentheses validation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants combining matrix traversal with state constraints are common in senior-level coding rounds.

What data structure is used in Check if There Is a Valid Parentheses String Path?

The main structures include a 2D grid (matrix) to represent the board and a DP table or set to track possible parentheses balances at each cell. Some implementations also use recursion stacks for DFS exploration.

What is the time complexity of Check if There Is a Valid Parentheses String Path?

The optimal dynamic programming solution runs in O(m*n*(m+n)) time because each cell can maintain multiple possible balance states up to the path length. Space complexity is also O(m*n*(m+n)) if all states are stored.

Comments

Next problem · similarCheck if There is a Valid Path in a GridMedium
Now write it yourselfClose this page and solve Check if There Is a Valid Parentheses String Path in the editor, without looking.
Practise Check if There Is a Valid Parentheses String Path