What is the time complexity of LeetCode 2267. Check if There Is a Valid Parentheses String Path?

The Python solution on this page runs in O(m \times n \times (m + n)).

What is the space complexity of LeetCode 2267. Check if There Is a Valid Parentheses String Path?

The Python solution on this page uses O(m \times n \times (m + n)) auxiliary space.

Check if There Is a Valid Parentheses String Path — LeetCode 2267 Python Solution

HardArrayDynamic ProgrammingMatrix

Problem: #2267
Pattern: Matrix and Grid
Reading time: 4 min
Source: leetcode.com

The 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 ().

Example

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
Output: true
Explanation: The above diagram shows two possible paths that form valid parentheses strings.

Python solution

Python

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        @cache
        def dfs(i: int, j: int, k: int) -> bool:
            d = 1 if grid[i][j] == "(" else -1
            k += d
            if k < 0 or k > m - i + n - j:
                return False
            if i == m - 1 and j == n - 1:
                return k == 0
            for a, b in pairwise((0, 1, 0)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k):
                    return True
            return False

        m, n = len(grid), len(grid[0])
        if (m + n - 1) % 2 or grid[0][0] == ")" or grid[m - 1][n - 1] == "(":
            return False
        return dfs(0, 0, 0)

Complexity

Measure	Complexity
Time	O(m \times n \times (m + n))
Space	O(m \times n \times (m + n)) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2267. Check if There Is a Valid Parentheses String Path is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2267. Check if There Is a Valid Parentheses String Path?: LeetCode 2267. Check if There Is a Valid Parentheses String Path is rated Hard on LeetCode.
What is the time complexity of LeetCode 2267. Check if There Is a Valid Parentheses String Path?: The Python solution on this page runs in O(m \times n \times (m + n)).
What is the space complexity of LeetCode 2267. Check if There Is a Valid Parentheses String Path?: The Python solution on this page uses O(m \times n \times (m + n)) auxiliary space.
What topics does LeetCode 2267. Check if There Is a Valid Parentheses String Path cover?: LeetCode 2267. Check if There Is a Valid Parentheses String Path is tagged Array, Dynamic Programming and Matrix on LeetCode.