Skip to main content

Leetcode 36: Valid Sudoku

 

1. Problem Statement (Simple Explanation):


You’re given a 9×9 Sudoku board (char[9][9]), partially filled.

You must determine if the board is valid according to Sudoku rules for the filled cells only:

  1. Each row must contain digits 1-9 without repetition.

  2. Each column must contain digits 1-9 without repetition.

  3. Each of the nine 3×3 sub-boxes must contain digits 1-9 without repetition.

Notes:

  • Empty cells are denoted by '.' and can be ignored.

  • A valid board might not be solvable; you only validate current filled cells.


2. Examples:


Example 1 (Valid):


[["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 (Invalid):


Same as Example 1 but top-left '5' changed to '8':

[["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"]]

Two 8s in the top-left 3×3 sub-box → invalid.

Output: false


3. Approach – Track Seen Digits in Rows, Columns, and Boxes:


We need to check three constraints simultaneously:

  • For each row r, digits 1..9 appear at most once.

  • For each column c, digits 1..9 appear at most once.

  • For each 3×3 box b, digits 1..9 appear at most once.

We can use boolean arrays or sets.


Indexing 3×3 boxes:


For a cell at row r, column c:

  • boxIndex = (r / 3) * 3 + (c / 3)

This gives box indices 0..8:

  • Rows 0–2, Cols 0–2 → box 0

  • Rows 0–2, Cols 3–5 → box 1

  • ...

  • Rows 3–5, Cols 0–2 → box 3

  • Etc.


Data Structures:


Use 3 boolean matrices:

  • rows[9][9] – rows[r][d] is true if digit d+1 seen in row r.

  • cols[9][9] – cols[c][d] is true if digit d+1 seen in column c.

  • boxes[9][9] – boxes[b][d] is true if digit d+1 seen in box b.

Where d = board[r][c] - '1' (0-based index for digits 1..9).


Algorithm (Step-by-Step):


  1. Initialize rows, cols, boxes to all false.

  2. Loop over all cells r = 0..8, c = 0..8:

    • If board[r][c] == '.', continue.

    • Compute:

      • val = board[r][c] - '1' (0 to 8)

      • boxIndex = (r / 3) * 3 + (c / 3)

    • If rows[r][val] or cols[c][val] or boxes[boxIndex][val] is already true:

      • Return false (duplicate digit in row / column / box).

    • Otherwise:

      • Set rows[r][val] = cols[c][val] = boxes[boxIndex][val] = true.

  3. If we finish the loops without conflict, return true.


Pseudo-code:



Complexity:


  • Board has fixed size 9×9 = 81.

  • Time: O(1)  in practice (81 operations).

  • Space: O(1)  (3×9×9 booleans).

Asymptotically, O(N2) for N×N Sudoku, but constant for N=9.


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more