Check if There Is a Valid Parentheses String Path

Hard
1628.

Check if There Is a Valid Parentheses String Path

Check if There Is a Valid Parentheses String Path is a hard coding problem on arrays, dynamic programming and matrix, asked in Google interviews.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is '(' or ')'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} grid
 * @return {boolean}
 */
var hasValidPath = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Check if There Is a Valid Parentheses String Path

  1. Hint 1

    A path is valid exactly when its running balance (+1 for (, -1 for )) never drops below zero and ends at zero.

  2. 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 most 100 * 100 * 200 states.

  3. Hint 3

    Fill a boolean table can[i][j][b] from the top-left, or run a memoised DFS. Quick rejections: the path length m + n - 1 must 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

  1. If m + n - 1 is odd, return false.
  2. Let can[i][j][b] be true when some path from (0, 0) to (i, j) has balance b after reading grid[i][j], never having gone negative.
  3. Seed can[0][0][1] = true if grid[0][0] == '(' (otherwise nothing is reachable).
  4. For each other cell in row-major order, for each balance b reachable on the cell above or to the left, mark b + 1 or b - 1 here (skipping negatives and balances above m + n).
  5. 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