forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0036-valid-sudoku.js
87 lines (68 loc) · 2.83 KB
/
0036-valid-sudoku.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* Hash Map - Matrix
* Time O(ROWS * COLS) | Space O(ROWS * COLS)
* https://leetcode.com/problems/valid-sudoku/
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = (board) => {
const boards = 3;
const [ boxes, cols, rows ] = getBoards(boards);/* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
return searchGrid(board, boxes, cols, rows); /* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
};
var initBoard = (rows, cols) => new Array(rows).fill()
.map(() => new Array(cols).fill(false));
var getBoards = (boards) => {
const [ rows, cols ] = [ 9, 9 ];
return new Array(boards).fill()
.map(() => initBoard(rows, cols))
}
var searchGrid = (board, boxes, cols, rows) => {
const [ _rows, _cols ] = [ 9, 9 ];
for (let row = 0; row < _rows; row++) {/* Time O(ROWS)*/
for (let col = 0; col < _cols; col++) {/* Time O(COLS)*/
const char = board[row][col];
const index = (Math.floor(row / 3) * 3) + Math.floor(col / 3);
const isEmpty = char === '.';
if (isEmpty) continue;
const hasMoved = boxes[index][char] || cols[col][char] || rows[row][char];
if (hasMoved) return false;
rows[row][char] = true; /* Space O(ROWS * COLS)*/
cols[col][char] = true; /* Space O(ROWS * COLS)*/
boxes[index][char] = true; /* Space O(ROWS * COLS)*/
}
}
return true;
}
/**
* Array - Fixed Size
* Time O(ROWS * COLS) | Space O(CELLS)
* https://leetcode.com/problems/valid-sudoku/
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = (board) => {
const [ boards, cells ] = [ 3, 9];
const [ boxes, rows, cols ] = getBoards(boards, cells);/* Time O(ROWS * COLS) | Space O(CELLS) */
return searchGrid(board, boxes, rows, cols); /* Time O(ROWS * COLS) | Space O(CELLS) */
}
var getBoards = (boards, cells) => new Array(boards).fill()
.map(() => new Array(cells).fill(0));
var searchGrid = (board, boxes, rows, cols) => {
const [ _rows, _cols ] = [ 9, 9 ];
for (let row = 0; row < _rows; row++) {/* Time O(ROWS)*/
for (let col = 0; col < _cols; col++) {/* Time O(COLS)*/
const char = board[row][col];
const position = 1 << (char - 1);
const index = (Math.floor(row / 3) * 3) + Math.floor(col / 3);
const isEmpty = char === '.';
if (isEmpty) continue;
const hasMoved = (boxes[index] & position) || (cols[col] & position) || (rows[row] & position);
if (hasMoved) return false;
rows[row] |= position; /* Space O(CELLS)*/
cols[col] |= position; /* Space O(CELLS)*/
boxes[index] |= position; /* Space O(CELLS)*/
}
}
return true;
}