Interview 150
Valid Sudoku
- Problem
- LC 36
- File
- interview150_LC36ValidSudoku.java
- Path
- pkg5leetcode/interview150/interview150_LC36ValidSudoku.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC36ValidSudoku.java
- Approach
- Hash sets for rows, columns, and 3x3 boxes.
- Complexity
- Time O(81), Space O(81)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Valid Sudoku | LC 365 * APPROACH: Hash sets for rows, columns, and 3x3 boxes.6 * COMPLEXITY: Time O(81), Space O(81)7 */8import java.util.*;9 10public class interview150_LC36ValidSudoku {11 static boolean isValidSudoku(char[][] board) {12 Set<String> seen = new HashSet<>();13 for (int r = 0; r < 9; r++) {14 for (int c = 0; c < 9; c++) {15 char ch = board[r][c];16 if (ch == '.') continue;17 String key = ch + "r" + r + "c" + c + "b" + r / 3 + c / 3;18 if (!seen.add(key)) return false;19 }20 }21 return true;22 }23 24 public static void main(String[] args) {25 char[][] valid = {26 {"5","3",".",".","7",".",".",".","."},27 {"6",".",".","1","9","5",".",".","."},28 {".","9","8",".",".",".",".","6","."},29 {"8",".",".",".","6",".",".",".","3"},30 {"4",".",".","8",".","3",".",".","1"},31 {"7",".",".",".","2",".",".",".","6"},32 {".","6",".",".",".",".","2","8","."},33 {".",".",".","4","1","9",".",".","5"},34 {".",".",".",".","8",".",".","7","9"}35 };36 check(isValidSudoku(valid), "case1");37 char[][] invalid = {38 {"8","3",".",".","7",".",".",".","."},39 {"6",".",".","1","9","5",".",".","."},40 {".","9","8",".",".",".",".","6","."},41 {"8",".",".",".","6",".",".",".","3"},42 {"4",".",".","8",".","3",".",".","1"},43 {"7",".",".",".","2",".",".",".","6"},44 {".","6",".",".",".",".","2","8","."},45 {".",".",".","4","1","9",".",".","5"},46 {".",".",".",".","8",".",".","7","9"}47 };48 check(!isValidSudoku(invalid), "case2");49 System.out.println("all tests passed");50 }51 52 static void check(boolean cond, String name) {53 if (!cond) throw new AssertionError("FAILED: " + name);54 System.out.println(" PASS " + name);55 }56}