Check if There Is a Valid Parentheses String Path — Solution
Check if There Is a Valid Parentheses String Path solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if There Is a Valid Parentheses String Path is a hard coding problem on arrays, dynamic programming and matrix, asked in Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string of parentheses is valid if it is empty, or is AB with A and B valid, or is (A) with A valid — in other words, every ( is matched by a later ).
You are given an m x n grid grid as m strings of length n, each character '(' or ')'. A valid path starts at the top-left cell (0, 0), ends at the bottom-right cell (m - 1, n - 1), only ever moves down or right, and the characters it passes over (including both ends) form a valid parentheses string.
Return true if some valid path exists, otherwise false.
Example 1
Input: grid = ["(((",")()","(()","(()"]
Output: true
Explanation: Right, right, down, down, down reads `((()))`, which is valid.
Example 2
Input: grid = ["))","(("]
Output: false
Explanation: Both paths start with `)`, so neither can be valid.
Example 3
Input: grid = ["()"]
Output: true
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 100grid[i][j] is '(' or ')'
Hints for Check if There Is a Valid Parentheses String Path
Hint 1
A path is valid exactly when its running balance (
+1for(,-1for)) never drops below zero and ends at zero.Hint 2
Two paths reaching the same cell with the same balance are interchangeable for the rest of the walk. So the state is
(row, col, balance)— at most100 * 100 * 200states.Hint 3
Fill a boolean table
can[i][j][b]from the top-left, or run a memoised DFS. Quick rejections: the path lengthm + n - 1must be even, the start must be(and the end).
How to solve Check if There Is a Valid Parentheses String Path
Validity of a parentheses string only depends on its running balance. So instead of paths, track which balances can be standing on each cell: a 3D reachability DP over (row, column, balance).
Approach
- If
m + n - 1is odd, returnfalse. - Let
can[i][j][b]be true when some path from(0, 0)to(i, j)has balancebafter readinggrid[i][j], never having gone negative. - Seed
can[0][0][1] = trueifgrid[0][0] == '('(otherwise nothing is reachable). - For each other cell in row-major order, for each balance
breachable on the cell above or to the left, markb + 1orb - 1here (skipping negatives and balances abovem + n). - Return
can[m-1][n-1][0].
Why it works
Any two partial paths that reach the same cell with the same balance can be completed by exactly the same suffixes, so keeping one boolean per (cell, balance) loses nothing. The DP considers every move into every cell, so it marks exactly the balances some valid prefix can have.
Complexity
- Time —
O(m * n * (m + n)) - Space —
O(n * (m + n)) with two rows
Pitfalls
- A prefix that ever goes negative can never recover into a valid string — drop it immediately instead of tracking negative balances.
- Searching paths one by one is exponential; the balance is the only thing that matters.
- A balance larger than the number of cells left can never return to zero — capping it keeps the table small.
Reference solution
Python
from typing import List
def hasValidPath(grid: List[str]) -> bool:
m, n = len(grid), len(grid[0])
if (m + n - 1) % 2 == 1 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(':
return False
L = m + n
prev = None
for i in range(m):
cur = [[False] * (L + 1) for _ in range(n)]
for j in range(n):
d = 1 if grid[i][j] == '(' else -1
if i == 0 and j == 0:
cur[0][1] = True
continue
here = cur[j]
up = prev[j] if i > 0 else None
left = cur[j - 1] if j > 0 else None
for b in range(L + 1):
if (up is not None and up[b]) or (left is not None and left[b]):
nb = b + d
if 0 <= nb <= L:
here[nb] = True
prev = cur
return prev[n - 1][0]Java
public static boolean hasValidPath(String[] grid) {
int m = grid.length, n = grid[0].length();
if ((m + n - 1) % 2 == 1 || grid[0].charAt(0) == ')' || grid[m - 1].charAt(n - 1) == '(') return false;
int L = m + n, W = L + 1;
boolean[] prev = new boolean[n * W];
for (int i = 0; i < m; i++) {
boolean[] cur = new boolean[n * W];
for (int j = 0; j < n; j++) {
int d = grid[i].charAt(j) == '(' ? 1 : -1;
if (i == 0 && j == 0) { cur[1] = true; continue; }
for (int b = 0; b <= L; b++) {
if ((i > 0 && prev[j * W + b]) || (j > 0 && cur[(j - 1) * W + b])) {
int nb = b + d;
if (nb >= 0 && nb <= L) cur[j * W + nb] = true;
}
}
}
prev = cur;
}
return prev[(n - 1) * W];
}C++
bool hasValidPath(vector<string>& grid) {
int m = grid.size(), n = grid[0].size();
if ((m + n - 1) % 2 == 1 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false;
int L = m + n, W = L + 1;
vector<char> prev(n * W, 0);
for (int i = 0; i < m; i++) {
vector<char> cur(n * W, 0);
for (int j = 0; j < n; j++) {
int d = grid[i][j] == '(' ? 1 : -1;
if (i == 0 && j == 0) { cur[1] = 1; continue; }
for (int b = 0; b <= L; b++) {
if ((i > 0 && prev[j * W + b]) || (j > 0 && cur[(j - 1) * W + b])) {
int nb = b + d;
if (nb >= 0 && nb <= L) cur[j * W + nb] = 1;
}
}
}
prev = cur;
}
return prev[(n - 1) * W];
}JavaScript
var hasValidPath = function(grid) {
var m = grid.length, n = grid[0].length;
if ((m + n - 1) % 2 === 1 || grid[0][0] === ')' || grid[m - 1][n - 1] === '(') return false;
var L = m + n, W = L + 1, prev = null;
for (var i = 0; i < m; i++) {
var cur = new Array(n * W).fill(false);
for (var j = 0; j < n; j++) {
var d = grid[i][j] === '(' ? 1 : -1;
if (i === 0 && j === 0) { cur[1] = true; continue; }
for (var b = 0; b <= L; b++) {
if ((i > 0 && prev[j * W + b]) || (j > 0 && cur[(j - 1) * W + b])) {
var nb = b + d;
if (nb >= 0 && nb <= L) cur[j * W + nb] = true;
}
}
}
prev = cur;
}
return prev[(n - 1) * W];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming