Daily LeetCode - by Vítor Belim

Description

You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Solutions

This code determines if there's a valid path of connected pipes from the top-left to bottom-right corner of a grid. Each cell contains a pipe type (1-6), where the map object defines which directions each pipe connects (up, right, down, left). The algorithm uses depth-first search (DFS) to explore paths, tracking the direction you enter each cell and ensuring the pipe at that cell has an opening in that direction. When visiting a cell, it checks all available directions you can exit from (avoiding backtracking), and uses a seen array with backtracking — marking cells as visited during exploration but unmarking them to allow alternative paths. The function starts from position (0, 0) and tries entering from all four directions to find if any leads to the bottom-right corner (m-1, n-1).

Language: javascript(2026-04-27 08:51)DONE

CPU Performance94.44%

Memory Performance61.11%

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var hasValidPath = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    // up, right, down, left
    const map = {
        1: [false, true, false, true],
        2: [true, false, true, false],
        3: [false, false, true, true],
        4: [false, true, true, false],
        5: [true, false, false, true],
        6: [true, true, false, false],
    };
    const seen = Array.from({ length: m }, () => Array(n).fill(false));

    const dfs = (r, c, dir) => {
        if (r < 0 || r >= m || c < 0 || c >= n) return false;
        if (!map[grid[r][c]][dir]) return false;
        if (r === m - 1 && c === n - 1) return true;
        if (seen[r][c]) return false;

        seen[r][c] = true;

        let res = false;

        if (dir !== 0 && map[grid[r][c]][0]) res = dfs(r - 1, c, 2);
        if (dir !== 1 && map[grid[r][c]][1]) res = dfs(r, c + 1, 3);
        if (dir !== 2 && map[grid[r][c]][2]) res = dfs(r + 1, c, 0);
        if (dir !== 3 && map[grid[r][c]][3]) res = dfs(r, c - 1, 1);

        seen[r][c] = false;

        return res;
    };

    return dfs(0, 0, 0) || dfs(0, 0, 1) || dfs(0, 0, 2) || dfs(0, 0, 3);
};

Description

Solutions

AI Explanation