Top Interview 150

In this post, we'll solve Valid Sudoku, a classic problem to validate a 9x9 Sudoku board based on specific rules. We'll implement the solution in JavaScript with a clear and efficient approach.

🚀 Problem Description

We are given a 9x9 Sudoku board. The goal is to determine if the current board configuration is valid, based on the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3x3 sub-boxes must contain the digits 1-9 without repetition.

💡 Notes:

• The board can have empty cells represented by ".", which we ignore for validation.
• The board doesn't need to be solvable; we only validate the current state.

💡 Examples

Example 1
Input 1 (Valid):

const board = [
  ["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"],
];

Output:

true

Example 2
Input 2 (Invalid):

const board = [
  ["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"],
];

Output:

false

Constraints

• board.length == 9
• board[i].length == 9
• board[i][j] is "." or a digit ("1" - "9").

🏆 JavaScript Solution

To solve the problem, we validate:

1. Rows: Check if each row contains unique numbers.
2. Columns: Check if each column contains unique numbers.
3. 3x3 Sub-Boxes: Divide the board into 9 sub-boxes (3x3 grids) and validate them for unique numbers.

Implementation

function isValidSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const value = board[r][c];

      if (value === ".") continue;

      const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

      if (rows[r].has(value) || cols[c].has(value) || boxes[boxIndex].has(value)) {
        return false;
      }

      rows[r].add(value);
      cols[c].add(value);
      boxes[boxIndex].add(value);
    }
  }

  return true;
}

🔍 How It Works

1. Initialization:

2. We use three arrays of Set objects to track values in rows, columns, and 3x3 boxes.

3. Iterate through the board:

4. For each cell (r, c):

   • If the cell is empty ("."), skip it.
   • Compute the box index: Math.floor(r / 3) * 3 + Math.floor(c / 3).
   • Check if the value already exists in the corresponding row, column, or box.
   • If it does, return false (invalid board).
   • Otherwise, add the value to the respective row, column, and box.

Return true:

• If all rows, columns, and boxes are valid.

🔑 Complexity Analysis

1. Time Complexity:

   • We traverse all 81 cells of the board once, performing constant-time operations for each cell.
   • O(81) → O(1) (constant time since the board size is fixed).

2. Space Complexity:

   • We use three arrays of size 9 to store sets for rows, columns, and boxes.
   • O(9 × 3) → O(1).

📋 Dry Run

✨ Pro Tips for Interviews

1. Understand the Problem Clearly:

   • Clarify whether the board is guaranteed to be 9x9.
   • Confirm that empty cells are represented as ".".

2. Explain Your Approach:

   • Discuss your plan to use rows, cols, and boxes sets for tracking.
   • Highlight why this approach works and how it efficiently detects duplicates.

3. Time and Space Complexity:

   • State that the algorithm runs in O(81) ≈ O(1) time due to fixed board size.
   • Space complexity is O(27) ≈ O(1) for the 27 sets.

4. Edge Cases:

   • An empty board (all ".") → should return true.
   • A nearly full but invalid board (e.g., duplicates in rows/columns/boxes) → ensure detection.
   • Single-row/column boards (if the board can be non-standard).

5. Code Readability:

   • Use clear variable names like rows, cols, boxes.
   • Avoid hardcoding; calculate the box index dynamically.

6. Don’t Overcomplicate:

   • Stick to the validation problem. Avoid solving the Sudoku or handling invalid input unless explicitly asked.

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Minimum Window Substring - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀