3665. Twisted Mirror Path Count - Solution

The problem

Given an m x n binary grid grid where:

grid[i][j] == 0 represents an empty cell, and
grid[i][j] == 1 represents a mirror.

A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). It can move only right or down. If the robot attempts to move into a mirror cell, it is reflected before entering that cell:

If it tries to move right into a mirror, it is turned down and moved into the cell directly below the mirror.
If it tries to move down into a mirror, it is turned right and moved into the cell directly to the right of the mirror.

If this reflection would cause the robot to move outside the grid boundaries, the path is considered invalid and should not be counted.

Return the number of unique valid paths from (0, 0) to (m - 1, n - 1).

Since the answer may be very large, return it modulo 10⁹ + 7.

Note: If a reflection moves the robot into a mirror cell, the robot is immediately reflected again based on the direction it used to enter that mirror: if it entered while moving right, it will be turned down; if it entered while moving down, it will be turned right. This process will continue until either the last cell is reached, the robot moves out of bounds or the robot moves to a non-mirror cell.

Example 1:

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

Output: 5

Explanation:

Number	Full Path
1	(0, 0) → (0, 1) [M] → (1, 1) → (1, 2) [M] → (2, 2)
2	(0, 0) → (0, 1) [M] → (1, 1) → (2, 1) → (2, 2)
3	(0, 0) → (1, 0) → (1, 1) → (1, 2) [M] → (2, 2)
4	(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2)
5	(0, 0) → (1, 0) → (2, 0) [M] → (2, 1) → (2, 2)

[M] indicates the robot attempted to enter a mirror cell and instead reflected.

Example 2:

Input: grid = [[0,0],[0,0]]

Output: 2

Explanation:

Number	Full Path
1	(0, 0) → (0, 1) → (1, 1)
2	(0, 0) → (1, 0) → (1, 1)

Example 3:

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

Output: 1

Explanation:

Number	Full Path
1	(0, 0) → (0, 1) [M] → (1, 1) [M] → (1, 2)

(0, 0) → (1, 0) [M] → (1, 1) [M] → (2, 1) goes out of bounds, so it is invalid.

Constraints:

m == grid.length
n == grid[i].length
2 <= m, n <= 500
grid[i][j] is either 0 or 1.
grid[0][0] == grid[m - 1][n - 1] == 0

Approach overview

Problem Overview: You are given a matrix where each cell may contain a mirror that twists the direction of movement. Starting from the top-left cell, you need to count how many valid ways reach the bottom-right cell while respecting how mirrors redirect the path.

Approach 1: Brute Force DFS Traversal (Exponential Time, O(2^(m+n)) time, O(m+n) space)

The most direct way is to simulate every possible path from the start cell. At each position, you follow the allowed movement determined by the mirror orientation in that cell. A recursive DFS explores both possible directions whenever the mirror allows branching. This approach is useful for understanding how the mirror redirection affects movement across the matrix. However, many subproblems repeat because different paths often reach the same cell with identical conditions.

Approach 2: DFS with Memoization (Dynamic Programming) (O(m*n) time, O(m*n) space)

Instead of recomputing the number of ways from the same cell repeatedly, store results in a memo table. When DFS reaches a cell (i, j), compute the number of valid paths from that state once and cache it. If the same state appears again, return the stored value immediately. This converts the exponential recursion into a linear number of states equal to the number of cells. The idea mirrors classic grid path counting but adjusts transitions depending on the mirror orientation stored in the grid. Memoization works well here because the number of unique states in the dynamic programming formulation is bounded by m * n.

Approach 3: Bottom-Up DP on the Grid (O(m*n) time, O(m*n) space)

A tabulation approach builds the solution iteratively. Create a DP table where dp[i][j] represents the number of ways to reach cell (i, j). Initialize the start cell with 1. Then iterate through the grid row by row. For each cell, propagate its path count to the next cell(s) determined by the mirror orientation. For example, a mirror may redirect the path to the right neighbor or the cell below. This avoids recursion and gives predictable performance. Since the grid structure is fixed, each state contributes to at most two transitions, making the total work proportional to the number of cells.

Approach 4: Space Optimized DP (O(m*n) time, O(n) space)

If transitions only depend on the current row and the next row, the DP table can be compressed into a rolling array. Instead of storing the entire m x n table, maintain only the current row and update values while iterating through the grid. This technique is common in array-based grid DP problems where dependencies are limited to adjacent cells.

Recommended for interviews: The bottom-up dynamic programming approach is usually what interviewers expect. A brute force DFS demonstrates that you understand the path rules and mirror behavior, but the DP optimization shows you recognize overlapping subproblems and can reduce the complexity to O(m*n).

Approach 1: Dynamic Programming

Thinking

Without mirrors, paths from the top-left to the bottom-right that only step right or down can be counted cell by cell. Sides reach 500, so listing every path grows exponentially and does not fit.

A mirror bends the direction. Entering to the right turns the robot downward, entering downward turns it right, a chain of mirrors bends again at once, and a step that leaves the board is not counted. An arrival count alone no longer says which way the next step must go.

The robot never moves left or up, so the cells have no cycles. Each cell only needs the number of ways that leave it to the right and the number that leave it downward. On an empty cell both equal the sum of the left and upper inflows; on a mirror the two inflows are swapped.

Fill an m times n table from left to right, row by row. The rightward component of the left neighbor and the downward component of the cell above are already known. The origin has no predecessor, so it is seeded with 1 way. The destination is an empty cell, and either component there is the answer.

We define f[i][j][0] as the number of ways to leave cell (i, j) to the right, and f[i][j][1] as the number of ways to leave downward. Every value is taken modulo 10^9+7.

Let r be the number of ways to enter (i, j) from the left, and d the number of ways to enter from above. If j > 0, then r = f[i][j - 1][0]; otherwise r = 0. If i > 0, then d = f[i - 1][j][1]. The origin has no predecessor, so set d = 1 there. Every other cell in the first row has no cell above, so d = 0.

On an empty cell, every path that arrives may continue either right or down, so both outgoing counts equal r + d:

$f[i][j][0] = f[i][j][1] = (r + d) bmod (10^9+7).

On a mirror, a path that enters from above is reflected to the right, and a path that enters from the left is reflected downward. The path does not stop on the mirror:

f[i][j][0] = d, \quad f[i][j][1] = r.

A reflection that crosses the border has no successor and is dropped. The problem guarantees grid[0][0] = grid[m - 1][n - 1] = 0, so both components at the destination equal the number of ways to arrive. Return f[m - 1][n - 1][0].

Compute cells in increasing row order, and from left to right inside a row. Each cell depends only on the left neighbor and the cell above, both of which are already filled.

The time complexity is O(mn) and the space complexity is O(mn), where m and n$ are the number of rows and columns.

Python

class Solution:
    def uniquePaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        f = [[[0, 0] for _ in range(n)] for _ in range(m)]
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                r = f[i][j - 1][0] if j else 0
                d = f[i - 1][j][1] if i else 0
                if i == 0 and j == 0:
                    d = 1
                if x == 1:
                    f[i][j] = [d, r]
                else:
                    s = (r + d) % mod
                    f[i][j] = [s, s]
        return f[-1][-1][0]

Java

class Solution {
    public int uniquePaths(int[][] grid) {
        final int mod = (int) 1e9 + 7;
        int m = grid.length, n = grid[0].length;
        int[][][] f = new int[m][n][2];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int r = j > 0 ? f[i][j - 1][0] : 0;
                int d = i > 0 ? f[i - 1][j][1] : 0;
                if (i == 0 && j == 0) {
                    d = 1;
                }
                if (grid[i][j] == 1) {
                    f[i][j][0] = d;
                    f[i][j][1] = r;
                } else {
                    int s = (r + d) % mod;
                    f[i][j][0] = f[i][j][1] = s;
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
}

C++

class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const int mod = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        vector<vector<array<int, 2>>> f(m, vector<array<int, 2>>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int r = j > 0 ? f[i][j - 1][0] : 0;
                int d = i > 0 ? f[i - 1][j][1] : 0;
                if (i == 0 && j == 0) {
                    d = 1;
                }
                if (grid[i][j] == 1) {
                    f[i][j] = {d, r};
                } else {
                    int s = (r + d) % mod;
                    f[i][j] = {s, s};
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
};

TypeScript

function uniquePaths(grid: number[][]): number {
    const mod = 1e9 + 7;
    const m = grid.length;
    const n = grid[0].length;
    const f: number[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => [0, 0]),
    );
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let r = j > 0 ? f[i][j - 1][0] : 0;
            let d = i > 0 ? f[i - 1][j][1] : 0;
            if (i === 0 && j === 0) {
                d = 1;
            }
            if (grid[i][j] === 1) {
                f[i][j] = [d, r];
            } else {
                const s = (r + d) % mod;
                f[i][j] = [s, s];
            }
        }
    }
    return f[m - 1][n - 1][0];
}

func uniquePaths(grid [][]int) int {
	const mod = int(1e9 + 7)
	m, n := len(grid), len(grid[0])
	f := make([][][2]int, m)
	for i := range f {
		f[i] = make([][2]int, n)
	}
	for i, row := range grid {
		for j, x := range row {
			r, d := 0, 0
			if j > 0 {
				r = f[i][j-1][0]
			}
			if i > 0 {
				d = f[i-1][j][1]
			}
			if i == 0 && j == 0 {
				d = 1
			}
			if x == 1 {
				f[i][j] = [2]int{d, r}
			} else {
				s := (r + d) % mod
				f[i][j] = [2]int{s, s}
			}
		}
	}
	return f[m-1][n-1][0]
}

Rust

impl Solution {
    pub fn unique_paths(grid: Vec<Vec<i32>>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let m = grid.len();
        let n = grid[0].len();
        let mut f = vec![vec![(0i32, 0i32); n]; m];
        for i in 0..m {
            for j in 0..n {
                let r = if j > 0 { f[i][j - 1].0 } else { 0 };
                let mut d = if i > 0 { f[i - 1][j].1 } else { 0 };
                if i == 0 && j == 0 {
                    d = 1;
                }
                f[i][j] = if grid[i][j] == 1 {
                    (d, r)
                } else {
                    let s = (r + d) % MOD;
                    (s, s)
                };
            }
        }
        f[m - 1][n - 1].0
    }
}

Try this approach in the editor

Approach 2: Dynamic Programming (Space Optimization)

Thinking

In Solution 1, f[i][j] reads only the rightward flow of the cell to its left on the same row, and the downward flow of the cell above in the same column. Once a row is finished, earlier rows are never read again.

A rolling array of length n + 1 keeps one pair per column. While column j is updated, the left neighbor already holds this row's rightward flow and this column still holds the previous row's downward flow. Overwriting in place brings the space from O(mn) down to O(n).

In Solution 1, cell f[i][j] depends only on the rightward flow of the left neighbor and the downward flow of the cell above, so finished rows can be discarded.

Let f be an array of length n + 1 that stores the latest pair for each column. f[j + 1][0] and f[j + 1][1] are the rightward and downward ways leaving column j. The extra slot f[0] is the left border, and both of its components stay 0.

Scanning a row from left to right, read r = f[j][0] and d = f[j + 1][1] before updating column j, then write the same transition as in Solution 1 back into f[j + 1]. At that moment r is already the new value from the left cell of this row, while d is still the previous row's downward flow.

Initialize f[1] = (1, 1), so the origin reads an inflow of 1 from above. Return f[n][0].

The time complexity is O(mn) and the space complexity is O(n), where m and n are the number of rows and columns.

Python

class Solution:
    def uniquePaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        n = len(grid[0])
        f = [[0, 0] for _ in range(n + 1)]
        f[1] = [1, 1]
        for row in grid:
            for j, x in enumerate(row):
                r, d = f[j][0], f[j + 1][1]
                if x == 1:
                    f[j + 1] = [d, r]
                else:
                    s = (r + d) % mod
                    f[j + 1] = [s, s]
        return f[n][0]

Java

class Solution {
    public int uniquePaths(int[][] grid) {
        final int mod = (int) 1e9 + 7;
        int n = grid[0].length;
        int[][] f = new int[n + 1][2];
        f[1][0] = f[1][1] = 1;
        for (int[] row : grid) {
            for (int j = 0; j < n; ++j) {
                int r = f[j][0], d = f[j + 1][1];
                if (row[j] == 1) {
                    f[j + 1][0] = d;
                    f[j + 1][1] = r;
                } else {
                    int s = (r + d) % mod;
                    f[j + 1][0] = f[j + 1][1] = s;
                }
            }
        }
        return f[n][0];
    }
}

C++

class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const int mod = 1e9 + 7;
        int n = grid[0].size();
        vector<array<int, 2>> f(n + 1);
        f[1] = {1, 1};
        for (auto& row : grid) {
            for (int j = 0; j < n; ++j) {
                int r = f[j][0], d = f[j + 1][1];
                if (row[j] == 1) {
                    f[j + 1] = {d, r};
                } else {
                    int s = (r + d) % mod;
                    f[j + 1] = {s, s};
                }
            }
        }
        return f[n][0];
    }
};

TypeScript

function uniquePaths(grid: number[][]): number {
    const mod = 1e9 + 7;
    const n = grid[0].length;
    const f: number[][] = Array.from({ length: n + 1 }, () => [0, 0]);
    f[1] = [1, 1];
    for (const row of grid) {
        for (let j = 0; j < n; ++j) {
            const r = f[j][0];
            const d = f[j + 1][1];
            if (row[j] === 1) {
                f[j + 1] = [d, r];
            } else {
                const s = (r + d) % mod;
                f[j + 1] = [s, s];
            }
        }
    }
    return f[n][0];
}

func uniquePaths(grid [][]int) int {
	const mod = int(1e9 + 7)
	n := len(grid[0])
	f := make([][2]int, n+1)
	f[1] = [2]int{1, 1}
	for _, row := range grid {
		for j, x := range row {
			r, d := f[j][0], f[j+1][1]
			if x == 1 {
				f[j+1] = [2]int{d, r}
			} else {
				s := (r + d) % mod
				f[j+1] = [2]int{s, s}
			}
		}
	}
	return f[n][0]
}

Rust

impl Solution {
    pub fn unique_paths(grid: Vec<Vec<i32>>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = grid[0].len();
        let mut f = vec![(0i32, 0i32); n + 1];
        f[1] = (1, 1);
        for row in &grid {
            for (j, &x) in row.iter().enumerate() {
                let (r, d) = (f[j].0, f[j + 1].1);
                f[j + 1] = if x == 1 {
                    (d, r)
                } else {
                    let s = (r + d) % MOD;
                    (s, s)
                };
            }
        }
        f[n].0
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming	–
Dynamic Programming (Space Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force DFS	O(2^(m+n))	O(m+n)	Understanding path rules and mirror behavior for small grids
DFS + Memoization	O(m*n)	O(m*n)	General solution when recursion is easier to implement
Bottom-Up Dynamic Programming	O(m*n)	O(m*n)	Interview-friendly approach with deterministic iteration
Space Optimized DP	O(m*n)	O(n)	Large grids where reducing memory usage matters

Frequently asked questions

Is Twisted Mirror Path Count easy or hard?

Twisted Mirror Path Count is generally classified as a Medium problem. The main challenge is correctly modeling the mirror direction rules and converting the path traversal into a dynamic programming state transition.

Twisted Mirror Path Count Python/Java solution

The solution typically uses a DP matrix or memoized DFS. Python implementations often use recursion with a dictionary cache or a 2D list DP table, while Java implementations use an integer 2D array and iterative loops to propagate path counts.

How to solve Twisted Mirror Path Count in O(n)?

Use a space-optimized dynamic programming technique. Instead of storing the full m x n DP table, maintain a rolling array representing the current row of path counts. Updates propagate according to the mirror direction, reducing space complexity to O(n) while keeping time complexity O(m*n).

What is the best approach for Twisted Mirror Path Count?

Dynamic programming over the grid is the most efficient solution. Each cell stores the number of ways to reach or leave that position while respecting the mirror direction. This reduces repeated work and runs in O(m*n) time with O(m*n) space.

Is Twisted Mirror Path Count asked at Google/Amazon/Meta?

Grid dynamic programming and path-counting problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving obstacles, direction constraints, or grid transformations are common interview patterns.

What data structure is used in Twisted Mirror Path Count?

The core structure is a 2D dynamic programming array representing the matrix state. Each entry tracks the number of valid ways to reach a cell while following the mirror redirection rules.

What is the time complexity of Twisted Mirror Path Count?

The optimal dynamic programming solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is processed once and contributes to a constant number of transitions based on the mirror orientation.

Twisted Mirror Path Count solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming

Approach 2: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Twisted Mirror Path Count solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming

Approach 2: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems