Leetcode: Valid Sudoku

Valid Sudoku | LeetCode OJ

To validate a sudoku, we need to check for the following things

1. All 9 rows should have only one occurrence of numbers 1–9
2. All 9 columns should have only one occurrence of numbers 1–9
3. All 9 boxes should have only one occurrence of numbers 1–9

Each value belongs to a row, a column and a box. So out of the 27 sets we check in the relevant ones for duplicates before inserting the current value.

If we find duplicate then its not a valid sudoku, otherwise its valid.

Remarks:

1. O(9*9) time complexity for iterating through the input
2. O(3*9*9) space complexity as we need to store each number in 3 different sets

from collections import defaultdict

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        res = defaultdict(list)
        for i, row in enumerate(board):
            for j, val in enumerate(row):
                if val != ".":
                    if val in res[3 * (i // 3) + j // 3 + 20] or val in res[i + 10] or val in res[j]:
                        return False
                    res[3 * (i // 3) + j // 3 + 20].append(val)
                    res[i + 10].append(val)
                    res[j].append(val)
        return True