LeetCode 3882 - Minimum XOR Path in a Grid

We are given an m × n grid of integers. Starting from the top-left cell (0, 0), we must reach the bottom-right cell (m - 1, n - 1) by moving only right or down.

leetcodemediumarraydynamic-programmingbit-manipulationmatrix

LeetCode Problem 3882

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Bit Manipulation, Matrix

Solution

LeetCode 3882 - Minimum XOR Path in a Grid

Problem Understanding

We are given an m × n grid of integers. Starting from the top-left cell (0, 0), we must reach the bottom-right cell (m - 1, n - 1) by moving only right or down.

For every path, we compute its cost as the bitwise XOR of all values encountered along the path, including both the starting and ending cells.

Our goal is to find the smallest XOR value achievable among all valid paths.

A key detail is that XOR behaves very differently from addition. With sums, dynamic programming often works by keeping only the minimum value seen so far. For XOR, a path with a larger intermediate XOR can eventually produce a smaller final XOR after more values are XORed in. Therefore, we cannot simply store a single best value per cell.

The constraints provide an important clue:

  • m * n <= 1000
  • 0 <= grid[i][j] <= 1023

Since every cell value is at most 1023, all values fit within 10 bits.

When XORing numbers that each use at most 10 bits, the result also remains within the range:

0 ... 1023

This means there are only 1024 possible XOR states.

Although the grid may contain up to 1000 cells, the number of possible XOR values is very small. This strongly suggests a dynamic programming solution that tracks reachable XOR values at each cell.

Important edge cases include:

  • A grid containing only one cell.
  • A single row grid where only right moves are possible.
  • A single column grid where only down moves are possible.
  • Multiple paths producing the same XOR value.
  • Cases where the minimum XOR is 0.
  • Large grids where many different XOR states become reachable.

Approaches

Brute Force

A straightforward solution is to enumerate every valid path from the top-left corner to the bottom-right corner.

For each path:

  1. Traverse the path.
  2. XOR all visited values.
  3. Track the minimum XOR encountered.

This approach is correct because it explicitly evaluates every possible path.

However, the number of paths is:

$$\binom{m+n-2}{m-1}$$

For a grid containing hundreds of cells, this number becomes astronomically large. Therefore brute force is completely infeasible.

Key Insight

The crucial observation is that the XOR value can only be one of 1024 possibilities.

Instead of storing a single value for each cell, we store all XOR values that can reach that cell.

Let:

dp[i][j]

be the set of XOR values achievable when arriving at cell (i, j).

If we know all XOR values reaching the cell above and the cell to the left, we can generate all XOR values for the current cell:

new_xor = previous_xor XOR grid[i][j]

Because there are only 1024 possible XOR states, the total state space is bounded by:

1000 × 1024

which is manageable.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Enumerates every path
Optimal O(m × n × 1024) O(m × n × 1024) DP over XOR states

Algorithm Walkthrough

Optimal Dynamic Programming

  1. Create a DP table where each cell stores a set of reachable XOR values.
  2. Initialize the starting cell:
dp[0][0] = {grid[0][0]}

The only possible XOR at the starting position is the value of that cell itself. 3. Process cells row by row. 4. For each cell (i, j), consider transitions from the cell above.

For every XOR value x reachable at (i-1, j):

x XOR grid[i][j]

becomes reachable at (i, j). 5. Also consider transitions from the cell to the left.

For every XOR value x reachable at (i, j-1):

x XOR grid[i][j]

becomes reachable at (i, j). 6. Continue until every cell has been processed. 7. The bottom-right cell contains every XOR value achievable by a valid path. 8. Return the minimum value contained in:

dp[m-1][n-1]

Why it works

For every cell, the DP set contains exactly the XOR values obtainable by some valid path ending at that cell.

The base case is correct because the starting cell contributes only its own value.

Every valid path reaching a cell must come either from above or from the left. The transition applies the current cell's value via XOR, which precisely matches the path definition.

Therefore, by induction over the processing order, every reachable XOR value is represented and no impossible XOR value is added. The destination cell contains exactly the XOR values of all valid paths, so taking the minimum yields the correct answer.

Python Solution

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

        dp = [[set() for _ in range(n)] for _ in range(m)]
        dp[0][0].add(grid[0][0])

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue

                current = set()

                if i > 0:
                    for xor_value in dp[i - 1][j]:
                        current.add(xor_value ^ grid[i][j])

                if j > 0:
                    for xor_value in dp[i][j - 1]:
                        current.add(xor_value ^ grid[i][j])

                dp[i][j] = current

        return min(dp[m - 1][n - 1])

Implementation Explanation

The DP table stores a set of reachable XOR values for every cell.

The starting cell is initialized with a single XOR state, namely its own value.

For each remaining cell, we build a new set of reachable XOR values. Every XOR value coming from above or from the left is extended by XORing the current cell value.

Because sets automatically eliminate duplicates, multiple paths producing the same XOR state do not increase memory usage.

After processing the entire grid, the destination cell contains all achievable XOR results. The answer is simply the smallest value in that set.

Go Solution

func minCost(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	dp := make([][]map[int]struct{}, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]map[int]struct{}, n)
		for j := 0; j < n; j++ {
			dp[i][j] = make(map[int]struct{})
		}
	}

	dp[0][0][grid[0][0]] = struct{}{}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				continue
			}

			if i > 0 {
				for xorValue := range dp[i-1][j] {
					dp[i][j][xorValue^grid[i][j]] = struct{}{}
				}
			}

			if j > 0 {
				for xorValue := range dp[i][j-1] {
					dp[i][j][xorValue^grid[i][j]] = struct{}{}
				}
			}
		}
	}

	ans := 1024
	for xorValue := range dp[m-1][n-1] {
		if xorValue < ans {
			ans = xorValue
		}
	}

	return ans
}

Go-Specific Notes

Go does not have a built-in set type, so a map[int]struct{} is used to represent a set of XOR states.

The empty struct consumes zero storage per value and is the standard Go idiom for implementing sets.

All XOR values remain in the range 0...1023, so integer overflow is never a concern.

Worked Examples

Example 1

grid =
[
  [1, 2],
  [3, 4]
]

Initial state:

Cell Reachable XORs
(0,0) {1}

Process (0,1):

1 XOR 2 = 3
Cell Reachable XORs
(0,1) {3}

Process (1,0):

1 XOR 3 = 2
Cell Reachable XORs
(1,0) {2}

Process (1,1):

From above:

3 XOR 4 = 7

From left:

2 XOR 4 = 6
Cell Reachable XORs
(1,1) {6, 7}

Answer:

min(6, 7) = 6

Example 2

grid =
[
  [6, 7],
  [5, 8]
]
Cell Reachable XORs
(0,0) {6}

Process (0,1):

6 XOR 7 = 1

Process (1,0):

6 XOR 5 = 3

Process (1,1):

From above:

1 XOR 8 = 9

From left:

3 XOR 8 = 11

Destination set:

{9, 11}

Answer:

9

Example 3

grid = [[2, 7, 5]]

Start:

{2}

After second cell:

2 XOR 7 = 5

After third cell:

5 XOR 5 = 0

Destination set:

{0}

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(m × n × 1024) Each cell processes at most 1024 XOR states
Space O(m × n × 1024) Each cell may store up to 1024 reachable XOR values

The important observation is that XOR results are bounded by the 10-bit value range. Even though the number of paths can be enormous, the number of distinct XOR states at any cell is at most 1024. This converts an exponential path enumeration problem into a polynomial dynamic programming problem.

Test Cases

sol = Solution()

assert sol.minCost([[1, 2], [3, 4]]) == 6  # Example 1

assert sol.minCost([[6, 7], [5, 8]]) == 9  # Example 2

assert sol.minCost([[2, 7, 5]]) == 0  # Example 3

assert sol.minCost([[5]]) == 5  # Single cell grid

assert sol.minCost([[1, 2, 3]]) == (1 ^ 2 ^ 3)  # Single row

assert sol.minCost([[1], [2], [3]]) == (1 ^ 2 ^ 3)  # Single column

assert sol.minCost([[0, 0], [0, 0]]) == 0  # All zeros

assert sol.minCost([[1023]]) == 1023  # Maximum cell value

assert sol.minCost([[1, 1], [1, 1]]) == 1  # Multiple paths same result

assert sol.minCost([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]) >= 0  # General larger example

Test Summary

Test Why
[[1,2],[3,4]] First official example
[[6,7],[5,8]] Second official example
[[2,7,5]] Single path example
[[5]] Minimum grid size
Single row Only right moves allowed
Single column Only down moves allowed
All zeros Minimum XOR should remain zero
[[1023]] Maximum value boundary
[[1,1],[1,1]] Duplicate XOR states
3×3 grid General multi-path scenario

Edge Cases

Single Cell Grid

When m = n = 1, the start and destination are the same cell. No movement occurs, and the path consists of exactly one value. A common bug is attempting transitions from non-existent neighbors. The implementation handles this by initializing dp[0][0] and skipping further processing for that cell.

Single Row or Single Column

In a single row, every path must move right. In a single column, every path must move down. Some implementations incorrectly assume both predecessors always exist. The solution explicitly checks i > 0 and j > 0 before accessing neighbors, so these boundary cases work naturally.

Many Different Paths Producing the Same XOR

Different paths can lead to identical XOR values. If duplicate states are stored repeatedly, memory usage can grow unnecessarily. Using sets ensures that each XOR value is stored only once per cell, keeping the state space bounded by 1024.

Minimum XOR Equal to Zero

A path XOR of zero is entirely possible and is actually the best possible answer because XOR values are non-negative. Some greedy approaches might miss such paths because they focus on locally small XOR values. The DP state representation preserves every reachable XOR value, guaranteeing that a zero result will be found whenever it exists.

Large Grids with Many Paths

Even though a grid may have an enormous number of valid paths, the XOR range remains limited to 1024 states. The implementation exploits this property, preventing the exponential explosion that would occur with path enumeration and ensuring the algorithm remains efficient within the given constraints.