LeetCode 3665 - Twisted Mirror Path Count

LeetCode Problem 3665

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to count all unique paths from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) of a binary grid where certain cells contain mirrors. The robot can move only right or down, but mirrors change its trajectory in a very specific way: moving right into a mirror moves the robot down, and moving down into a mirror moves the robot right. If a reflection would cause the robot to go out of bounds, the path is invalid. A critical detail is that mirrors can chain-reflect the robot, so a mirror might immediately redirect it again if the robot enters from a certain direction.

The grid is given as an m x n array of integers where 0 represents an empty cell and 1 represents a mirror. The output is the number of valid unique paths modulo 10^9 + 7. Constraints indicate that the grid size can be up to 500 x 500, so any brute-force solution that explores all possible paths without pruning or memoization will be too slow.

Important edge cases include: a mirror in the starting or ending positions is impossible (guaranteed 0), paths that immediately reflect out of bounds, and chains of mirrors that could repeatedly redirect the robot.

Approaches

A naive brute-force solution would explore every path recursively, simulating the robot's movement and reflection for each move. This approach is correct because it directly models the rules of the problem. However, the number of paths can grow exponentially with m and n (roughly O(2^(m+n))), making it infeasible for large grids.

The key observation for an optimal solution is that the problem has overlapping subproblems and optimal substructure, which allows us to use dynamic programming. We can define a DP state dp[i][j][d] where i, j is the cell and d is the direction from which the robot enters (0 = right, 1 = down). This state tracks the number of ways to reach (i, j) coming from a specific direction. Using this DP structure, we can propagate counts efficiently across the grid while handling mirror reflections deterministically.

Algorithm Walkthrough

1. Initialize a 3-dimensional DP table dp[m][n][2], where the last dimension represents the direction the robot entered the cell: 0 for right, 1 for down. This tracks the number of ways to reach each cell from each direction.
2. Set the starting cell (0, 0) to have dp[0][0][0] = 1 and dp[0][0][1] = 1, since the robot can initially choose to move either right or down.
3. Iterate over each cell (i, j) in row-major order. For each direction d, check the number of ways dp[i][j][d].
4. If grid[i][j] is empty (0), propagate the paths in the usual directions: moving right adds to dp[i][j+1][0], and moving down adds to dp[i+1][j][1].
5. If grid[i][j] is a mirror (1), apply reflection rules: moving right into the mirror adds to dp[i+1][j][1], and moving down adds to dp[i][j+1][0]. Skip moves that go out of bounds.
6. Use modulo 10^9 + 7 after each update to prevent overflow.
7. At the end, sum dp[m-1][n-1][0] and dp[m-1][n-1][1] to get the total number of unique paths.

Why it works: The DP table ensures that every possible path is counted exactly once. The direction dimension correctly handles reflections, ensuring paths are counted according to their correct entry direction into each cell.

Python Solution

from typing import List

class Solution:
    MOD = 10**9 + 7
    
    def uniquePaths(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # dp[i][j][d]: number of ways to reach cell (i,j) entering from direction d
        dp = [[[0, 0] for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = dp[0][0][1] = 1  # can start moving either right or down
        
        for i in range(m):
            for j in range(n):
                for d in range(2):
                    if dp[i][j][d] == 0:
                        continue
                    if grid[i][j] == 0:
                        # empty cell: move normally
                        if j + 1 < n:
                            dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][d]) % self.MOD
                        if i + 1 < m:
                            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][d]) % self.MOD
                    else:
                        # mirror: reflect based on entry direction
                        if d == 0 and i + 1 < m:  # moving right into mirror -> down
                            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][d]) % self.MOD
                        elif d == 1 and j + 1 < n:  # moving down into mirror -> right
                            dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][d]) % self.MOD
        
        return (dp[m-1][n-1][0] + dp[m-1][n-1][1]) % self.MOD

Explanation: The DP table uses three dimensions to track cells and entry direction. For empty cells, the robot moves normally; for mirrors, reflections are applied. We skip out-of-bounds moves and use modulo arithmetic to manage large numbers. The sum at the destination gives the total valid paths.

Go Solution

func uniquePaths(grid [][]int) int {
    mod := 1_000_000_007
    m, n := len(grid), len(grid[0])
    dp := make([][][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([][]int, n)
        for j := 0; j < n; j++ {
            dp[i][j] = make([]int, 2)
        }
    }
    
    dp[0][0][0], dp[0][0][1] = 1, 1
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            for d := 0; d < 2; d++ {
                if dp[i][j][d] == 0 {
                    continue
                }
                if grid[i][j] == 0 {
                    if j+1 < n {
                        dp[i][j+1][0] = (dp[i][j+1][0] + dp[i][j][d]) % mod
                    }
                    if i+1 < m {
                        dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][d]) % mod
                    }
                } else {
                    if d == 0 && i+1 < m {
                        dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][d]) % mod
                    } else if d == 1 && j+1 < n {
                        dp[i][j+1][0] = (dp[i][j+1][0] + dp[i][j][d]) % mod
                    }
                }
            }
        }
    }
    
    return (dp[m-1][n-1][0] + dp[m-1][n-1][1]) % mod
}

Go-specific notes: Go uses slices instead of Python lists, and we preallocate the 3D slice. Integer overflow is handled explicitly by modulo arithmetic. The logic is otherwise identical to the Python version.

Worked Examples

Example 1: grid = [[0,1,0],[0,0,1],[1,0,0]]

After filling the table, sum dp[2][2][0] + dp[2][2][1] = 5.

Example 2: `grid = [[