Grids

Determine if a \(9 \times 9\) Sudoku board is valid. A Sudoku board has nine \(3 \times 3\) sub-boxes. Validate the filled cells such that each row, column, and sub-box contain the digits \([1, …, 9]\) without repetition.

I don’t think we can do better than validating all 9 rows, 9 columns, and 9 sub-boxes. There’s no repeated work that can be optimized. At its core, this problem is about traversing the grid in different ways. There is room for improvement in how we handle each check. From the char[][] grid, we can use a HashSet<char> to check for duplicates (ignoring c == '.'). If we convert the char[][] to an int?[9,9] grid, we can use a compact BitArray to check for duplicates, or as I’ve just learned, a BitVector32 which is even more compact at 32 bits.

Shortest Path in a Grid with Obstacles Elimination - LeetCode. leetcode.com . Accessed Jul 21, 2024.

Problem

You are given an \(m \times n\) grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner \((0, 0)\) to the lower-right corner \((m-1, n-1)\) given that you can eliminate at most \(k\) obstacles. If it is not possible to find such a walk, return -1.

Queen's Attack II. www.hackerrank.com . Accessed Jul 20, 2024.

Problem

A queen is standing on an \(n \times n\) chess board. The chess board’s rows are numbered from \(1\) to \(n\), going from bottom to top. Its columns are numbered from \(1\) to \(n\), going from left to right. Each square is referenced by a tuple \((r, c)\), describing the row, \(r\), and column, \(c\), where the square is located.

Grid Game - LeetCode. leetcode.com . Accessed Jul 20, 2024.

Problem

You are given a 0-indexed 2D array grid of size \(2 \times n\), where grid[r][c] represents the number of points at position \((r, c)\) on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at \((0, 0)\) and want to reach \((1, n-1)\). Each robot may only move to the right or down.

Problem

Starting from the top-left corner, what is the number of possible unique paths to reach the bottom-right corner, if you can only move either down or right at any point in time, and the path cannot include any square that is an obstacle?

Solution

The addition of obstacles has these implications:

• I can’t use the combinatorics formula because the problem is no longer easy to define in general terms.
• The logic in the inner loop of the DP solution needs to take the obstacles into account.

#dynamic-programming

Problem

Given an \(M \times N\) integer array grid where grid[i][j] could be:

• 1 representing the starting square. There is exactly one starting square.
• 2 representing the ending square. There is exactly one ending square.
• 0 representing empty squares that we can walk over.
• -1 representing obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Problem

Starting from the top-left corner, what is the number of possible unique paths to reach the bottom-right corner, if you can only move either down or right at any point in time?

Dynamic Programming Solution for Moving Down/Right

#dynamic-programming

The number of unique paths to grid[r][c] is the number of unique paths to grid[r-1][c] plus the number of unique paths to grid[r][c-1], e.g.,

At any given time, we’re interested in two adjacent rows, so our space usage should be at most \(2n\). Furthermore, we do not back-track to the left, so if we update our values left-to-right, we can use \(n\) space because the current cell will have the value from what would have been in the previous row.