Problem Statement in English

You’re given a grid of integers. You have to find the minimum XOR path from the top-left corner to the bottom-right corner of the grid. You can only move right or down.

Return the minimum XOR path from the top-left corner to the bottom-right corner of the grid.

Approach

This reeks of dynamic programming. The only main difference here is that instead of a single result from each cell we have a set of results. This is because you can’t really predict what will have a lower XOR value, so you have to keep track of all the possible XOR values from each cell.

And we’re done!

Solution in Python


class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        M = len(grid)
        N = len(grid[0])

        @cache
        def dp(i, j):
            if i == M - 1 and j == N - 1:
                return (grid[i][j],)

            this = grid[i][j]
            candidates = []

            if i + 1 < M:
                candidates.extend(dp(i + 1, j))
            
            if j + 1 < N:
                candidates.extend(dp(i, j + 1))

            return tuple(set(this ^ x for x in candidates))

        return min(dp(0, 0))

Complexity

  • Time: $O(M \times N)$
    Since we have at most $M \times N$ subproblems and each subproblem takes $O(1)$ time to solve.

  • Space: $O(M \times N)$
    Since we store the results of the subproblems in a cache.

Mistakes I Made

I didn’t wrap the results in a set, which caused duplicates and thus, a MLE.

And we are done.