LeetCode Entry

2267. Check if There Is a Valid Parentheses String Path

29.09.2026 hard 2026 kotlin rust

Any balanced braces-path

2267. Check if There Is a Valid Parentheses String Path hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1497

Problem TLDR

Any balanced braces-path

Intuition

Dp choice for each cell to go from top or from the left. Keep open braces balances. Remove negatives.

Approach

• instead of a set we can use the big integer or u128: on opened brace moves every bit to the left, meaning incrementing all at once

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(n)\)

Code

    fun hasValidPath(g: Array<CharArray>) = run {
        val o=Array(102){0.toBigInteger()};o[1] = 1.toBigInteger()
        for (r in g) for (x in r.indices)
            o[x+1] = (o[x] or o[x+1]).shiftLeft(81 - r[x].code * 2)
        o[g[0].size].testBit(0)
    }

    pub fn has_valid_path(g: Vec<Vec<char>>) -> bool {
        let mut d = [0u128; 102]; d[1] = 1;
        for r in &g { for i in 0..r.len() {
            let m = d[i]|d[i+1]; d[i+1] = if r[i]<')' {m<<1} else {m>>1}
        }} d[g[0].len()] % 2 > 0
    }