algoadvance

Leetcode 36. Valid Sudoku

Problem Statement

Determine if a 9x9 Sudoku board is valid. A Sudoku board is valid if:

1. Each row contains the digits 1-9 without repetition.
2. Each column contains the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid contains the digits 1-9 without repetition.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Clarifying Questions

1. Input constraints: Is the board always 9x9?
   • Yes, you can assume the board is always 9x9.
2. Characters: Confirm that only digits (‘1’-‘9’) and ‘.’ are valid characters in the grid.
   • Yes, only ‘1’-‘9’ and ‘.’ will appear in the grid.
3. Input format: Is the input provided as a vector of vector of chars?
   • Yes, the input is provided as a vector of vector of chars.

Strategy

To determine if the Sudoku board is valid:

1. Use three 2D arrays (rows, cols, boxes) to keep track of the digits we have seen in each row, column, and 3x3 box.
2. Iterate over each cell of the board.
3. For each digit:
   • Check if it has already appeared in the current row, column, or 3x3 box using the rows, cols, and boxes arrays.
   • If it has, return false immediately since the board is invalid.
   • Otherwise, mark this digit as seen in the respective row, column, and 3x3 box.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> rows(9, vector<bool>(9, false));
        vector<vector<bool>> cols(9, vector<bool>(9, false));
        vector<vector<bool>> boxes(9, vector<bool>(9, false));

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '1'; // convert char to int (0-8)
                int boxIndex = (i / 3) * 3 + j / 3;
                if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
                    return false;
                }
                rows[i][num] = cols[j][num] = boxes[boxIndex][num] = true;
            }
        }

        return true;
    }
};

Time Complexity

• Time Complexity: O(1)
  • We iterate over each cell in the 9x9 board exactly once, performing constant-time operations for each cell.
• Space Complexity: O(1)
  • We use three 2D arrays of fixed size 9x9, which is effectively a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?