LeetCode 2267 - Check if There Is a Valid Parentheses String Path

This problem is asking us to determine whether there exists a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) of a 2D grid containing only '(' and ')' characters, such that the sequence of characters along the path forms a valid parentheses string.

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 2267

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem is asking us to determine whether there exists a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) of a 2D grid containing only '(' and ')' characters, such that the sequence of characters along the path forms a valid parentheses string. The path is constrained to only move right or down at each step.

A valid parentheses string is defined recursively: either it is "()", or it is the concatenation of two valid strings, or it is a valid string enclosed in parentheses. In essence, this is the classical definition of well-formed parentheses.

The input grid is a matrix of size m x n with 1 <= m, n <= 100. Each cell contains either '(' or ')'. The output is a boolean: true if a valid parentheses string path exists, otherwise false.

Key constraints and observations are:

  1. The length of the path from (0,0) to (m-1,n-1) is always m + n - 1. This means the resulting parentheses string must have even length, because a valid parentheses string must have the same number of opening and closing brackets.
  2. At any point along a path, the number of closing brackets ) encountered cannot exceed the number of opening brackets (; otherwise, it is impossible to form a valid parentheses string from that point onward.
  3. Edge cases that could trip up a naive solution include grids where the first or last cell is ')' or '(', respectively, as these immediately make a valid path impossible. Very narrow grids (1 row or 1 column) are also edge cases, as they allow only a single path.

Approaches

Brute Force

A brute force approach would attempt to enumerate all possible paths from (0,0) to (m-1,n-1). For each path, it would build the resulting parentheses string and check if it is valid. This approach would involve a depth-first search (DFS) exploring every possible combination of moves down and right.

Although correct, the brute force method is infeasible for m, n up to 100. The number of paths from top-left to bottom-right is combinatorial, specifically C(m+n-2, m-1), which grows exponentially.

Optimized Approach

The key insight is that we do not need to store the full parentheses string for every path. Instead, we can maintain a running balance of open parentheses:

  • Increment balance by 1 for '('.
  • Decrement balance by 1 for ')'.

The balance represents the net number of unmatched '(' encountered so far. For a path to remain potentially valid:

  1. Balance must never be negative.
  2. Balance must be zero at the bottom-right cell.

Since multiple paths can reach the same cell with different balances, we can use dynamic programming (DP) to track all possible balances at each cell efficiently. Specifically, we maintain a set of balances for each cell based on the balances from its top and left neighbors.

This avoids recomputation and ensures correctness while staying within feasible time and space complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Explore all paths recursively and check validity
Optimal (DP with balance) O(m * n * (m+n)) O(m * n * (m+n)) Track all feasible balances at each cell using sets

Algorithm Walkthrough

  1. Initial Check: If grid[0][0] is ')', return false immediately. Similarly, if grid[m-1][n-1] is '(', return false.
  2. DP Table Setup: Create a 2D array dp where each cell holds a set of feasible balances at that cell.
  3. Initialize DP: Set dp[0][0] = {1} if grid[0][0] is '(' or {0} if it were ')' (though initial check prevents this).
  4. Iterate through the grid: For each cell (i,j), combine the balances from the top (i-1,j) and left (i,j-1) neighbors. For each balance b:
  • If the current cell is '(', add b+1 to the current cell's set.
  • If the current cell is ')', add b-1 to the current cell's set only if b > 0.
  1. Prune invalid balances: At each step, ignore negative balances because they cannot lead to valid strings.
  2. Check result: After processing all cells, check if balance 0 exists in dp[m-1][n-1]. Return true if it does, otherwise false.

Why it works: The DP maintains an invariant that dp[i][j] contains all balances that are achievable along any valid path to (i,j). Negative balances are discarded, ensuring that only potentially valid paths are considered. This guarantees correctness.

Python Solution

from typing import List

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        if grid[0][0] == ')' or grid[m-1][n-1] == '(':
            return False
        
        dp = [[set() for _ in range(n)] for _ in range(m)]
        dp[0][0].add(1)
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                current = set()
                if i > 0:
                    for b in dp[i-1][j]:
                        if grid[i][j] == '(':
                            current.add(b + 1)
                        elif b > 0:
                            current.add(b - 1)
                if j > 0:
                    for b in dp[i][j-1]:
                        if grid[i][j] == '(':
                            current.add(b + 1)
                        elif b > 0:
                            current.add(b - 1)
                dp[i][j] = current
        return 0 in dp[m-1][n-1]

Explanation: We iterate over the grid, updating the set of feasible balances from the top and left neighbors. We increment the balance for '(' and decrement for ')' only if positive. Finally, we check if zero balance is reachable at the bottom-right.

Go Solution

func hasValidPath(grid [][]byte) bool {
    m, n := len(grid), len(grid[0])
    if grid[0][0] == ')' || grid[m-1][n-1] == '(' {
        return false
    }
    
    dp := make([][]map[int]struct{}, m)
    for i := range dp {
        dp[i] = make([]map[int]struct{}, n)
        for j := range dp[i] {
            dp[i][j] = make(map[int]struct{})
        }
    }
    dp[0][0][1] = struct{}{}
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 {
                continue
            }
            current := make(map[int]struct{})
            if i > 0 {
                for b := range dp[i-1][j] {
                    if grid[i][j] == '(' {
                        current[b+1] = struct{}{}
                    } else if b > 0 {
                        current[b-1] = struct{}{}
                    }
                }
            }
            if j > 0 {
                for b := range dp[i][j-1] {
                    if grid[i][j] == '(' {
                        current[b+1] = struct{}{}
                    } else if b > 0 {
                        current[b-1] = struct{}{}
                    }
                }
            }
            dp[i][j] = current
        }
    }
    _, ok := dp[m-1][n-1][0]
    return ok
}

Go-specific notes: In Go, sets are implemented using map[int]struct{}. The logic mirrors Python, iterating over top and left neighbors and updating balances accordingly.

Worked Examples

Example 1:

Grid:

( ( (
) ( )
( ( )
( ( )
  • Initialize dp[0][0] = {1}.
  • Cell (0,1): add '(' → balance 2.
  • Cell (0,2): add '(' → balance 3.
  • Cell (1,0): add ')' → balance 0.
  • Continue this process for all cells.
  • dp[3][2] contains 0 → return true.

Example 2:

Grid:

) )
( (
  • Initial check fails: grid[0][0] = ')' → return false.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * (m+n)) Each cell considers balances up to m+n (maximum path length) from two neighbors
Space O(m * n * (