#3665
Twisted Mirror Path Count
MediumArrayDynamic ProgrammingMatrixDynamic ProgrammingGrid Traversal
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(m * n) |
| Space | O(1) | O(m * n) |
💡
Intuition
Time O(m * n)Space O(m * n)
Use dynamic programming to store the number of ways to reach each cell, leveraging precomputed jump targets for mirrors.
⚙️
Algorithm
3 steps- 1Step 1: Precompute jump targets for each cell based on mirror reflections.
- 2Step 2: Initialize dp array with dp[0][0] = 1.
- 3Step 3: Iterate through the grid, updating dp based on valid moves and reflections.
solution.py17 lines
1def countPaths(grid):
2 m, n = len(grid), len(grid[0])
3 dp = [[0] * n for _ in range(m)]
4 dp[0][0] = 1
5 for i in range(m):
6 for j in range(n):
7 if grid[i][j] == 0:
8 if i + 1 < m:
9 dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % (10**9 + 7)
10 if j + 1 < n:
11 dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % (10**9 + 7)
12 else:
13 if i + 1 < m:
14 dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % (10**9 + 7)
15 if j + 1 < n:
16 dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % (10**9 + 7)
17 return dp[m - 1][n - 1]ℹ
Complexity note: Each cell is processed once, leading to linear complexity with respect to the grid size.
- 1Mirrors change direction, requiring careful path tracking.
- 2Dynamic programming efficiently counts paths without redundancy.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.