Sudoku board integrity check

You're sitting in an Adobe interview when the interviewer pulls up a partially filled Sudoku grid on the screen. "Forget about solving it," they say. "I just want to know if what's already on the board is legal." This problem, also known as Valid Sudoku on other platforms, is a favorite at companies like Adobe, Amazon, and Riot Games because it tests your ability to decompose a problem into independent validation checks and choose the right data structures to support them.

TL;DR

Iterate through the 9x9 board and use HashSets to track which digits have appeared in each row, column, and 3x3 sub-box. If a digit appears twice in any group, the board is invalid. Skip empty cells (represented by '.'). Since the board is always 9x9, both time and space complexity are O(1).

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

Sudoku validation is a clean example of constraint checking on a fixed-size grid. It combines array traversal, hash-based duplicate detection, and index arithmetic for sub-box mapping. These skills transfer directly to problems involving matrix validation, game state verification, and multi-dimensional data integrity checks. If you can break a Sudoku board into its three independent constraints and validate each one, you'll find similar decomposition patterns in many other interview problems.

Understanding the Problem

A valid Sudoku board must satisfy three rules simultaneously:

1. Each row contains digits 1-9 with no duplicates.
2. Each column contains digits 1-9 with no duplicates.
3. Each 3x3 sub-box contains digits 1-9 with no duplicates.

Empty cells (marked with '.') are ignored during validation. The board does not need to be solvable, it just needs to have no conflicts among the filled cells.

Here is a partial view of the example board. Filled cells are highlighted:

This board is valid because no row, column, or sub-box contains a repeated digit among its filled cells.

Edge Cases to Consider

1. All empty board: Every cell is '.'. This is valid since there are no digits to conflict.
2. Duplicate in a row: Two identical digits in the same row means invalid.
3. Duplicate in a column: Same digit appearing twice in the same column.
4. Duplicate in a sub-box: A repeated digit within the same 3x3 region, even if the row and column checks pass individually.

Breaking Down the Three Checks

The strategy is straightforward: check each constraint independently. Let's walk through them one at a time.

Check 1: Rows

For each of the 9 rows, scan left to right and track which digits you have seen. If you encounter a digit that is already in the set, return false.

Row 0 is being validated. The digits 5, 3, and 7 are unique, so this row passes.

Check 2: Columns

For each of the 9 columns, scan top to bottom using the same duplicate-detection logic.

Column 0 is being validated. The digits 5, 6, 8, 4, and 7 are all unique, so this column passes.

Check 3: Sub-Boxes

The 9x9 board contains nine 3x3 sub-boxes. For each sub-box, collect all filled digits and check for duplicates. The tricky part is mapping cell coordinates to the correct sub-box.

The top-left 3x3 sub-box (highlighted in orange) contains digits 5, 3, 6, 9, and 8. No duplicates, so it passes.

The sub-box starting row and column are computed using integer division: for a cell at (i, j), the sub-box starts at row (i / 3) * 3 and column (j / 3) * 3. This maps every cell to one of the nine non-overlapping 3x3 regions.

Detecting an Invalid Board

Consider this modified board where the first cell is changed from 5 to 8:

Both board[0][0] and board[3][0] contain 8 (highlighted in orange). Column 0 has a duplicate, so the board is invalid.

Implementation

Here is the Java solution that validates each constraint with a separate loop. Each loop creates a fresh HashSet for the group being checked.

import java.util.HashSet;

public class Solution {
  public boolean isValidSudoku(char[][] board) {
    // Check each row for duplicate digits
    for (int i = 0; i < 9; i++) {
      HashSet<Character> rowSet = new HashSet<>();
      for (int j = 0; j < 9; j++) {
        char current = board[i][j];
        if (current != '.') {
          if (rowSet.contains(current)) {
            return false;
          }
          rowSet.add(current);
        }
      }
    }

    // Check each column for duplicate digits
    for (int j = 0; j < 9; j++) {
      HashSet<Character> colSet = new HashSet<>();
      for (int i = 0; i < 9; i++) {
        char current = board[i][j];
        if (current != '.') {
          if (colSet.contains(current)) {
            return false;
          }
          colSet.add(current);
        }
      }
    }

    // Check each 3x3 sub-box for duplicate digits
    for (int boxRow = 0; boxRow < 3; boxRow++) {
      for (int boxCol = 0; boxCol < 3; boxCol++) {
        HashSet<Character> boxSet = new HashSet<>();
        for (int i = 0; i < 3; i++) {
          for (int j = 0; j < 3; j++) {
            char current = board[boxRow * 3 + i][boxCol * 3 + j];
            if (current != '.') {
              if (boxSet.contains(current)) {
                return false;
              }
              boxSet.add(current);
            }
          }
        }
      }
    }

    return true;
  }
}

The structure is deliberately repetitive. Each validation block follows the same pattern: create a set, iterate through the group, skip dots, check-then-add. This makes the code easy to reason about during an interview.

Walkthrough with the Example

Let's trace through the first few iterations with the valid board:

Row 0: Scan cells [5, 3, ., ., 7, ., ., ., .]. After filtering dots, the set contains {5, 3, 7}. No duplicates. Pass.

Row 1: Scan cells [6, ., ., 1, 9, 5, ., ., .]. Set becomes {6, 1, 9, 5}. No duplicates. Pass.

Column 0: Scan cells [5, 6, ., 8, 4, 7, ., ., .]. Set becomes {5, 6, 8, 4, 7}. No duplicates. Pass.

Sub-box (0,0): Cells at rows 0-2, columns 0-2 give us [5, 3, ., 6, ., ., ., 9, 8]. Set becomes {5, 3, 6, 9, 8}. No duplicates. Pass.

All 9 rows, 9 columns, and 9 sub-boxes pass. Return true.

Complexity Analysis

Time Complexity: O(1)

The board is always 9x9, meaning we always process exactly 81 cells. The three separate passes each iterate through all 81 cells, for a total of 243 cell visits. HashSet operations (contains and add) are O(1) amortized. Since the input size is fixed, the total work is constant.

If the problem were generalized to an n x n board, the complexity would be O(n^2).

Space Complexity: O(1)

Each HashSet holds at most 9 elements (one per digit). We create at most 9 sets at a time (one per row, column, or sub-box check). The total extra memory is bounded by a constant regardless of the cell values.

Single-Pass Optimization

You can combine all three checks into a single pass through the board. Instead of separate loops, maintain 9 row sets, 9 column sets, and 9 box sets simultaneously:

for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        char current = board[i][j];
        if (current == '.') continue;
        int boxIndex = (i / 3) * 3 + j / 3;
        if (!rowSets[i].add(current) ||
            !colSets[j].add(current) ||
            !boxSets[boxIndex].add(current)) {
            return false;
        }
    }
}

This trades slightly more memory (27 sets alive at once instead of 9) for fewer iterations. The asymptotic complexity stays the same, but the constant factor improves. Mentioning this optimization in an interview shows strong problem-solving awareness.

Common Pitfalls

1. Forgetting to skip empty cells: Every check must ignore '.' characters. Adding dots to your set will cause false negatives since dots repeat across the board.

2. Wrong sub-box index formula: The formula (i / 3) * 3 + j / 3 uses integer division. Getting this wrong will map cells to incorrect sub-boxes and produce wrong results.

3. Checking if the board is solvable: The problem only asks for constraint validation on filled cells. Do not attempt to verify whether the puzzle has a valid solution.

4. Using the wrong data type: In Java, board[i][j] returns a char. Make sure your HashSet uses Character, not String.

Interview Tips

When solving this problem in an interview:

1. Clarify the scope: "Am I checking validity of filled cells only, or also verifying the board is solvable?" This shows you understand the distinction.

2. Start with the three-pass approach: It is clearer and easier to get right. Once your interviewer confirms correctness, offer the single-pass optimization.

3. Explain the sub-box index math: Walk through a concrete example. "Cell (4, 7) maps to sub-box (4/3)*3 + 7/3 = 3 + 2 = 5." This demonstrates you understand the formula rather than memorizing it.

4. Mention the constant complexity: Since the board is fixed at 9x9, clarify that your O(1) answer is for this specific problem. Show awareness that a generalized n x n version would be O(n^2).

5. Anticipate follow-ups: Be ready to discuss solving the board with backtracking, or how you would extend validation to non-standard Sudoku sizes.

Key Takeaways

• Decompose the problem into three independent constraint checks (rows, columns, sub-boxes) and validate each with a HashSet for O(1) duplicate detection.
• The sub-box index formula (i / 3) * 3 + j / 3 maps any cell to its 3x3 region. Practice deriving this formula rather than memorizing it.
• Both time and space are O(1) because the 9x9 board is a fixed-size input. Always clarify this with your interviewer.
• The three-pass approach is interview-friendly due to its clarity. Offer the single-pass optimization as a follow-up to demonstrate depth.
• Skip empty cells early. Adding '.' to your tracking sets is the most common bug in this problem.

Practice Makes Perfect

Once you are comfortable with Sudoku validation, try these related problems to strengthen your matrix and hash table skills:

• Image Matrix 90 Degree Twist (rotation and index arithmetic on grids)
• Zero Out Rows and Columns (matrix modification with tracking sets)
• Matrix Spiral Traversal (index management in 2D arrays)

Solutions in Other Languages

Python

class Solution:
    def is_valid_sudoku(self, board):
        def is_valid_block(block):
            block = [num for num in block if num != '.']
            return len(block) == len(set(block))

        for row in board:
            if not is_valid_block(row):
                return False

        for col in range(9):
            if not is_valid_block([board[row][col] for row in range(9)]):
                return False

        for box_row in range(0, 9, 3):
            for box_col in range(0, 9, 3):
                block = [
                    board[r][c]
                    for r in range(box_row, box_row + 3)
                    for c in range(box_col, box_col + 3)
                ]
                if not is_valid_block(block):
                    return False

        return True

The Python solution uses a helper function is_valid_block that filters dots and checks for duplicates using set length comparison. List comprehensions extract columns and sub-boxes cleanly.

JavaScript

class Solution {
  isValidSudoku(board) {
    const isValid = (set, value) => {
      if (value === '.') return true;
      if (set.has(value)) return false;
      set.add(value);
      return true;
    };

    for (let i = 0; i < 9; i++) {
      const rows = new Set();
      const cols = new Set();
      const box = new Set();

      for (let j = 0; j < 9; j++) {
        if (!isValid(rows, board[i][j]) ||
            !isValid(cols, board[j][i]) ||
            !isValid(box, board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)])) {
          return false;
        }
      }
    }

    return true;
  }
}

The JavaScript version uses a single-pass approach, checking rows, columns, and sub-boxes simultaneously with a helper function that combines the contains-check and add operations.

TypeScript

class Solution {
  isValidSudoku(board: string[][]): boolean {
    const isValid = (set: Set<string>, value: string): boolean => {
      if (value === '.') return true;
      if (set.has(value)) return false;
      set.add(value);
      return true;
    };

    for (let i = 0; i < 9; i++) {
      const rows = new Set<string>();
      const cols = new Set<string>();
      const box = new Set<string>();

      for (let j = 0; j < 9; j++) {
        if (!isValid(rows, board[i][j]) ||
            !isValid(cols, board[j][i]) ||
            !isValid(box, board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)])) {
          return false;
        }
      }
    }

    return true;
  }
}

Identical to the JavaScript solution with added type annotations for the board parameter, return type, and Set generic types.

C++

#include <vector>
#include <unordered_set>

class Solution {
public:
  bool isValidSudoku(std::vector<std::vector<char>> &board) {
    for (int i = 0; i < 9; ++i) {
      std::unordered_set<char> rowSet;
      for (int j = 0; j < 9; ++j) {
        char current = board[i][j];
        if (current != '.') {
          if (rowSet.find(current) != rowSet.end()) return false;
          rowSet.insert(current);
        }
      }
    }

    for (int j = 0; j < 9; ++j) {
      std::unordered_set<char> colSet;
      for (int i = 0; i < 9; ++i) {
        char current = board[i][j];
        if (current != '.') {
          if (colSet.find(current) != colSet.end()) return false;
          colSet.insert(current);
        }
      }
    }

    for (int boxRow = 0; boxRow < 3; ++boxRow) {
      for (int boxCol = 0; boxCol < 3; ++boxCol) {
        std::unordered_set<char> boxSet;
        for (int i = 0; i < 3; ++i) {
          for (int j = 0; j < 3; ++j) {
            char current = board[boxRow * 3 + i][boxCol * 3 + j];
            if (current != '.') {
              if (boxSet.find(current) != boxSet.end()) return false;
              boxSet.insert(current);
            }
          }
        }
      }
    }

    return true;
  }
};

The C++ version mirrors the Java approach, using std::unordered_set for O(1) average-case lookups. The board is passed by reference to avoid copying.

Go

func (s *Solution) IsValidSudoku(board [][]byte) bool {
    rows := make([]map[byte]bool, 9)
    cols := make([]map[byte]bool, 9)
    boxes := make([]map[byte]bool, 9)

    for i := 0; i < 9; i++ {
        rows[i] = make(map[byte]bool)
        cols[i] = make(map[byte]bool)
        boxes[i] = make(map[byte]bool)
    }

    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            num := board[i][j]
            if num == '.' {
                continue
            }
            if rows[i][num] {
                return false
            }
            rows[i][num] = true

            if cols[j][num] {
                return false
            }
            cols[j][num] = true

            boxIndex := (i/3)*3 + j/3
            if boxes[boxIndex][num] {
                return false
            }
            boxes[boxIndex][num] = true
        }
    }

    return true
}

The Go solution uses a single-pass approach with maps for each row, column, and box. Go maps return the zero value (false) for missing keys, making the duplicate check concise.

Scala

class Solution {
  def isValidSudoku(board: Array[Array[Char]]): Boolean = {
    def isValidBlock(block: Seq[Char]): Boolean = {
      val digits = block.filter(_ != '.')
      digits.distinct.length == digits.length
    }

    def isValidRow(row: Int): Boolean = isValidBlock(board(row))

    def isValidColumn(col: Int): Boolean = isValidBlock(board.map(_(col)))

    def isValidSubBox(row: Int, col: Int): Boolean = {
      val subBox = for {
        r <- row until row + 3
        c <- col until col + 3
      } yield board(r)(c)
      isValidBlock(subBox)
    }

    val rowsValid = (0 until 9).forall(isValidRow)
    val colsValid = (0 until 9).forall(isValidColumn)
    val subBoxesValid = (0 until 9 by 3).forall { r =>
      (0 until 9 by 3).forall { c =>
        isValidSubBox(r, c)
      }
    }

    rowsValid && colsValid && subBoxesValid
  }
}

The Scala version takes a functional approach. The isValidBlock helper filters dots and compares distinct length to total length. The forall combinator checks all groups at once.

Kotlin

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        for (i in 0 until 9) {
            val rowSet = mutableSetOf<Char>()
            for (j in 0 until 9) {
                val current = board[i][j]
                if (current != '.') {
                    if (current in rowSet) return false
                    rowSet.add(current)
                }
            }
        }

        for (j in 0 until 9) {
            val colSet = mutableSetOf<Char>()
            for (i in 0 until 9) {
                val current = board[i][j]
                if (current != '.') {
                    if (current in colSet) return false
                    colSet.add(current)
                }
            }
        }

        for (boxRow in 0 until 3) {
            for (boxCol in 0 until 3) {
                val boxSet = mutableSetOf<Char>()
                for (i in 0 until 3) {
                    for (j in 0 until 3) {
                        val current = board[boxRow * 3 + i][boxCol * 3 + j]
                        if (current != '.') {
                            if (current in boxSet) return false
                            boxSet.add(current)
                        }
                    }
                }
            }
        }

        return true
    }
}

Kotlin uses mutableSetOf and the in operator for readable duplicate checking. The structure matches the Java solution closely.

Rust

use std::collections::HashSet;

impl Solution {
    pub fn is_valid_sudoku(&self, board: Vec<Vec<char>>) -> bool {
        for i in 0..9 {
            let mut row_set = HashSet::new();
            for j in 0..9 {
                let current = board[i][j];
                if current != '.' {
                    if row_set.contains(&current) { return false; }
                    row_set.insert(current);
                }
            }
        }

        for j in 0..9 {
            let mut col_set = HashSet::new();
            for i in 0..9 {
                let current = board[i][j];
                if current != '.' {
                    if col_set.contains(&current) { return false; }
                    col_set.insert(current);
                }
            }
        }

        for box_row in 0..3 {
            for box_col in 0..3 {
                let mut box_set = HashSet::new();
                for i in 0..3 {
                    for j in 0..3 {
                        let current = board[box_row * 3 + i][box_col * 3 + j];
                        if current != '.' {
                            if box_set.contains(&current) { return false; }
                            box_set.insert(current);
                        }
                    }
                }
            }
        }

        true
    }
}

Rust's HashSet requires borrowing with &current for the contains check. The ownership model means the board is consumed by this function.

Ruby

require 'set'

class Solution
  def is_valid_sudoku(board)
    (0...9).each do |i|
      row_set = Set.new
      (0...9).each do |j|
        current = board[i][j]
        if current != '.'
          return false if row_set.include?(current)
          row_set.add(current)
        end
      end
    end

    (0...9).each do |j|
      col_set = Set.new
      (0...9).each do |i|
        current = board[i][j]
        if current != '.'
          return false if col_set.include?(current)
          col_set.add(current)
        end
      end
    end

    (0...3).each do |box_row|
      (0...3).each do |box_col|
        box_set = Set.new
        (0...3).each do |i|
          (0...3).each do |j|
            current = board[box_row * 3 + i][box_col * 3 + j]
            if current != '.'
              return false if box_set.include?(current)
              box_set.add(current)
            end
          end
        end
      end
    end

    true
  end
end

Ruby uses the Set class from the standard library. The exclusive range operator ... provides clean 0-based iteration.

Dart

class Solution {
  bool isValidSudoku(List<List<String>> board) {
    for (int i = 0; i < 9; i++) {
      Set<String> rowSet = {};
      for (int j = 0; j < 9; j++) {
        String current = board[i][j];
        if (current != '.') {
          if (rowSet.contains(current)) return false;
          rowSet.add(current);
        }
      }
    }

    for (int j = 0; j < 9; j++) {
      Set<String> colSet = {};
      for (int i = 0; i < 9; i++) {
        String current = board[i][j];
        if (current != '.') {
          if (colSet.contains(current)) return false;
          colSet.add(current);
        }
      }
    }

    for (int boxRow = 0; boxRow < 3; boxRow++) {
      for (int boxCol = 0; boxCol < 3; boxCol++) {
        Set<String> boxSet = {};
        for (int i = 0; i < 3; i++) {
          for (int j = 0; j < 3; j++) {
            String current = board[boxRow * 3 + i][boxCol * 3 + j];
            if (current != '.') {
              if (boxSet.contains(current)) return false;
              boxSet.add(current);
            }
          }
        }
      }
    }

    return true;
  }
}

Dart's Set literal syntax {} and String type make this implementation straightforward.

C#

using System.Collections.Generic;

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            var rowSet = new HashSet<char>();
            for (int j = 0; j < 9; j++) {
                var current = board[i][j];
                if (current != '.') {
                    if (rowSet.Contains(current)) return false;
                    rowSet.Add(current);
                }
            }
        }

        for (int j = 0; j < 9; j++) {
            var colSet = new HashSet<char>();
            for (int i = 0; i < 9; i++) {
                var current = board[i][j];
                if (current != '.') {
                    if (colSet.Contains(current)) return false;
                    colSet.Add(current);
                }
            }
        }

        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                var boxSet = new HashSet<char>();
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        var current = board[boxRow * 3 + i][boxCol * 3 + j];
                        if (current != '.') {
                            if (boxSet.Contains(current)) return false;
                            boxSet.Add(current);
                        }
                    }
                }
            }
        }

        return true;
    }
}

C# uses HashSet<char> with Contains and Add methods. The var keyword keeps declarations concise.

Swift

import Foundation

class Solution {
    func isValidSudoku(_ board: [[Character]]) -> Bool {
        for i in 0..<9 {
            var rowSet = Set<Character>()
            for j in 0..<9 {
                let current = board[i][j]
                if current != Character(".") {
                    if rowSet.contains(current) { return false }
                    rowSet.insert(current)
                }
            }
        }

        for j in 0..<9 {
            var colSet = Set<Character>()
            for i in 0..<9 {
                let current = board[i][j]
                if current != Character(".") {
                    if colSet.contains(current) { return false }
                    colSet.insert(current)
                }
            }
        }

        for boxRow in 0..<3 {
            for boxCol in 0..<3 {
                var boxSet = Set<Character>()
                for i in 0..<3 {
                    for j in 0..<3 {
                        let current = board[boxRow * 3 + i][boxCol * 3 + j]
                        if current != Character(".") {
                            if boxSet.contains(current) { return false }
                            boxSet.insert(current)
                        }
                    }
                }
            }
        }

        return true
    }
}

Swift compares characters using Character(".") rather than a char literal. The half-open range operator ..< handles 0-based indexing naturally.

PHP

class Solution {
    public function isValidSudoku(array $board): bool {
        for ($i = 0; $i < 9; $i++) {
            $rowSet = [];
            for ($j = 0; $j < 9; $j++) {
                $current = $board[$i][$j];
                if ($current !== '.') {
                    if (isset($rowSet[$current])) return false;
                    $rowSet[$current] = true;
                }
            }
        }

        for ($j = 0; $j < 9; $j++) {
            $colSet = [];
            for ($i = 0; $i < 9; $i++) {
                $current = $board[$i][$j];
                if ($current !== '.') {
                    if (isset($colSet[$current])) return false;
                    $colSet[$current] = true;
                }
            }
        }

        for ($boxRow = 0; $boxRow < 3; $boxRow++) {
            for ($boxCol = 0; $boxCol < 3; $boxCol++) {
                $boxSet = [];
                for ($i = 0; $i < 3; $i++) {
                    for ($j = 0; $j < 3; $j++) {
                        $current = $board[$boxRow * 3 + $i][$boxCol * 3 + $j];
                        if ($current !== '.') {
                            if (isset($boxSet[$current])) return false;
                            $boxSet[$current] = true;
                        }
                    }
                }
            }
        }

        return true;
    }
}

PHP uses associative arrays with isset() for set-like behavior. The strict comparison !== ensures type-safe checks against the dot character.

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies.