LC-102-binary-tree-level-order-traversal
LC-104-maximum-depth-of-binary-tree
LC-1046-last-stone-weight
LC-105-construct-binary-tree-from-preorder-and-inorder-traversal
LC-106-construct-binary-tree-from-inorder-and-postorder-traversal
LC-11-container-with-most-water
LC-110-balanced-binary-tree
LC-116-populating-next-right-pointers-in-each-node
LC-117-populating-next-right-pointers-in-each-node-ii
LC-119-pascals-triangle-ii
LC-121-best-time-to-buy-and-sell-stock
LC-128-longest-consecutive-sequence
LC-131-palindrome-partitioning
LC-1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold
LC-138-copy-list-with-random-pointer
LC-142-linked-list-cycle-ii
LC-144-binary-tree-preorder-traversal
LC-1448-count-good-nodes-in-binary-tree
LC-145-binary-tree-postorder-traversal
LC-1472-design-browser-history
LC-150-evaluate-reverse-polish-notation
LC-153-find-minimum-in-rotated-sorted-array
LC-167-two-sum-ii-input-array-is-sorted
LC-17-letter-combinations-of-a-phone-number
LC-173-binary-search-tree-iterator
LC-1899-merge-triplets-to-form-target-triplet
LC-19-remove-nth-node-from-end-of-list
LC-1929-concatenation-of-array
LC-199-binary-tree-right-side-view
LC-206-reverse-linked-list
LC-208-implement-trie-prefix-tree
LC-209-minimum-size-subarray-sum
LC-21-merge-two-sorted-lists
LC-211-design-add-and-search-words-data-structure
LC-2130-maximum-twin-sum-of-a-linked-list
LC-215-kth-largest-element-in-an-array
LC-217-contains-duplicate
LC-219-contains-duplicate-ii
LC-22-generate-parentheses
LC-225-implement-stack-using-queues
LC-226-invert-binary-tree
LC-230-kth-smallest-element-in-a-bst
LC-232-implement-queue-using-stacks
LC-235-lowest-common-ancestor-of-a-binary-search-tree
LC-236-lowest-common-ancestor-of-a-binary-tree
LC-238-product-of-array-except-self
LC-239-sliding-window-maximum
LC-24-swap-nodes-in-pairs
LC-240-search-a-2d-matrix-ii
LC-250-count-univalue-subtrees
LC-26-remove-duplicates-from-sorted-array
LC-271-encode-and-decode-strings
LC-287-find-the-duplicate-number
LC-297-serialize-and-deserialize-binary-tree
LC-3-longest-substring-without-repeating-characters
LC-303-range-sum-query-immutable
LC-304-range-sum-query-2d-immutable
LC-33-search-in-rotated-sorted-array
LC-347-top-k-frequent-elements
LC-374-guess-number-higher-or-lower
LC-42-trapping-rain-water
LC-424-longest-repeating-character-replacement
LC-435-non-overlapping-intervals
LC-543-diameter-of-binary-tree
LC-560-subarray-sum-equals-k
LC-567-permutation-in-string
LC-572-subtree-of-another-tree
LC-678-valid-parenthesis-string
LC-680-valid-palindrome-ii
LC-700-search-in-a-binary-search-tree
LC-701-search-in-a-binary-search-tree
LC-703-kth-largest-element-in-a-stream
LC-707-design-linked-list
LC-739-daily-temperatures
LC-76-minimum-window-substring
LC-779-k-th-symbol-in-grammar
LC-80-remove-duplicates-from-sorted-array-ii
LC-84-largest-rectangle-in-histogram
LC-875-koko-eating-bananas
LC-876-middle-of-the-linked-list
LC-918-maximum-sum-circular-subarray
LC-93-restore-ip-addresses
LC-94-binary-tree-inorder-traversal
LC-973-k-closest-points-to-origin
LC-978-longest-turbulent-subarray
LC-98-validate-binary-search-tree
LC-981-time-based-key-value-store
Failed to load latest commit information.
Latest commit Cannot retrieve latest commit at this time.Folders and files Name Name Last commit message
Last commit date
parent directory
View all files
PEDAC: Problem
input:
board
: 9 * 9 matrix with strings from set { 1-9, . }
output:
boolean that indicates if board
is a valid sudoku board or not
valid if
each row has string digits 1-9
with no duplicates
each col has string digits 1-9
with no duplciates
each 3 x 3
sub-boxes has string digits 1-9
with no duplicates
constraints
valid board may not be solvable
only filled cells need to be validated according to rules
PEDAC: Examples
Solution 1: hashset solution (NeetCode's modded)
O(9^2) T and O(9^2) S solution
initialise variables
rows
: hashmap that maps each row index to a string set containing all the digits in that row
cols
: hashmap that maps each row index to a string set containing all the digits in that col
box
: hashmap that contains maps each sub-box of the grid to a string set containing all the digits in that sub-box
key = tuple pair of (row_index / 3 as int, col_index / 3 as int)
iterate thru board
with nested for loops
if the current cell is a .
char, continue
if the current cell (which is a digit) is in any of the respective sets of the following hashmaps, return false:
rows[r]
cols[c]
box[(r // 3, c // 3)]
add the current cell to the above sets of the following hashmaps
if exited loop, return true
You can’t perform that action at this time.
Failed to load latest commit information.