3665. Twisted Mirror Path Count
- Array
- Dynamic Programming
- Matrix
TIME
O(m * n)
SPACE
O(n)
Intuition
Plain grid path counting, except a mirror cell is never a place the robot stands. It is a turn whose result depends on the direction the robot came from: entering moving right sends it down, entering moving down sends it right. So the DP needs one extra bit per cell, the direction of entry. Moves still only go right or down, so row-major order works and chains of mirrors resolve on their own, one cell at a time.
Approach
- Let
R[i][j]= ways to enter(i, j)moving right, andD[i][j]= ways to enter it moving down. - Walk the grid row by row, left to right. At each cell:
- Empty: the robot stops here and picks either move. With
t = R + D, addttoR[i][j+1]and toD[i+1][j]. - Mirror: add
R[i][j]toD[i+1][j](right turns into down), andD[i][j]toR[i][j+1](down turns into right). - Anything sent past the grid edge is dropped, since those paths are invalid.
- Empty: the robot stops here and picks either move. With
- Start with
t = 1at(0, 0). The answer isR + Dat(m-1, n-1), mod10^9 + 7. Donly flows to the next row andRonly to the next column, so keep onedownarray for the row and one runningrightvalue.
Complexity
- Time: O(m * n)
- Space: O(n)
Edge Cases
- Chains of mirrors (example 3): each mirror passes its count on with the turn applied, so a chain needs no special loop
- A mirror on the last row hit while moving right, or on the last column hit while moving down, sends the robot out of the grid: the count is dropped
- A mirror's two incoming streams swap directions instead of merging, so the two counts must stay separate
- Start and end are guaranteed empty, so
(0, 0)seeds with 1 and the answer is read at an empty cell - Take the mod on every addition. In Java,
R + Dof two values below10^9 + 7can overflowint, so the sum is done inlong
Code
from typing import List
class Solution:
def uniquePaths(self, grid: List[List[int]]) -> int:
"""
3665. Twisted Mirror Path Count
Time: O(m * n)
Space: O(n)
"""
MOD = 10**9 + 7
m, n = len(grid), len(grid[0])
# down[j] = ways to enter (i, j) moving down, filled by the row above.
down = [0] * n
for i in range(m):
row = grid[i]
nxt = [0] * n
# right = ways to enter (i, j) moving right, from (i, j - 1).
right = 0
for j in range(n):
r, d = right, down[j]
if i == 0 and j == 0:
r, d = 1, 0
if row[j]:
# Mirror: moving right turns down, moving down turns right.
nxt[j] = r
right = d
else:
t = (r + d) % MOD
nxt[j] = t
right = t
if i == m - 1 and j == n - 1:
return (r + d) % MOD
# right leaving column n - 1 and nxt leaving row m - 1 fall off the grid.
down = nxt
return 0/**
* 3665. Twisted Mirror Path Count
* Time: O(m * n)
* Space: O(n)
*/
class Solution {
private static final int MOD = 1_000_000_007;
public int uniquePaths(int[][] grid) {
int m = grid.length, n = grid[0].length;
// down[j] = ways to enter (i, j) moving down, filled by the row above.
int[] down = new int[n];
for (int i = 0; i < m; i++) {
int[] next = new int[n];
// right = ways to enter (i, j) moving right, from (i, j - 1).
int right = 0;
for (int j = 0; j < n; j++) {
int r = right, d = down[j];
if (i == 0 && j == 0) {
r = 1;
d = 0;
}
int total = (int) (((long) r + d) % MOD);
if (i == m - 1 && j == n - 1) {
return total;
}
if (grid[i][j] == 1) {
// Mirror: moving right turns down, moving down turns right.
next[j] = r;
right = d;
} else {
next[j] = total;
right = total;
}
}
// right leaving column n - 1 and next leaving row m - 1 fall off the grid.
down = next;
}
return 0;
}
}