leetcode 655 - Print Binary Tree

https://leetcode.com/problems/print-binary-tree/

Print a binary tree in an m*n 2D string array following these rules:

The row number m should be equal to the height of the given binary tree.
The column number n should always be an odd number.
The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
Each unused space should contain an empty string “”.
Print the subtrees following the same rules.
Example 1:
Input:
1
/
2
Output:
[[“”, “1”, “”],
[“2”, “”, “”]]
Example 2:
Input:
1
/
2 3

4
Output:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
Example 3:
Input:
1
/
2 5
/
3
/
4
Output:

[[“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “”]
[“”, “”, “”, “2”, “”, “”, “”, “”, “”, “”, “”, “5”, “”, “”, “”]
[“”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
[“4”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]]
Note: The height of binary tree is in the range of [1, 10].

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
class Solution {
public:
vector<vector<string>> printTree(TreeNode* root) {
int depth = get_depth(root);
int width = (1 << depth) - 1;

vector<vector<string>> result(depth, vector<string>(width, ""));

print(root, result, 0, 0, width-1);

return result;
}

int get_depth(TreeNode *root) {
if (!root) return 0;

return max(get_depth(root->left), get_depth(root->right)) + 1;
}

void print(TreeNode *root, vector<vector<string>> &result, int d, int l, int r) {
if (!root) return;

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

result[d][m] = to_string(root->val);
print(root->left, result, d+1, l, m-1);
print(root->right, result, d+1, m+1, r);
}
};

leetcode 393 - UTF-8 Validation

https://leetcode.com/problems/utf-8-validation/

Given an integer array data representing the data, return whether it is a valid UTF-8 encoding.

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For a 1-byte character, the first bit is a 0, followed by its Unicode code.
For an n-bytes character, the first n bits are all one’s, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.
This is how the UTF-8 encoding would work:

Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
——————–+———————————————
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:

Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one’s and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that’s correct.
But the second continuation byte does not start with 10, so it is invalid.

Constraints:

1 <= data.length <= 2 * 10^4
0 <= data[i] <= 255

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
class Solution {
public:
bool validUtf8(vector<int>& data) {
int n = data.size();
int bytes_to_process = 0;

for (int i = 0; i < n; i++) {
if (bytes_to_process == 0) {
int bits = get_leading_bits(data[i]);
if (bits == 1 || bits > 4) return false;

if (bits)
bytes_to_process = bits - 1;
} else {
if (get_leading_bits(data[i]) != 1)
return false;
bytes_to_process--;
}
}

return bytes_to_process == 0;
}

int get_leading_bits(int num) {
int bit = 0;

for (int i = 7; i >= 0; i--) {
if ((num & (1 << i)) == 0)
break;
bit++;
}

return bit;
}
};

leetcode 399 - Evaluate Division

https://leetcode.com/problems/evaluate-division/

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
Example 2:

Input: equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:

Input: equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits.

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
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_map<string, vector<pair<string, double>>> graph;

int n = equations.size();
for (int i = 0; i < n; i++) {
string &a = equations[i][0];
string &b = equations[i][1];

graph[a].push_back({b, 1.0/values[i]});
graph[b].push_back({a, values[i]});
}

vector<double> result;

for (auto &query : queries) {
if (graph.count(query[0]) == 0 || graph.count(query[1]) == 0)
result.push_back(-1.0);
else
result.push_back(bfs(graph, query[1], query[0]));
}

return result;
}

double bfs(unordered_map<string, vector<pair<string, double>>> &graph, string &a, string &b) {
queue<pair<string, double>> q;
unordered_set<string> seen;

q.push({a, 1.0});
seen.insert(a);

while (!q.empty()) {
int n = q.size();

for (int i = 0; i < n; i++) {
auto p = q.front(); q.pop();
if (p.first == b)
return p.second;

auto &edges = graph[p.first];
for (auto &e : edges) {
if (seen.count(e.first)) continue;

q.push({e.first, p.second * e.second});
seen.insert(e.first);
}
}
}

return -1.0;
}
};

leetcode 427 - Construct Quad Tree

https://leetcode.com/problems/construct-quad-tree/

Given a n * n matrix grid of 0’s and 1’s only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s.
isLeaf: True if the node is leaf node on the tree or False if the node has the four children.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e all 1’s or all 0’s) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

Example 3:

Input: grid = [[1,1],[1,1]]
Output: [[1,1]]
Example 4:

Input: grid = [[0]]
Output: [[1,0]]
Example 5:

Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]

Constraints:

n == grid.length == grid[i].length
n == 2^x where 0 <= x <= 6
Accepted

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
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;

Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}

Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}

Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
*/

class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
return recursive(grid, 0, 0, grid.size()-1, grid[0].size()-1);
}

Node *recursive(vector<vector<int>> &grid, int x1, int y1, int x2, int y2) {
if (all_same(grid, x1, y1, x2, y2))
return new Node(grid[x1][y1], true);

Node *parent = new Node(1, false);
parent->topLeft = recursive(grid, x1, y1, (x1+x2)/2, (y1+y2)/2);
parent->topRight = recursive(grid, x1, (y1+y2)/2+1, (x1+x2)/2, y2);
parent->bottomLeft = recursive(grid, (x1+x2)/2+1, y1, x2, (y1+y2)/2);
parent->bottomRight = recursive(grid, (x1+x2)/2+1, (y1+y2)/2+1, x2, y2);
return parent;
}

bool all_same(vector<vector<int>> &grid, int x1, int y1, int x2, int y2) {
int rows = x2 - x1 + 1;
int cols = y2 - y1 + 1;

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[x1+r][y1+c] != grid[x1][y1])
return false;
}
}

return true;
}
};

leetcode 966 - Vowel Spellchecker

https://leetcode.com/problems/vowel-spellchecker/

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
Example: wordlist = [“yellow”], query = “YellOw”: correct = “yellow”
Example: wordlist = [“Yellow”], query = “yellow”: correct = “Yellow”
Example: wordlist = [“yellow”], query = “yellow”: correct = “yellow”
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
Example: wordlist = [“YellOw”], query = “yollow”: correct = “YellOw”
Example: wordlist = [“YellOw”], query = “yeellow”: correct = “” (no match)
Example: wordlist = [“YellOw”], query = “yllw”: correct = “” (no match)
In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.
Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = [“KiTe”,”kite”,”hare”,”Hare”], queries = [“kite”,”Kite”,”KiTe”,”Hare”,”HARE”,”Hear”,”hear”,”keti”,”keet”,”keto”]
Output: [“kite”,”KiTe”,”KiTe”,”Hare”,”hare”,””,””,”KiTe”,””,”KiTe”]
Example 2:

Input: wordlist = [“yellow”], queries = [“YellOw”]
Output: [“yellow”]

Constraints:

1 <= wordlist.length, queries.length <= 5000
1 <= wordlist[i].length, queries[i].length <= 7
wordlist[i] and queries[i] consist only of only English letters.

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
class Solution {
public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
unordered_set<string> words;
unordered_map<string, vector<int>> words_lowercase;
unordered_map<string, vector<int>> words_vowel;

int n = wordlist.size();
for (int i = 0; i < n; i++) {
words.insert(wordlist[i]);
words_lowercase[get_key_lowercase(wordlist[i])].push_back(i);
words_vowel[get_key_vowel(wordlist[i])].push_back(i);
}

vector<string> result;

for (auto &query : queries) {
if (words.count(query)) {
result.push_back(query);
continue;
}

string key = get_key_lowercase(query);
if (words_lowercase.count(key)) {
int idx = words_lowercase[key].front();
result.push_back(wordlist[idx]);
continue;
}

key = get_key_vowel(query);
if (words_vowel.count(key)) {
int idx = words_vowel[key].front();
result.push_back(wordlist[idx]);
continue;
}

result.push_back("");
}

return result;
}

string get_key_lowercase(string word) {
for (int i = 0; i < word.size(); i++) {
if (word[i] >= 'A' && word[i] <= 'Z')
word[i] = word[i] - 'A' + 'a';
}

return word;
}

string get_key_vowel(string word) {
word = get_key_lowercase(word);
string vowel = "aeiou";
for (int i = 0; i < word.size(); i++) {
for (char v : vowel) {
if (word[i] == v) {
word[i] = '*';
break;
}
}
}

return word;
}
};

leetcode 37 - Sudoku Solver

https://leetcode.com/problems/sudoku-solver/
https://leetcode.com/problems/sudoku-solver/discuss/15853/Simple-and-Clean-Solution-C%2B%2B

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The ‘.’ character indicates empty cells.

Example 1:

Input: board = [[“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: [[“5”,”3”,”4”,”6”,”7”,”8”,”9”,”1”,”2”],[“6”,”7”,”2”,”1”,”9”,”5”,”3”,”4”,”8”],[“1”,”9”,”8”,”3”,”4”,”2”,”5”,”6”,”7”],[“8”,”5”,”9”,”7”,”6”,”1”,”4”,”2”,”3”],[“4”,”2”,”6”,”8”,”5”,”3”,”7”,”9”,”1”],[“7”,”1”,”3”,”9”,”2”,”4”,”8”,”5”,”6”],[“9”,”6”,”1”,”5”,”3”,”7”,”2”,”8”,”4”],[“2”,”8”,”7”,”4”,”1”,”9”,”6”,”3”,”5”],[“3”,”4”,”5”,”2”,”8”,”6”,”1”,”7”,”9”]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit or ‘.’.
It is guaranteed that the input board has only one solution.

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
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
dfs(board, 0, 0);
}

bool dfs(vector<vector<char>>& board, int r, int c) {
if (r == 9) return true;
if (c == 9) return dfs(board, r+1, 0);

if (board[r][c] != '.')
return dfs(board, r, c+1);

for (int v = 1; v <= 9; v++) {
if (isValidSudoku(board, r, c, v+'0')) {
board[r][c] = v + '0';
if (dfs(board, r, c+1))
return true;
}
}

board[r][c] = '.';
return false;
}

bool isValidSudoku(vector<vector<char>>& board, int r, int c, char v) {
for (int col = 0; col < 9; col++)
if (board[r][col] == v)
return false;

for (int row = 0; row < 9; row++)
if (board[row][c] == v)
return false;

r = r / 3 * 3;
c = c / 3 * 3;

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[r+i][c+j] == v)
return false;

return true;
}
};

leetcode 332 - Reconstruct Itinerary

https://leetcode.com/problems/reconstruct-itinerary/

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]
Example 2:

Input: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
Output: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
Explanation: Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] but it is larger in lexical order.

Constraints:

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi

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
class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
int n = tickets.size();
unordered_map<string, vector<pair<string, bool>>> graph;

for (auto &ticket : tickets) {
auto &from = ticket[0];
auto &to = ticket[1];

graph[from].push_back({to, false});
}

for (auto &edges : graph)
sort(edges.second.begin(), edges.second.end());

vector<string> result;
dfs(graph, "JFK", result, n);

return result;
}

bool dfs(unordered_map<string, vector<pair<string, bool>>> &graph, string city, vector<string> &path, int n) {
path.push_back(city);
if (path.size() == n + 1)
return true;

auto &edges = graph[city];
bool ret = false;

for (int k = 0; k < edges.size(); k++) {
if (edges[k].second == false) {
edges[k].second = true;
ret = dfs(graph, edges[k].first, path, n);
if (ret) {
break;
}
edges[k].second = false;
}
}

if (!ret)
path.pop_back();

return ret;
}
};

leetcode 1254 - Number of Closed Islands

https://leetcode.com/problems/number-of-closed-islands/

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
Example 3:

Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2

Constraints:

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

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
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int rows = grid.size(), cols = grid[0].size();

int ans = 0;

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 0) {
int result = 1;
dfs(grid, r, c, result);
ans += result;
}
}
}

return ans;
}

void dfs(vector<vector<int>>& grid, int r, int c, int &result) {
int rows = grid.size(), cols = grid[0].size();

int dirs[] = {0, -1, 0, 1, 0};

for (int i = 0; i < 4; i++) {
int x = r + dirs[i];
int y = c + dirs[i+1];

if (x < 0 || x >= rows || y < 0 || y >= cols) {
result = 0;
continue;
}

if (grid[x][y] == 0) {
grid[x][y] = 1;
dfs(grid, x, y, result);
}
}
}
};

leetcode 4 - Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

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
//O(log(min(len1, len2)))
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() < nums2.size())
return binary_search(nums1, nums2);
else
return binary_search(nums2, nums1);
}

double binary_search(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int l = 0, r = n;

int total = n + nums2.size();

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

int x_min = (m == 0) ? INT_MIN : nums1[m-1];
int x_max = (m == n) ? INT_MAX : nums1[m];

int k = (total + 1) / 2 - m; //left partion size for nums2

int y_min = (k == 0) ? INT_MIN : nums2[k-1];
int y_max = (k == nums2.size()) ? INT_MAX : nums2[k];

if (x_min <= y_max && y_min <= x_max) {
if (total % 2)
return max(x_min, y_min);
else
return (max(x_min, y_min) + min(x_max, y_max)) / 2.0;
} else if (x_min > y_max) {
r = m - 1;
} else {
l = m + 1;
}
}

//should not get here
return 0;
}
};

leetcode 359 - Logger Rate Limiter

https://leetcode.com/problems/logger-rate-limiter/

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

Logger() Initializes the logger object.
bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

Input
[“Logger”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”]
[[], [1, “foo”], [2, “bar”], [3, “foo”], [8, “bar”], [10, “foo”], [11, “foo”]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, “foo”); // return true, next allowed timestamp for “foo” is 1 + 10 = 11
logger.shouldPrintMessage(2, “bar”); // return true, next allowed timestamp for “bar” is 2 + 10 = 12
logger.shouldPrintMessage(3, “foo”); // 3 < 11, return false
logger.shouldPrintMessage(8, “bar”); // 8 < 12, return false
logger.shouldPrintMessage(10, “foo”); // 10 < 11, return false
logger.shouldPrintMessage(11, “foo”); // 11 >= 11, return true, next allowed timestamp for “foo” is
// 11 + 10 = 21

Constraints:

0 <= timestamp <= 10^9
Every timestamp will be passed in non-decreasing order (chronological order).
1 <= message.length <= 30
At most 104 calls will be made to shouldPrintMessage.

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
class Logger {
public:
/** Initialize your data structure here. */
Logger() {

}

/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
If this method returns false, the message will not be printed.
The timestamp is in seconds granularity. */
bool shouldPrintMessage(int timestamp, string message) {
while (!dq.empty()) {
if (dq.front().first + 10 <= timestamp) {
seen.erase(dq.front().second);
dq.pop_front();
} else {
break;
}
}

if (seen.count(message))
return false;
else {
seen.insert(message);
dq.push_back({timestamp, message});
return true;
}
}

private:
deque<pair<int,string>> dq;
unordered_set<string> seen;
};

/**
* Your Logger object will be instantiated and called as such:
* Logger* obj = new Logger();
* bool param_1 = obj->shouldPrintMessage(timestamp,message);
*/

//Token bucket
class Logger {
public:
/** Initialize your data structure here. */
Logger() {

}

/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
If this method returns false, the message will not be printed.
The timestamp is in seconds granularity. */
bool shouldPrintMessage(int timestamp, string message) {
if (token_bucket.count(message) == 0) {
token_bucket[message] = {timestamp, 1};
}

auto &t = token_bucket[message];
if (t.first + 10 <= timestamp) {
t.first = timestamp;
t.second = 1;
}

if (t.second > 0) {
t.second--;
return true;
} else {
return false;
}
}

private:
unordered_map<string, pair<int, int>> token_bucket; //bucket_id ==> {timestamp, token}
};