What is the time complexity of Valid Sudoku?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Valid Sudoku?

This problem uses Array, Hash Table, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Valid Sudoku?

Insight 1: We need to efficiently check for the presence of a digit within a row, column, and 3x3 sub-box. Insight 2: Using a set (or hash table) is an efficient way to track which numbers have already been seen in a row, column, or sub-box. Its fast O(1) lookup is crucial.

Which companies ask LeetCode 36. Valid Sudoku in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Attentive, Autodesk and 25 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Valid Sudoku - LeetCode 36 Solution

Valid Sudoku - Complete Solution Guide

Valid Sudoku is LeetCode problem 36, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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. Exa

Detailed Explanation

The problem 'Valid Sudoku' asks us to determine whether a given 9x9 Sudoku board is valid. A Sudoku board is valid if the following three conditions are met: 1. Each row contains the digits 1-9 without any repetition. 2. Each column contains the digits 1-9 without any repetition. 3. Each of the nine 3x3 sub-boxes (also called blocks or regions) of the grid contains the digits 1-9 without any repetition. It's important to note that the input Sudoku board might be partially filled, meaning it can contain empty cells represented by the character '.'. We only need to check if the filled cells violate the Sudoku rules. The board is not necessarily solvable, just needs to be a valid configuration so far.

Solution Approach

The provided solution uses a single set (`seen`) to keep track of the numbers encountered in each row, column, and 3x3 sub-box. For each cell in the board, it checks if the cell contains a digit (not a '.'). If it does, it generates three unique keys: one for the row, one for the column, and one for the 3x3 sub-box the cell belongs to. These keys include the row index, column index, and sub-box indices, and the digit in the cell. Before adding these keys to the `seen` set, the solution checks if any of them are already present. If any key is already in the set, it means that the same digit has been encountered before in the same row, column, or sub-box, violating the Sudoku rules. If all keys are new, they are added to the set, and the algorithm continues. If no violations are found after iterating through all the cells, the board is valid.

Step-by-Step Algorithm

Step 1: Initialize an empty set called `seen` to store the keys.
Step 2: Iterate through each cell of the 9x9 Sudoku board using nested loops.
Step 3: For each cell, check if it contains a digit (i.e., it's not a '.').
Step 4: If the cell contains a digit, generate three unique keys:
a. `row_key`: Represents the row constraint (e.g., 'row05' indicates the digit '5' in row 0).
b. `col_key`: Represents the column constraint (e.g., 'col15' indicates the digit '5' in column 1).
c. `box_key`: Represents the 3x3 sub-box constraint (e.g., 'box005' indicates the digit '5' in the top-left sub-box).
Step 5: Check if any of the generated keys are already present in the `seen` set. If any key is found, it means there's a duplicate digit in that row, column, or sub-box, and the Sudoku board is invalid. Return `false`.
Step 6: If all three keys are new (not found in the `seen` set), add them to the `seen` set.
Step 7: After iterating through all the cells, if no duplicates were found, the Sudoku board is valid. Return `true`.

Key Insights

Insight 1: We need to efficiently check for the presence of a digit within a row, column, and 3x3 sub-box.
Insight 2: Using a set (or hash table) is an efficient way to track which numbers have already been seen in a row, column, or sub-box. Its fast O(1) lookup is crucial.
Insight 3: Representing the row, column, and sub-box constraints as unique strings (or tuples) allows a single set to manage validation across all three rules simultaneously.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Array, Hash Table, Matrix.

Companies

Asked at: Adobe, Amazon, Apple, Attentive, Autodesk, Bloomberg, Confluent, DoorDash, Geico, Goldman Sachs, Instacart, Karat, Media.net, Meta, Microsoft, MongoDB, Nvidia, Oracle, PayPal, Riot Games, Samsara, Snap, TikTok, Uber, Veeva Systems, Visa, Walmart Labs, Waymo, Yahoo, Zoho.

Valid Sudoku | LeetCode 36

Medium

Array Hash Table Matrix

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

Solution Code

Available in:

import java.util.HashSet;
import java.util.Set;

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++) {
                char num = board[i][j];
                if (num != '.') {
                    String row_key = "row" + i + num;
                    String col_key = "col" + j + num;
                    String box_key = "box" + i / 3 + j / 3 + num;

                    if (seen.contains(row_key) || seen.contains(col_key) || seen.contains(box_key)) {
                        return false;
                    }

                    seen.add(row_key);
                    seen.add(col_key);
                    seen.add(box_key);
                }
            }
        }
        return true;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 36: Valid Sudoku - Detailed explanation and solution approaches.

Topics

Array Hash Table Matrix

Companies

AdobeAmazonAppleAttentiveAutodeskBloombergConfluentDoorDash

Stats

Difficulty:Medium

Languages:4

Companies:30

Problem #:36

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize an empty set called `seen` to store the keys.
2
Step 2: Iterate through each cell of the 9x9 Sudoku board using nested loops.
3
Step 3: For each cell, check if it contains a digit (i.e., it's not a '.').
4
Step 4: If the cell contains a digit, generate three unique keys:
5
a. `row_key`: Represents the row constraint (e.g., 'row05' indicates the digit '5' in row 0).
6
b. `col_key`: Represents the column constraint (e.g., 'col15' indicates the digit '5' in column 1).
7
c. `box_key`: Represents the 3x3 sub-box constraint (e.g., 'box005' indicates the digit '5' in the top-left sub-box).
8
Step 5: Check if any of the generated keys are already present in the `seen` set. If any key is found, it means there's a duplicate digit in that row, column, or sub-box, and the Sudoku board is invalid. Return `false`.
9
Step 6: If all three keys are new (not found in the `seen` set), add them to the `seen` set.
10
Step 7: After iterating through all the cells, if no duplicates were found, the Sudoku board is valid. Return `true`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(1) because the input size is fixed (9x9 Sudoku board). The algorithm iterates through all 81 cells of the board. The operations inside the loop (generating keys, checking the set, and adding to the set) are all O(1) operations on average. The space complexity is also O(1) because the `seen` set can hold at most 9 * 3 = 27 elements (9 possible digits in each of the 9 rows, 9 columns and 9 boxes). Because this is a fixed maximum, the space required is constant.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Separate Sets for Rows, Columns, and Boxes

Instead of using a single set to track all constraints, we could use three separate sets: one for rows, one for columns, and one for 3x3 sub-boxes. Each set would store the digits encountered in its respective row, column, or sub-box.

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

Trade-offs: This approach may be slightly easier to understand for some, as it explicitly separates the different constraints. However, it might be slightly less efficient in terms of space, as it uses three sets instead of one. The overall space complexity would still be O(1) since the size of each set would be bounded by a constant.

✨

Key Insights

1Insight 1: We need to efficiently check for the presence of a digit within a row, column, and 3x3 sub-box.
2Insight 2: Using a set (or hash table) is an efficient way to track which numbers have already been seen in a row, column, or sub-box. Its fast O(1) lookup is crucial.
3Insight 3: Representing the row, column, and sub-box constraints as unique strings (or tuples) allows a single set to manage validation across all three rules simultaneously.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: An empty board (all cells are '.') is a valid Sudoku. The algorithm correctly handles this because it only processes cells that contain a digit.
Edge case 2: A board with only one filled cell is a valid Sudoku. The algorithm correctly handles this because it only needs to check for duplicates in rows, columns, and sub-boxes.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to check for '.' (empty cells) before processing a cell. This can lead to incorrect keys being generated or trying to convert '.' to an integer.

✗Common mistake 2: Incorrectly calculating the indices for the 3x3 sub-boxes. The integer division `i // 3` and `j // 3` is crucial for correctly identifying the sub-box a cell belongs to.

✗Common mistake 3: Forgetting to check for duplicates in *all* three dimensions: rows, columns, *and* boxes. Some implementations only consider one or two of these constraints.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Sudoku game validation: This algorithm can be used in Sudoku games or applications to ensure that the player's moves are valid and don't violate the Sudoku rules.

🏦Real-world scenario 2: Data validation: The core concept of checking for unique values within defined groups (rows, columns, subgrids) can be applied in various data validation scenarios, such as ensuring uniqueness of IDs within specific categories or regions.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 7, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Valid Sudoku"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?