← leetcode

Twisted Mirror Path Count

· Medium

LeetCode problem 3665

a lot better than the last question...

this is a fairly rudimentary dynamic programming question, with the only tricky part being the mirrors. we can circumvent this by realising that mirrors have independent 2 directional states:

  • paths from the left that get reflected downwards
  • paths from the top that get reflected to the right

since an empty cell is just a cell where both directional states equal the total paths arriving (from the left and from the top), we can simply model each cell using a pair of integers.

code link to code

class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const long long MOD = 1e9 + 7;

        int m = grid.size();
        int n = grid[0].size();

        vector<vector<pair<long long, long long>>> paths(2, vector<pair<long long, long long>>(n));
        for (int i = 0; i < n; ++i) {
            if (grid[0][i] == 1) {
                paths[0][i] = {1, 0};
                break;
            }
            paths[0][i] = {1, 1};

        }

        for (int i = 1; i < m; ++i) {
            paths[1][0] = {(grid[i][0] == 1) ? 0 : paths[0][0].first, paths[0][0].first};

            for (int j = 1; j < n; ++j) {
                paths[1][j].first = paths[1][j-1].second;
                paths[1][j].second = paths[0][j].first;
                
                if (grid[i][j] == 0) {
                    paths[1][j].first =
                        (paths[1][j].first + paths[0][j].first) % MOD;
                    paths[1][j].second =
                        (paths[1][j].second + paths[1][j-1].second) % MOD;
                }
            }
            paths[0] = paths[1];
        }

        return paths[0].back().second;
    }
};

complexity link to complexity

  • Time: O(mn)
  • Space: O(n)

learnings link to learnings

  • i'm really terrible at debugging

time taken link to time taken

  • 31 minutes and 32 seconds
    • guys, i'm not that washed i swear i js spent like 20 minutes debugging