Finished Sudoku of Any Size
MediumMatrix
Problem
A puzzle site publishes Sudoku variants in several sizes. A board has side N = k² (for example 4, 9 or 16) and is split into N boxes of k × k cells. A finished board is correct when every row, every column and every box contains each number from 1 to N exactly once.
Given a fully filled board of integers, return true if it is a correct finished board and false otherwise. Values outside 1..N make the board incorrect.
Example 1
- Input:
- board = [[1, 2, 3, 4], [3, 4, 1, 2], [2, 1, 4, 3], [4, 3, 2, 1]]
- Output:
- true
N = 4, k = 2: every row, column and 2 × 2 box holds 1, 2, 3 and 4.
Example 2
- Input:
- board = [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]
- Output:
- false
Rows and columns are fine, but the top-left box holds 1, 2, 2, 3.
Example 3
- Input:
- board = [[1]]
- Output:
- true
Constraints
- N = board.length = board[i].length
- N is a perfect square, 1 ≤ N ≤ 25
- -100 ≤ board[i][j] ≤ 100
Hint
Show the first hint
There are three kinds of units: rows, columns and boxes. Each must contain no repeats and no out-of-range values.
Walkthrough
How to approach it
01Clarify before coding
- Is the board always full? Yes; the question is whether it is a correct solution.
- How is k found? k = √N; N is guaranteed to be a perfect square.
- Are out-of-range values possible? Yes, 0 or N + 1 must make the board incorrect.
02Brute force
For each of the 3N units, collect its N values, sort them and compare with [1, 2, …, N].
Cost: O(N² log N) time and O(N) memory per unit. Correct, but it walks the board three times and sorts each unit.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.