Skip to content

3882. Minimum XOR Path in a Grid

SourceBiweekly Contest 179 Q3DifficultyMediumRating1770

Description

You are given a 2D integer array grid of size m * n.

You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).

At each step, you may move either right or down.

The cost of a path is defined as the bitwise XOR of all the values in the cells along that path, including the start and end cells.

Return the minimum possible XOR value among all valid paths from (0, 0) to (m - 1, n - 1).

 

Example 1:

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

Output: 6

Explanation:

There are two valid paths:

  • (0, 0) → (0, 1) → (1, 1) with XOR: 1 XOR 2 XOR 4 = 7
  • (0, 0) → (1, 0) → (1, 1) with XOR: 1 XOR 3 XOR 4 = 6

The minimum XOR value among all valid paths is 6.

Example 2:

Input: grid = [[6,7],[5,8]]

Output: 9

Explanation:

There are two valid paths:

  • (0, 0) → (0, 1) → (1, 1) with XOR: 6 XOR 7 XOR 8 = 9
  • (0, 0) → (1, 0) → (1, 1) with XOR: 6 XOR 5 XOR 8 = 11

The minimum XOR value among all valid paths is 9.

Example 3:

Input: grid = [[2,7,5]]

Output: 0

Explanation:

There is only one valid path:

  • (0, 0) → (0, 1) → (0, 2) with XOR: 2 XOR 7 XOR 5 = 0

The XOR value of this path is 0, which is the minimum possible.

 

Constraints:

  • 1 <= m == grid.length <= 1000
  • 1 <= n == grid[i].length <= 1000
  • m * n <= 1000
  • 0 <= grid[i][j] <= 1023​

Solutions

Solution 1: Dynamic Programming

Thinking

Moves are only right or down, and the goal is the minimum XOR of a whole path. There are at most \(1000\) cells and values are below \(2^{10}\), but the number of paths still grows exponentially with the row and column counts, so enumerating paths does not fit.

XOR has no optimal substructure under numeric comparison. A smaller prefix XOR can become larger after later cells are appended, so every XOR that has already occurred must be kept.

After a cell is reached, later choices depend only on the current XOR. A state \((i,j,k)\) records whether cell \((i,j)\) is reachable with path XOR \(k\). Since \(k < 1024\), there are about \(10^6\) states.

Transitions go only right or down, so a row-major scan finds the upper and left cells already finished. A boolean array \(f[i][j][k]\) stores reachability; a cell of value \(x\) is entered from XOR \(k \oplus x\). The smallest \(k\) that is true at the lower-right cell is the answer.

Define \(f[i][j][k]\) as whether cell \((i, j)\) is reachable from \((0, 0)\) with the bitwise XOR of every cell on the path equal to \(k\).

Let \(M\) be the maximum value in the grid. Every path XOR lies in \([0, mx)\), where \(mx = 2^{b}\) and \(b\) is the bit length of \(M\). When \(M = 0\), \(b = 0\) and \(mx = 1\). Cell values are at most \(1023\), so \(mx \le 1024\).

The path at the start contains only that cell, so \(f[0][0][\textit{grid}[0][0]] = \textit{true}\).

Cells are processed in row-major order. For cell \((i, j)\) with value \(x\), if it is not the start, every \(k \in [0, mx)\) is considered. Because \((k \oplus x) \oplus x = k\), the XOR before entering the cell is \(k \oplus x\):

  • If \(i > 0\) and \(f[i - 1][j][k \oplus x]\) is true, the cell can be entered from above, and \(f[i][j][k] = \textit{true}\).
  • If \(j > 0\) and \(f[i][j - 1][k \oplus x]\) is true, the cell can be entered from the left, and \(f[i][j][k] = \textit{true}\).

Moves are only right or down, so the upper and left cells are already finished when \((i, j)\) is scanned. The answer is the smallest \(k\) for which \(f[m - 1][n - 1][k]\) is true. At least one path from the upper-left cell to the lower-right cell exists, so this \(k\) is guaranteed.

The time complexity is \(O(mn mx)\), and the space complexity is \(O(mn mx)\), where \(m\) and \(n\) are the number of rows and columns, and \(mx \le 1024\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        mx = 1 << (max(max(row) for row in grid)).bit_length()
        f = [[[False] * mx for _ in range(n)] for _ in range(m)]
        f[0][0][grid[0][0]] = True
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if i > 0 or j > 0:
                    for k in range(mx):
                        if i > 0 and f[i - 1][j][k ^ x]:
                            f[i][j][k] = True
                        if j > 0 and f[i][j - 1][k ^ x]:
                            f[i][j][k] = True
        return next(k for k in range(mx) if f[m - 1][n - 1][k])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }
        mx = 1 << (Integer.SIZE - Integer.numberOfLeadingZeros(mx));
        boolean[][][] f = new boolean[m][n][mx];
        f[0][0][grid[0][0]] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        if (i > 0 && f[i - 1][j][k ^ x]) {
                            f[i][j][k] = true;
                        }
                        if (j > 0 && f[i][j - 1][k ^ x]) {
                            f[i][j][k] = true;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[m - 1][n - 1][k]) {
                return k;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int mx = 0;
        for (auto& row : grid) {
            for (int x : row) {
                mx = max(mx, x);
            }
        }
        mx = 1 << bit_width(static_cast<unsigned>(mx));
        vector<vector<vector<char>>> f(m, vector<vector<char>>(n, vector<char>(mx, 0)));
        f[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        if (i > 0 && f[i - 1][j][k ^ x]) {
                            f[i][j][k] = 1;
                        }
                        if (j > 0 && f[i][j - 1][k ^ x]) {
                            f[i][j][k] = 1;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[m - 1][n - 1][k]) {
                return k;
            }
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func minCost(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    mx := 0
    for _, row := range grid {
        for _, x := range row {
            if x > mx {
                mx = x
            }
        }
    }
    mx = 1 << bits.Len(uint(mx))
    f := make([][][]bool, m)
    for i := range f {
        f[i] = make([][]bool, n)
        for j := range f[i] {
            f[i][j] = make([]bool, mx)
        }
    }
    f[0][0][grid[0][0]] = true
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            x := grid[i][j]
            if i > 0 || j > 0 {
                for k := 0; k < mx; k++ {
                    if i > 0 && f[i-1][j][k^x] {
                        f[i][j][k] = true
                    }
                    if j > 0 && f[i][j-1][k^x] {
                        f[i][j][k] = true
                    }
                }
            }
        }
    }
    for k := 0; ; k++ {
        if f[m-1][n-1][k] {
            return k
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function minCost(grid: number[][]): number {
    const m = grid.length,
        n = grid[0].length;
    let mx = 0;
    for (const row of grid) {
        for (const x of row) {
            mx = Math.max(mx, x);
        }
    }
    mx = 1 << (32 - Math.clz32(mx));
    const f: boolean[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => new Array<boolean>(mx).fill(false)),
    );
    f[0][0][grid[0][0]] = true;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const x = grid[i][j];
            if (i > 0 || j > 0) {
                for (let k = 0; k < mx; k++) {
                    if (i > 0 && f[i - 1][j][k ^ x]) {
                        f[i][j][k] = true;
                    }
                    if (j > 0 && f[i][j - 1][k ^ x]) {
                        f[i][j][k] = true;
                    }
                }
            }
        }
    }
    for (let k = 0; ; k++) {
        if (f[m - 1][n - 1][k]) {
            return k;
        }
    }
}

Solution 2: Dynamic Programming (Rolling Array)

Thinking

Solution 1 keeps every reachable XOR of every cell, so the space grows with \(mn\). Cell \((i, j)\) reads only the cell above and the cell to the left, and a row-major scan finishes both first. The previous row is still complete when the current row begins, and the current row only needs the left neighbor already written, so two rolling rows are enough. The transition still looks back at \(k \oplus x\) for a cell of value \(x\), the answer is still the smallest reachable XOR at the lower-right cell, and the space drops to \(O(n mx)\).

Define \(f[i \bmod 2][j][k]\) as whether row \(i\) and column \(j\) are reachable from \((0, 0)\) with the bitwise XOR of every cell on the path equal to \(k\). The value of \(mx\) matches Solution 1, and the start cell again has \(f[0][0][\textit{grid}[0][0]] = \textit{true}\).

Cells are processed in row-major order. For cell \((i, j)\) with value \(x\), if it is not the start, every \(k \in [0, mx)\) is considered. The row index is taken modulo \(2\), so the current slot may still hold an older row. Each \(k\) is therefore cleared first, then set with the same conditions as Solution 1:

  • If \(i > 0\) and \(f[(i - 1) \bmod 2][j][k \oplus x]\) is true, the cell can be entered from above, and \(f[i \bmod 2][j][k] = \textit{true}\).
  • If \(j > 0\) and \(f[i \bmod 2][j - 1][k \oplus x]\) is true, the cell can be entered from the left, and \(f[i \bmod 2][j][k] = \textit{true}\).

Row \(i\) is stored at index \(i \bmod 2\), the previous row stays at \((i - 1) \bmod 2\), and the left cell shares that row. The answer is the smallest \(k\) for which \(f[(m - 1) \bmod 2][n - 1][k]\) is true. At least one path from the upper-left cell to the lower-right cell exists, so this \(k\) is guaranteed.

The time complexity is \(O(mn mx)\), and the space complexity is \(O(n mx)\), where \(m\) and \(n\) are the number of rows and columns, and \(mx \le 1024\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        mx = 1 << (max(max(row) for row in grid)).bit_length()
        f = [[[False] * mx for _ in range(n)] for _ in range(2)]
        f[0][0][grid[0][0]] = True
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if i > 0 or j > 0:
                    for k in range(mx):
                        f[i & 1][j][k] = False
                        if i > 0 and f[(i - 1) & 1][j][k ^ x]:
                            f[i & 1][j][k] = True
                        if j > 0 and f[i & 1][j - 1][k ^ x]:
                            f[i & 1][j][k] = True
        return next(k for k in range(mx) if f[(m - 1) & 1][n - 1][k])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }
        mx = 1 << (Integer.SIZE - Integer.numberOfLeadingZeros(mx));
        boolean[][][] f = new boolean[2][n][mx];
        f[0][0][grid[0][0]] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        f[i & 1][j][k] = false;
                        if (i > 0 && f[(i - 1) & 1][j][k ^ x]) {
                            f[i & 1][j][k] = true;
                        }
                        if (j > 0 && f[i & 1][j - 1][k ^ x]) {
                            f[i & 1][j][k] = true;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[(m - 1) & 1][n - 1][k]) {
                return k;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int mx = 0;
        for (auto& row : grid) {
            for (int x : row) {
                mx = max(mx, x);
            }
        }
        mx = 1 << bit_width(static_cast<unsigned>(mx));
        vector<vector<vector<char>>> f(2, vector<vector<char>>(n, vector<char>(mx, 0)));
        f[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                if (i > 0 || j > 0) {
                    for (int k = 0; k < mx; k++) {
                        f[i & 1][j][k] = 0;
                        if (i > 0 && f[(i - 1) & 1][j][k ^ x]) {
                            f[i & 1][j][k] = 1;
                        }
                        if (j > 0 && f[i & 1][j - 1][k ^ x]) {
                            f[i & 1][j][k] = 1;
                        }
                    }
                }
            }
        }
        for (int k = 0;; k++) {
            if (f[(m - 1) & 1][n - 1][k]) {
                return k;
            }
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func minCost(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    mx := 0
    for _, row := range grid {
        for _, x := range row {
            if x > mx {
                mx = x
            }
        }
    }
    mx = 1 << bits.Len(uint(mx))
    f := make([][][]bool, 2)
    for i := range f {
        f[i] = make([][]bool, n)
        for j := range f[i] {
            f[i][j] = make([]bool, mx)
        }
    }
    f[0][0][grid[0][0]] = true
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            x := grid[i][j]
            if i > 0 || j > 0 {
                for k := 0; k < mx; k++ {
                    f[i&1][j][k] = false
                    if i > 0 && f[(i-1)&1][j][k^x] {
                        f[i&1][j][k] = true
                    }
                    if j > 0 && f[i&1][j-1][k^x] {
                        f[i&1][j][k] = true
                    }
                }
            }
        }
    }
    for k := 0; ; k++ {
        if f[(m-1)&1][n-1][k] {
            return k
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function minCost(grid: number[][]): number {
    const m = grid.length,
        n = grid[0].length;
    let mx = 0;
    for (const row of grid) {
        for (const x of row) {
            mx = Math.max(mx, x);
        }
    }
    mx = 1 << (32 - Math.clz32(mx));
    const f: boolean[][][] = Array.from({ length: 2 }, () =>
        Array.from({ length: n }, () => new Array<boolean>(mx).fill(false)),
    );
    f[0][0][grid[0][0]] = true;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const x = grid[i][j];
            if (i > 0 || j > 0) {
                for (let k = 0; k < mx; k++) {
                    f[i & 1][j][k] = false;
                    if (i > 0 && f[(i - 1) & 1][j][k ^ x]) {
                        f[i & 1][j][k] = true;
                    }
                    if (j > 0 && f[i & 1][j - 1][k ^ x]) {
                        f[i & 1][j][k] = true;
                    }
                }
            }
        }
    }
    for (let k = 0; ; k++) {
        if (f[(m - 1) & 1][n - 1][k]) {
            return k;
        }
    }
}

Comments