We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if There Is a Valid Parentheses String Path

Number: 2349

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an m x n grid containing only '(' and ')', determine if there exists a path from the top-left to the bottom-right cell (only moving down or right) such that the concatenated characters form a valid parentheses string. A valid parentheses string never has more ')' than '(' at any point, and must finally balance to zero.

Key Insights

  • Use dynamic programming (DP) to track feasible "balance" states (number of unmatched '(') along each cell.
  • Transition: moving right or down updates the balance (+1 for '(' and -1 for ')'). Discard states that become negative as they represent invalid sequences.
  • At the bottom-right cell, a valid path must yield a balance of zero.
  • The number of states can be pruned by only tracking valid, non-negative balances.

Space and Time Complexity

Time Complexity: O(m * n * k) where k is limited by the maximum balance (which is O(m+n) in the worst case). Space Complexity: O(m * n * k) for storing the set of possible balances at each grid cell.

Solution

We solve the problem using a dynamic programming approach where each cell [i][j] stores a set of possible balance values derived from all valid paths reaching that cell. Starting from the top-left, update the balance as you move right or down. If at any point the calculated balance is negative, that state is discarded. At the end, if the set at the bottom-right cell contains zero, then there exists a valid path.

Code Solutions

def hasValidPath(grid):
    m, n = len(grid), len(grid[0])
    # Create a 2D list of sets storing possible balances at each cell
    dp = [[set() for _ in range(n)] for _ in range(m)]
    
    # Initialize the starting cell; if it starts with ')', no valid path exists.
    if grid[0][0] == '(':
        dp[0][0].add(1)
    else:
        return False
    
    for i in range(m):
        for j in range(n):
            for balance in dp[i][j]:
                # Move right if possible
                if j + 1 < n:
                    new_balance = balance + (1 if grid[i][j+1] == '(' else -1)
                    if new_balance >= 0:
                        dp[i][j+1].add(new_balance)
                # Move down if possible
                if i + 1 < m:
                    new_balance = balance + (1 if grid[i+1][j] == '(' else -1)
                    if new_balance >= 0:
                        dp[i+1][j].add(new_balance)
    # Check if a valid path ends with balance 0
    return 0 in dp[m-1][n-1]

# Example usage:
grid = [["(", "(", "("], [")", "(", ")"], ["(", "(", ")"], ["(", "(", ")"]]
print(hasValidPath(grid))
← Back to All Questions