Watch 7 video solutions for Twisted Mirror Path Count, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by Sanyam IIT Guwahati has 332 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an m x n binary grid grid where:
grid[i][j] == 0 represents an empty cell, andgrid[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 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 either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 0Problem 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 | 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 |