Skip to main content
Talentd

Check if There Is a Valid Parentheses String Path - Solution & Explanation

HardArrayDynamic ProgrammingMatrix25 min readAsked at: Google
Practice this problem

Problem Statement

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

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

Detailed 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

Video Solution

Weekly Leetcode Contest 292 | 2267. Check if There Is a Valid Parentheses String Path • codingMohan • 1,400 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Check if There Is a Valid Parentheses String Path with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if a Parentheses String Can Be Valid

Next

Check if There is a Valid Path in a Grid