36. Valid Sudoku

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/valid-sudoku
• topics: 2D Array

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to 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 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.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set()
        index = {}
        nums.sort()
 
        # Save max index of pivot = candidates for nums[k]
        for i in range(len(nums)-1, -1, -1):
            if not -nums[i] in index:
                index[-nums[i]] = i
 
        prev = float('-inf')
 
        # Loop through sums respecting that i < j < k
        for i in range(len(nums)):
            # Don't use same element twice and filter positiv values
            if nums[i] > 0 or nums[i] == prev:
                continue
            for j in range(i+1, len(nums)):
                two_sum = nums[i] + nums[j]
                if (not two_sum in index or 
                    index[two_sum] <= j or 
                    (nums[i], nums[j]) in ans):
                    continue
                else:
                    ans.add((nums[i], nums[j]))
            prev = nums[i]
        return [[x[0], x[1], -x[0]-x[1]] for x in ans]