What is the brute force approach and complexity for Valid Sudoku?

For each filled cell, look through its row, column and box for the same digit with time complexity O(81 · 27) = O(1) and space complexity O(1).

What is the optimal approach and complexity for Valid Sudoku?

Keep a seen-set for every row, column and box; one pass over the board with optimal time complexity O(81) = O(1) and space complexity O(1).

How do you identify the pattern for Valid Sudoku?

Look for key signals in the prompt: "no repeats in each row / column / box" indicates "Have I seen this digit in this group before?" → one seen-set per group.; "3×3 box" indicates Cells must be grouped by box → compute a box key from (r, c) that all cells of a box share.; "only filled cells / not necessarily solvable" indicates This is a checking problem, not a search: one pass, no backtracking..

Valid Sudoku

Medium·LeetCode #36 Pro OnlyMedium

LeetCode

Problem Statement

You are given a 9×9 Sudoku board that is only partly filled. Empty cells hold '.'.

Decide if the board is valid so far. Only look at the filled cells. The board is valid when:

no digit appears twice in the same row,
no digit appears twice in the same column,
no digit appears twice in the same 3×3 box (the nine boxes that split the grid).

You do not need to check whether the puzzle can actually be solved.

Input

board: a 9×9 grid of characters, each '1'–'9' or '.'.

Output

true if no row, column or 3×3 box contains a repeated digit, otherwise false.

Example 1

Input: board = 53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79

Output: true

Every row, column and 3×3 box has each digit at most once.

Example 2

Input: Same board, but the top-left cell is 8 instead of 5

Output: false

Now column 0 has two 8s (rows 0 and 3), and the top-left box also has two 8s (at (0,0) and (2,2)). One repeat is enough to make it invalid.

Constraints

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit '1'–'9' or '.'

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“no repeats in each row / column / box”

→ "Have I seen this digit in this group before?" → one seen-set per group.

“3×3 box”

→ Cells must be grouped by box → compute a box key from (r, c) that all cells of a box share.

“only filled cells / not necessarily solvable”

→ This is a checking problem, not a search: one pass, no backtracking.

Approach Complexity Ladder

Brute Force — scan row, column and box for every cellO(81 · 27) = O(1)O(1)

For each filled cell, look through its row, column and box for the same digit

Optimal — one pass with 27 setsO(81) = O(1)O(1)

Keep a seen-set for every row, column and box; one pass over the board

Brute Force Intuition

Take each filled cell one by one. Walk along its row, down its column and through its 3×3 box, and see if any other cell has the same digit. If any does, the board is invalid.

Recognition rule for this sub-pattern:

Items that should be grouped together produce the same key (sorted string, count signature). Group by that key.

Remember this · Arrays & Hashing

Trigger

"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.

Think

Instead of scanning again for each element, can I remember earlier elements in a map?

Key question

What exactly do I store as the key, and what as the value?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track

C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track

Group Anagrams