Welcome to Subscribe On Youtube
3665. Twisted Mirror Path Count
Description
Given an m x n binary grid grid where:
grid[i][j] == 0represents an empty cell, andgrid[i][j] == 1represents 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 109 + 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.lengthn == grid[i].length2 <= m, n <= 500grid[i][j]is either0or1.grid[0][0] == grid[m - 1][n - 1] == 0
Solutions
Solution 1
Solution 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.
-
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]; } } // Solution 2 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]; } } -
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]; } }; // Solution 2 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]; } }; -
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] # Solution 2 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] -
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] } // Solution 2 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] } -
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]; } // Solution 2 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]; } -
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 } } // Solution 2 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 } }