Backtracking — Valid Sudoku

↗ LeetCode: Valid Sudoku · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftAppleUberBloomberg

Check partial Sudoku validity (no duplicates within row/col/box among filled cells).

Constraints — 9×9 board. Brute nested triple-loop is O(9²·9) = 729 ops — trivial. Set-based row/col/box check is O(81) = 81 ops per full validation, ~10⁶ ops/sec for streaming boards. Example 1 — Standard partially-filled 9×9 board → trueExample 2 — Same as 1 but with two 8s in same column → false

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Three passes

Rows, columns, boxes — separate scans.

Approach 2 — One pass with encoded keys (canonical)

Insight. Emit three keys per filled cell into a set: "r{r}={d}", "c{c}={d}", "b{r/3}{c/3}={d}". Duplicate → invalid.

boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            char d = board[r][c];
            if (d == '.') continue;
            if (!seen.add("r" + r + d) || !seen.add("c" + c + d) || !seen.add("b" + r/3 + c/3 + d)) return false;
        }
    return true;
}

Approach 3 — Bitmasks (fastest)

rows[9], cols[9], boxes[9] as ints; check + set bit for each cell.

Complexity — Time O(1) (fixed 81); Space O(1).

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Three-pass	O(81)	O(9)	baseline
One-pass keys	O(81)	O(1)	canonical
Bitmasks	O(81)	O(1)	fastest

When to use which

• Standard → encoded keys.
• Speed → bitmasks.
• Solve, not validate → see Sudoku Solver.

✨AI Study CompanionBeta

Related problems

• Sudoku Solver

Was this page helpful?