36. Valid Sudoku LeetCode Solution

In this guide we will provide 36. Valid Sudoku LeetCode Solution with best time and space complexity. The solution to Valid Sudoku problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Valid Sudoku solution in C++
Valid Sudoku soution in Java
Valid Sudoku solution Python
Additional Resources

36. Valid Sudoku LeetCode Solution image

Problem Statement of Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

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

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: 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: 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
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3×3 sub-box, it is invalid.

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or ‘.’.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(1)

36. Valid Sudoku LeetCode Solution in C++

class Solution {
 public:
  bool isValidSudoku(vector<vector<char>>& board) {
    unordered_set<string> seen;

    for (int i = 0; i < 9; ++i)
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.')
          continue;
        const string c(1, board[i][j]);
        if (!seen.insert(c + "@row" + to_string(i)).second ||
            !seen.insert(c + "@col" + to_string(j)).second ||
            !seen.insert(c + "@box" + to_string(i / 3) + to_string(j / 3))
                 .second)
          return false;
      }

    return true;
  }
};
/* code provided by PROGIEZ */

36. Valid Sudoku LeetCode Solution in Java

class Solution {
  public boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();

    for (int i = 0; i < 9; ++i)
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.')
          continue;
        final char c = board[i][j];
        if (!seen.add(c + "@row" + i) || //
            !seen.add(c + "@col" + j) || //
            !seen.add(c + "@box" + i / 3 + j / 3))
          return false;
      }

    return true;
  }
}
// code provided by PROGIEZ

36. Valid Sudoku LeetCode Solution in Python

class Solution:
  def isValidSudoku(self, board: list[list[str]]) -> bool:
    seen = set()

    for i in range(9):
      for j in range(9):
        c = board[i][j]
        if c == '.':
          continue
        if (c + '@row ' + str(i) in seen or
            c + '@col ' + str(j) in seen or
                c + '@box ' + str(i // 3) + str(j // 3) in seen):
          return False
        seen.add(c + '@row ' + str(i))
        seen.add(c + '@col ' + str(j))
        seen.add(c + '@box ' + str(i // 3) + str(j // 3))

    return True
 #code by PROGIEZ