DDSA Solutions

3882. Minimum XOR Path in a Grid

MediumView on LeetCode
ArrayDynamic ProgrammingBit ManipulationMatrix
Time: O(m * n * R)
Space: O(n * R)

Problem Overview

A path cost is the XOR of every cell on a right and down route from the top left to the bottom right.

Intuition

A path cost is the XOR of every cell on a right and down route from the top left to the bottom right. Keeping only the smallest XOR that reaches a cell fails, because later cells can turn a larger prefix into a smaller finish. Every grid value is at most 1023, so it fits in 10 bits, and the XOR of any path stays inside that same range. The useful range can be tighter. R is the next power of two above the largest cell, and it is never more than 1024. Each cell stores a yes or no for every XOR from 0 through R minus 1. Those flags come from the cell above and the cell to the left, each combined with the current value. After a row is finished, the row above it is no longer needed.

Algorithm

  1. 1Find the largest cell and set R to the next power of two above it. A grid of zeros uses R equal to 1.
  2. 2Seed the previous row so that XOR 0 is reachable before any cell is applied.
  3. 3For each cell, mark k XOR the cell value whenever k is reachable from above or from the left.
  4. 4Swap the two row buffers and continue.
  5. 5Return the smallest marked value in the last column of the final row.

Example Walkthrough

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

  1. 1.Right then down is 1 XOR 2 XOR 4, which is 7.
  2. 2.Down then right is 1 XOR 3 XOR 4, which is 6.
  3. 3.Both values reach the bottom right, and 6 is the smaller one.

Output: 6

Common Pitfalls

  • •A single minimum per cell is not enough. A larger prefix XOR can become the smaller answer after later cells.
  • •The start cell is included. Seed a phantom XOR of 0 and then XOR the first cell into it, so a one cell grid returns that cell.
  • •R must be a power of two strictly above the biggest cell. Otherwise k XOR the cell can land past the end of the array.
  • •Moves are only right and down. A value reached by stepping left or up is not a valid path.
3882.cs
C#
// Approach: XOR is not a running minimum, because a larger prefix can finish
// smaller. Every cell value fits in 10 bits, so every path XOR has at most R
// possible values, where R is the next power of two above the largest cell.
// A cell's reachable values are the values of the cell above and the cell to
// the left, each XORed with the current cell. Only the previous row is kept.
// Time: O(m * n * R) Space: O(n * R)

public class Solution
{
    public int MinCost(int[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int maxV = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] > maxV)
                    maxV = grid[i][j];

        int limit = 1;
        while (limit <= maxV)
            limit <<= 1;

        bool[][] above = new bool[n][];
        bool[][] cur = new bool[n][];
        for (int j = 0; j < n; j++)
        {
            above[j] = new bool[limit];
            cur[j] = new bool[limit];
        }
        above[0][0] = true;

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
                Array.Clear(cur[j]);
            for (int j = 0; j < n; j++)
            {
                int v = grid[i][j];
                bool[] up = above[j];
                bool[] left = j > 0 ? cur[j - 1] : null;
                bool[] dest = cur[j];
                for (int k = 0; k < limit; k++)
                    if (up[k] || (left != null && left[k]))
                        dest[k ^ v] = true;
            }

            bool[][] tmp = above;
            above = cur;
            cur = tmp;
        }

        for (int k = 0; k < limit; k++)
            if (above[n - 1][k])
                return k;
        return 0;
    }
}
Was this solution helpful?

Related Problems