Loading page…
Practice problem · medium
A parcel hub stores crates on a wall of n rows and n columns, where n is a perfect square such as 4, 9 or 16. Each crate has a label from 1 to n, and an empty slot has the label 0.
The wall is split into square blocks, each with sides of the square root of n slots. A wall is valid when no label repeats in any row, any column or any block.
You check a wall. Your team lead says: "Every row, column and block is a group. A label may appear once in each group."
Write valid_grid(grid).
grid is a square list of lists. grid[r][c] is the label of the crate at row r and column c, or 0 for an empty slot.n is a perfect square, and the side of a block is its square root. The blocks tile the wall: the block of the slot at row r and column c holds the rows and columns that share r // side and c // side.true when no label from 1 to n appears twice in a row, a column or a block. Empty slots are ignored. Return false otherwise.Input: grid = [[1, 2, 3, 4], [3, 4, 1, 2], [2, 1, 4, 3], [4, 3, 2, 1]]
Output: trueThe side is 4 and a block has side 2. The trace shows the keys of the first row. A key is a kind of group, its number and the label.
| Step | Cell | Keys added | Already seen? |
|---|---|---|---|
| 1 | row 0, column 0, label 1 | (row, 0, 1), (column, 0, 1), (block, 0, 1) | no |
| 2 | row 0, column 1, label 2 | (row, 0, 2), (column, 1, 2), (block, 0, 2) | no |
| 3 | row 0, column 2, label 3 | (row, 0, 3), (column, 2, 3), (block, 1, 3) | no |
| 4 | row 0, column 3, label 4 | (row, 0, 4), (column, 3, 4), (block, 1, 4) | no |
The other 12 slots add their keys in the same way, and none repeats.
Input: grid = [[1, 2, 3, 4], [3, 4, 1, 2], [2, 1, 4, 3], [4, 3, 1, 2]]
Output: falseThe label 1 is in column 2 twice, in rows 1 and 3.
Input: grid = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Output: trueEmpty slots are ignored, so a mostly empty wall can be valid.
1 ≤ grid.length ≤ 400, and grid.length is a perfect squaregrid.length entries, and each entry is from 0 to grid.length.The wall has up to 160,000 slots. Comparing every crate with every other crate of its row, column and block costs about 160,000 × 1,200 = 2 × 10^8 comparisons. A plain loop over all pairs of slots costs far more. A set of keys costs three steps for each slot.
Each slot is in three groups, so each slot makes three keys.
valid_grid · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.