Check if There Is a Valid Parentheses String Path

Check if There Is a Valid Parentheses String Path - Problem

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.

Input & Output

Example 1 — Valid Path Exists

$ Input: grid = [["(",")"],["(",")"]]

› Output: true

💡 Note: Path (0,0)→(0,1)→(1,1) gives string "())" which is invalid, but path (0,0)→(1,0)→(1,1) gives string "(()" which is also invalid. However, we need to find "()". Path (0,0)→(0,1) gives "()" which is valid.

Example 2 — No Valid Path

$ Input: grid = [[")","("],["(",")"]]

› Output: false

💡 Note: All paths start with ")" which immediately makes the balance negative, so no valid parentheses string can be formed.

Example 3 — Larger Grid

$ Input: grid = [["(","(",")"],[")",")","("],["(",")",")"]]

› Output: true

💡 Note: There exists at least one path that forms a valid parentheses string by carefully choosing down/right moves.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 100
grid[i][j] is either '(' or ')'

Visualization

Tap to expand

Understanding the Visualization

Grid Input

2D matrix of '(' and ')' characters

Path Constraint

Can only move right or down

Valid Check

Path string must be valid parentheses

Key Takeaway

🎯 Key Insight: Track parentheses balance at each position and ensure it never becomes negative while reaching the destination.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 F Facebook 28

The key insight is to track the balance of parentheses (count of '(' minus count of ')') at each position, ensuring it never goes negative. The optimal approach uses dynamic programming to maintain sets of possible balance values at each cell. Time: O(m*n*k), Space: O(m*n*k) where k is the maximum possible balance.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(2^(m+n))	O(m+n)	Try all possible paths from top-left to bottom-right and validate each
DFS with Memoization	O(mnk)	O(mnk)	Use memoization to avoid recomputing the same state multiple times
Dynamic Programming with Set	O(mnk)	O(mnk)	Use DP to track all possible balance values at each position

Brute Force DFS — Algorithm Steps

Start DFS from (0,0)
For each cell, try moving right and down
Build path string and check validity at the end

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin at (0,0) and explore all paths

Path Building

Build string by concatenating characters along path

Validate

Check if final string is valid parentheses

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValid(char* s) {
    int balance = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(') {
            balance++;
        } else {
            balance--;
            if (balance < 0) return false;
        }
    }
    return balance == 0;
}

bool dfs(char grid[][100], int i, int j, char* path, int pathLen, int m, int n) {
    path[pathLen] = grid[i][j];
    path[pathLen + 1] = '\0';
    
    if (i == m - 1 && j == n - 1) {
        return isValid(path);
    }
    
    if (i >= m || j >= n) return false;
    
    return (i + 1 < m && dfs(grid, i + 1, j, path, pathLen + 1, m, n)) ||
           (j + 1 < n && dfs(grid, i, j + 1, path, pathLen + 1, m, n));
}

bool solution(char grid[][100], int m, int n) {
    char path[200];
    return dfs(grid, 0, 0, path, 0, m, n);
}

int main() {
    // Simplified for demo
    char grid[2][100] = {{'(', ')'}, {'(', ')'}};
    printf(solution(grid, 2, 2) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(m+n))

Each cell has 2 choices (right/down), with m+n-2 decisions total

✓ Linear Growth

Space Complexity

O(m+n)

Recursion stack depth is m+n-1 for the longest path

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler