How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Validate 9x9 grid in one pass | Amazon Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Validate 9x9 grid in one pass states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Validate 9x9 grid in one pass

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given a partially filled 9x9 board using digits '1'–'9' and '.' for empty cells, determine whether the current configuration is valid under Sudoku rules (no duplicates per row, column, or 3x3 sub-box). Provide a one-pass algorithm that detects conflicts during a single scan, describe your data structures (e.g., bitmasks or hash sets), and analyze time and space complexity.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Validate 9x9 grid in one pass states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a partially filled 9x9 Sudoku board represented as a list of 9 rows, each a list of 9 single-character strings using the digits '1'-'9' and '.' for empty cells, determine whether the current configuration is valid. A board is valid if: - Each row contains no duplicate digits. - Each column contains no duplicate digits. - Each of the nine 3x3 sub-boxes contains no duplicate digits. Only the filled cells need to be checked for validity. The board does not need to be solvable. Return True if valid, False otherwise. Solve it in a single pass over the 81 cells. Use bitmasks (one integer per row, per column, and per 3x3 box) or hash sets to detect a conflict the moment a digit repeats within any of its three regions.

Constraints

board.length == 9 and board[i].length == 9
board[i][j] is a digit '1'-'9' or '.'
Only the filled cells must be validated; the board need not be solvable
Must run in a single pass over the 81 cells

Examples

Input: ([['5','3','.','.','7','.','.','.','.'],['6','.','.','1','9','5','.','.','.'],['.','9','8','.','.','.','.','6','.'],['8','.','.','.','6','.','.','.','3'],['4','.','.','8','.','3','.','.','1'],['7','.','.','.','2','.','.','.','6'],['.','6','.','.','.','.','2','8','.'],['.','.','.','4','1','9','.','.','5'],['.','.','.','.','8','.','.','7','9']],)

Expected Output: True

Explanation: The canonical valid LeetCode example board. No row, column, or 3x3 box contains a duplicate digit, so the configuration is valid.

Input: ([['8','3','.','.','7','.','.','.','.'],['6','.','.','1','9','5','.','.','.'],['.','9','8','.','.','.','.','6','.'],['8','.','.','.','6','.','.','.','3'],['4','.','.','8','.','3','.','.','1'],['7','.','.','.','2','.','.','.','6'],['.','6','.','.','.','.','2','8','.'],['.','.','.','4','1','9','.','.','5'],['.','.','.','.','8','.','.','7','9']],)

Expected Output: False

Explanation: Changing the top-left cell from '5' to '8' puts two 8s in the first column (rows 0 and 3) — also two 8s in the top-left 3x3 box — so the board is invalid.

Input: ([['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.']],)

Expected Output: True

Explanation: Edge case: a fully empty board has no filled cells and therefore no conflicts, so it is trivially valid.

Input: ([['5','5','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.']],)

Expected Output: False

Explanation: Two 5s in the same row (and same 3x3 box) at positions (0,0) and (0,1) — a row duplicate makes the board invalid.

Input: ([['5','.','.','.','.','.','.','.','.'],['5','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.'],['.','.','.','.','.','.','.','.','.']],)

Expected Output: False

Explanation: Two 5s in the same column at (0,0) and (1,0) — a column duplicate makes the board invalid.

Hints

Map a 3x3 box to an index with box = (row // 3) * 3 + (col // 3); cells in the same box share this index.
Keep one bitmask integer per row, per column, and per box. For digit d (0-8) the bit is 1 << d.
On each filled cell, if the bit is already set in the row, column, or box mask, you have found a duplicate — return False immediately. Otherwise set the bit in all three masks.
Empty cells ('.') are skipped entirely; they never participate in a conflict.

Quick Overview