Huahua’s Tech Road

花花酱 LeetCode 36. Valid Sudoku

By zxi on August 20, 2019

Determine if a 9×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 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: HashTable

Use hashtable to store the numbers of each row, column and each 3×3 box. If there number appears more than once then it’s an invalid Sudoku.

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

C++

// Author: Huahua

class Solution {

public:

bool isValidSudoku(vector<vector<char> > &board) {

for (int i = 0; i < 9;i++) {

set<char> r, c;

for (int j = 0; j < 9; j++) {

if (board[i][j] != '.' && !r.insert(board[i][j]).second)

return false;

if (board[j][i] != '.' && !c.insert(board[j][i]).second)

return false;

}

for (int p = 0; p < 3; p++)

for (int q = 0; q < 3; q++) {

set<char> b;

for (int i = 0; i < 3; i++)

for (int j = 0; j < 3; j++) {

int x = p * 3 + i;

int y = q * 3 + j;

if (board[y][x] != '.' && !b.insert(board[y][x]).second)

return false;

}

return true;

}

};

Follow up:

https://zxi.mytechroad.com/blog/searching/leetcode-37-sudoku-solver/

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

By zxi on August 20, 2019

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution: Binary Search

Basically this problem asks you to implement lower_bound and upper_bound using binary search.

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> searchRange(vector<int>& nums, int target) {

return {firstPos(nums, target), lastPos(nums, target)};

}

private:

int firstPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] >= target) {

r = m;

} else {

l = m + 1;

}

if (l == nums.size() || nums[l] != target) return -1;

return l;

}

int lastPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] > target) {

r = m;

} else {

l = m + 1;

}

// l points to the first element this is greater than target.

--l;

if (l < 0 || nums[l] != target) return -1;

return l;

}

};

花花酱 LeetCode 1163. Last Substring in Lexicographical Order

By zxi on August 18, 2019

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: "leetcode"
Output: "tcode"

Note:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Key observation: The last substring must be a suffix of the original string, can’t a substring in the middle since we can always extend it.
e.g. leetcode -> tcode, can’t be “t”, “tc”, “tco”, “tcod”

Solution 1: Brute Force

Try all possible suffixes.
Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, 452 ms, 12.8 MB

class Solution {

public:

string lastSubstring(string_view s) {

string_view ans;

for (int i = 0; i < s.length(); ++i)

if (s.substr(i) > ans) ans = s.substr(i);

return string(ans);

}

};

Solution 2: Keep max and compare with candidates

Find the first largest letter as a starting point, whenever there is a same letter, keep it as a candidate and compare with the current best. If the later is larger, take over the current best.

e.g. “acbacbc”

“c” > “a”, the first “c” becomes the best.
“c” = “c”, the second “c” becomes a candidate
starting compare best and candidate.
“cb” = “cb”
“cba” < “cbc”, cand_i is the new best.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string lastSubstring(string s) {

int max_i = 0;

char max_c = 0;

int cand_i = 0;

int l = 0;

for (int i = 0; i < s.length(); ++i) {

if (s[i] > max_c) {

// Find a better starting point.

max_c = s[i];

max_i = i;

cand_i = -1;

l = 1;

} else if (cand_i != -1) {

// Has a candidate.

if (s[i] > s[max_i + l]) {

// The candidate is larger.

max_i = cand_i;

cand_i = -1;

} else if (s[i] == s[max_i + l]) {

// The candidate is the same as current best.

++l;

} else {

// The candidate is smaller, no longer needed.

cand_i = -1;

}

} else if (s[i] == max_c) {

// Find a new candidate, starting with length 1.

cand_i = i;

l = 1;

}

return s.substr(max_i);

}

};

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

By zxi on August 17, 2019

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

Solution: Hashtable

Use a hashtable to store each letter’s frequency of the string and compare that with each word.

Time complexity: O(n + sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua, 72 ms, 20 MB

class Solution {

public:

int countCharacters(vector<string>& words, string chars) {

vector<int> counts(26);

for (char c : chars) ++counts[c - 'a'];

int ans = 0;

for (const string& word : words) {

vector<int> cur(26);

bool valid = true;

for (char c: word)

if (++cur[c - 'a'] > counts[c - 'a']) {

valid = false;

break;

}

if (valid) ans += word.length();

}

return ans;

}

};

Python#

# Author: Huahua

class Solution:

def countCharacters(self, words: List[str], chars: str) -> int:

counts = collections.Counter(chars)

def isValid(word):

cur = collections.Counter(word)

for c in cur:

if c not in counts or cur[c] > counts[c]:

return False

return True

ans = 0

for word in words:

ans += len(word) if isValid(word) else 0

return ans

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

By zxi on August 17, 2019

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Example 1:

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:

The number of nodes in the given tree is between 1 and 10^4.
-10^5 <= node.val <= 10^5

Solution: HashTable

Use a hash table / array to store the level sum.

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua, 232 ms, 70.2 ms

class Solution {

public:

int maxLevelSum(TreeNode* root) {

vector<int> sums;

function<void(TreeNode*, int)> preorder = [&](TreeNode* n, int d) {

if (!n) return;

while (sums.size() <= d) sums.push_back(0);

sums[d] += n->val;

preorder(n->left, d + 1);

preorder(n->right, d + 1);

};

preorder(root, 1);

int max_sum = sums[1];

int ans = 1;

for (int i = 2; i < sums.size(); ++i)

if (sums[i] > max_sum) {

max_sum = sums[i];

ans = i;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 36. Valid Sudoku

Solution: HashTable

C++

Follow up:

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

Solution: Binary Search

C++

花花酱 LeetCode 1163. Last Substring in Lexicographical Order

Solution 1: Brute Force

C++

Solution 2: Keep max and compare with candidates

C++

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

Solution: Hashtable

C++

Python#

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

Solution: HashTable

C++