LeetCode

LeetCode

  • Problems
  • GitHub

›Problems

Problems

  • Two Sum
  • Add Two Numbers
  • Longest Substring Without Repeating Characters
  • Median of Two Sorted Arrays
  • Longest Palindromic Substring
  • ZigZag Conversion
  • Reverse Integer
  • String to Integer (atoi)
  • Palindrome Number
  • Regular Expression Matching
  • Container With Most Water
  • Integer to Roman
  • Roman to Integer
  • Longest Common Prefix
  • 3Sum
  • 3Sum Closest
  • Letter Combinations of a Phone Number
  • 4Sum
  • Remove Nth Node From End of List
  • Valid Parentheses
  • Merge Two Sorted Lists
  • Generate Parentheses
  • Merge k Sorted Lists
  • Swap Nodes in Pairs
  • Reverse Nodes in k-Group
  • Remove Duplicates from Sorted Array
  • Remove Element
  • Implement strStr()
  • Divide Two Integers
  • Substring with Concatenation of All Words
  • Next Permutation
  • Longest Valid Parentheses
  • Search in Rotated Sorted Array
  • Find First and Last Position of Element in Sorted Array
  • Search Insert Position
  • Valid Sudoku
  • Sudoku Solver
  • Count and Say
  • Combination Sum
  • Combination Sum II
  • First Missing Positive
  • Trapping Rain Water
  • Multiply Strings
  • Wildcard Matching
  • Jump Game II
  • Permutations
  • Permutations II
  • Rotate Image
  • Group Anagrams
  • Pow(x, n)
  • Binary Tree Inorder Traversal
  • Triangle
  • Number of Islands
  • Random Pick Index
  • Coin Change 2
  • Maximum Length of Pair Chain
  • Repeated String Match
  • Minimum ASCII Delete Sum for Two Strings
  • Remove Comments
  • Split Linked List in Parts
  • Design HashSet
  • RLE Iterator
  • Number of Recent Calls
  • Rotting Oranges
  • Minimum Number of K Consecutive Bit Flips
  • Remove All Adjacent Duplicates In String
  • Unique Number of Occurrences
  • Count Servers that Communicate
  • Subtract the Product and Sum of Digits of an Integer
  • Find the Smallest Divisor Given a Threshold
  • Find N Unique Integers Sum up to Zero
  • Minimum Flips to Make a OR b Equal to c
  • Combine Two Tables
  • Second Highest Salary
  • Nth Highest Salary
  • Rank Scores
  • Consecutive Numbers
  • Employees Earning More Than Their Managers
  • Duplicate Emails
  • Customers Who Never Order
  • Department Highest Salary
  • Department Top Three Salaries
  • Delete Duplicate Emails
  • Rising Temperature
  • Trips and Users
  • Big Countries
  • Classes More Than 5 Students
  • Valid Phone Numbers
  • Tenth Line
  • Print in Order
  • Maximum Subarray

Valid Sudoku

Description

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["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:

Input:
[
  ["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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

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.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Solution(javascript)

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    let map = new Map();
    
    function getKeys(x, y) {
        const row = 'r' + y;
        const col = 'c' + x;
        const sqr = '' + Math.floor(x/3) + Math.floor(y/3);
        return [row, col, sqr];
    }
    
    for(let i = 0; i < 9; i++){
        for(let j = 0; j < 9; j++) {
            const s = board[i][j];
            if(s !== '.'){
                const arr = getKeys(i, j);
                for(let a of arr) {
                    if(!map.has(a)){
                        map.set(a, new Map());
                    }
                    
                    if(map.get(a).has(s)){
                        return false;
                    } else {
                        map.get(a).set(s, 1);
                    }
                }
            }
        }
    }
        
    return true;
};
← Search Insert PositionSudoku Solver →
  • Description
  • Solution(javascript)
Powered By LeetCode Site Generator