The O(n) Club: Valid Sudoku—How Not to Ruin Your Day (or Tech Interview)

The O(n) Club: Valid Sudoku—How Not to Ruin Your Day (or Tech Interview)

⚡ TL;DR

Validating Sudoku isn’t about flexing galaxy-brain backtracking. Just spot duplicate digits in any row, column, or 3×3 box—ignore empty cells, and don’t you dare try to fill them. Here’s your Java pseudocode cheat sheet:

// Nine sets for row/col/box sanity
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        char digit = board[i][j];
        if (digit == '.') continue;
        int box = (i / 3) * 3 + (j / 3);
        // If digit found in any, snap False
        // Otherwise, add digit everywhere
    }
}
// No snags? Board’s valid.

🧠 How Devs Usually Mess This Up

Raise your hand if you’ve tried to “solve” the Sudoku instead of just checking its vibe. 👋

Classic missteps include:

🔍 What’s Actually Going On

You’re running a nightclub (the Sudoku board). Rows, columns, and boxes are bouncers. Every time a number shows up, all three bouncers check their VIP lists—if the number’s already had its fun, they throw it out. The only real trick: mapping (i, j) to the right box. Treat empty cells like invisible partygoers; the bouncers won’t notice or care.

🛠️ PseudoCode

• Initialize three arrays of sets: one for rows, one for columns, one for boxes.
  • Set<Character>[] rows = new HashSet[9];
  • Set<Character>[] cols = new HashSet[9];
  • Set<Character>[] boxes = new HashSet[9];
• For every cell (i, j):
  • If board[i][j] is ‘.’, continue (go take a coffee sip).
  • Digit wants in? Use int box = (i / 3) * 3 + (j / 3); to figure out which box it’s partying in.
  • If this digit is in rows[i], cols[j], or boxes[box], return false (party pooper detected).
  • Otherwise, add digit to all three sets and carry on.
• If you finish without drama, return true.

💻 The Code

import java.util.HashSet;
 public class ValidSudoku {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character>[] rows = new HashSet[9];
        HashSet<Character>[] cols = new HashSet[9];
        HashSet<Character>[] boxes = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char digit = board[i][j];
                if (digit == '.') continue;
                int box = (i / 3) * 3 + (j / 3);
                if (rows[i].contains(digit) || cols[j].contains(digit) || boxes[box].contains(digit))
                    return false;
                rows[i].add(digit);
                cols[j].add(digit);
                boxes[box].add(digit);
            }
        }
        return true;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Never add or check ‘.’—if it’s not a digit, it doesn’t exist. Don’t snitch on blank cells.
• Botch the 3×3 box formula and you’re validating some alternate Sudoku dimension.
• No, you can’t “optimize” this: the board’s tiny. Time/space are O(1). Life is short.
• Sudoku grids bigger than 9×9? Politely decline and ask for a pizza instead.

🧠 Interviewer Brain-Tattoo

“The best validator is the one that doesn’t accidentally become a solver. Stay lazy, stay correct, stay employed.”