leetcode 1612 - Check If Two Expression Trees are Equivalent

https://leetcode.com/problems/check-if-two-expression-trees-are-equivalent/

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (variables), and internal nodes (nodes with two children) correspond to the operators. In this problem, we only consider the ‘+’ operator (i.e. addition).

You are given the roots of two binary expression trees, root1 and root2. Return true if the two binary expression trees are equivalent. Otherwise, return false.

Two binary expression trees are equivalent if they evaluate to the same value regardless of what the variables are set to.

Follow up: What will you change in your solution if the tree also supports the ‘-‘ operator (i.e. subtraction)?

Example 1:

Input: root1 = [x], root2 = [x]
Output: true
Example 2:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Output: true
Explaination: a + (b + c) == (b + c) + a
Example 3:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Output: false
Explaination: a + (b + c) != (b + d) + a

Constraints:

The number of nodes in both trees are equal, odd and, in the range [1, 4999].
Node.val is ‘+’ or a lower-case English letter.
It’s guaranteed that the tree given is a valid binary expression tree.

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
/**
* Definition for a binary tree node.
* struct Node {
* char val;
* Node *left;
* Node *right;
* Node() : val(' '), left(nullptr), right(nullptr) {}
* Node(char x) : val(x), left(nullptr), right(nullptr) {}
* Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool checkEquivalence(Node* root1, Node* root2) {
vector<int> count(256, 0);

dfs(root1, count, 1);
dfs(root2, count, -1);

for (int n : count) {
if (n != 0)
return false;
}

return true;
}

void dfs(Node *root, vector<int> &count, int d) {
if (!root) return;

if (root->val != '+')
count[(int)root->val] += d;

dfs(root->left, count, d);
dfs(root->right, count, d);
}
};

leetcode 1609 - Even Odd Tree

https://leetcode.com/problems/even-odd-tree/

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).
Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.
Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.
Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.
Example 4:

Input: root = [1]
Output: true
Example 5:

Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
Output: true

Constraints:

The number of nodes in the tree is in the range [1, 105].
1 <= Node.val <= 106

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
queue<TreeNode *> q;

q.push(root);
int level = 0;

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

int prev;
for (int i = 0; i < n; i++) {
TreeNode *node = q.front(); q.pop();
int cur = node->val;

if (level % 2 == cur % 2)
return false;

if (i == 0)
prev = cur;
else {
if (level % 2 == 0) {
if (cur <= prev)
return false;
} else {
if (cur >= prev)
return false;
}
}

prev = cur;
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}

level++;
}

return true;
}
};

leetcode 1564 - Put Boxes Into the Warehouse I

https://leetcode.com/problems/put-boxes-into-the-warehouse-i/

You are given two arrays of positive integers, boxes and warehouse, representing the heights of some boxes of unit width and the heights of n rooms in a warehouse respectively. The warehouse’s rooms are labelled from 0 to n - 1 from left to right where warehouse[i] (0-indexed) is the height of the ith room.

Boxes are put into the warehouse by the following rules:

Boxes cannot be stacked.
You can rearrange the insertion order of the boxes.
Boxes can only be pushed into the warehouse from left to right only.
If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.
Return the maximum number of boxes you can put into the warehouse.

Example 1:

Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
Output: 3
Explanation:

We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
There is no way we can fit all 4 boxes in the warehouse.
Example 2:

Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
Output: 3
Explanation:

Notice that it’s not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3.
Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit.
We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead.
Swapping the orange and green boxes is also valid, or swapping one of them with the red box.
Example 3:

Input: boxes = [1,2,3], warehouse = [1,2,3,4]
Output: 1
Explanation: Since the first room in the warehouse is of height 1, we can only put boxes of height 1.
Example 4:

Input: boxes = [4,5,6], warehouse = [3,3,3,3,3]
Output: 0

Constraints:

n == warehouse.length
1 <= boxes.length, warehouse.length <= 10^5
1 <= boxes[i], warehouse[i] <= 10^9

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:
int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
stack<int> stk;

for (int h : warehouse) {
if (stk.empty())
stk.push(h);
else
stk.push(min(stk.top(), h));
}

sort(boxes.begin(), boxes.end());

int n = 0;
int i = 0;

while (i < boxes.size() && !stk.empty()) {
int h = stk.top(); stk.pop();

if (boxes[i] <= h) {
n++;
i++;
}
}

return n;
}
};

leetcode 1563 - Stone Game V

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice’s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice’s is initially zero.

Return the maximum score that Alice can obtain.

Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice’s score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice’s score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice’s score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.
Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28
Example 3:

Input: stoneValue = [4]
Output: 0

Constraints:

1 <= stoneValue.length <= 500
1 <= stoneValue[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
44
class Solution {
public:
vector<vector<int>> memo;

int stoneGameV(vector<int>& stoneValue) {
int size = stoneValue.size();
memo.resize(size, vector<int>(size, -1));

return stoneGameV(stoneValue, 0, size - 1);
}

int stoneGameV(vector<int>& stoneValue, int i, int j) {
if (memo[i][j] != -1) return memo[i][j];

if (i == j) {
memo[i][j] = 0;
return 0;
}

int maxScore = INT_MIN;

for (int k = i + 1; k <= j; k++) {
int sum1 = 0, sum2 = 0;

for (int m = i; m <= k - 1; m++)
sum1 += stoneValue[m];
for (int m = k; m <= j; m++)
sum2 += stoneValue[m];

int score;
if (sum1 > sum2)
score = sum2 + stoneGameV(stoneValue, k, j);
else if (sum1 < sum2)
score = sum1 + stoneGameV(stoneValue, i, k-1);
else
score = sum1 + max(stoneGameV(stoneValue, i, k-1), stoneGameV(stoneValue, k, j));

maxScore = max(maxScore, score);
}

memo[i][j] = maxScore;
return maxScore;
}
};

leetcode 1060 - Missing Element in Sorted Array

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Example 1:

Input: A = [4,7,9,10], K = 1
Output: 5
Explanation:
The first missing number is 5.
Example 2:

Input: A = [4,7,9,10], K = 3
Output: 8
Explanation:
The missing numbers are [5,6,8,…], hence the third missing number is 8.
Example 3:

Input: A = [1,2,4], K = 3
Output: 6
Explanation:
The missing numbers are [3,5,6,7,…], hence the third missing number is 6.

Note:

1 <= A.length <= 50000
1 <= A[i] <= 1e7
1 <= K <= 1e8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int i = 0, j = nums.size() - 1;

while (i <= j) {
int m = i + (j - i) / 2;

if (missing(nums, m) < k)
i = m + 1;
else
j = m - 1;
}

return nums[j] + (k - missing(nums, j));
}

int missing(vector<int> &nums, int i) {
return nums[i] - nums[0] - i;
}
};

leetcode 1102 - Path With Maximum Minimum Value

https://leetcode.com/problems/path-with-maximum-minimum-value

Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].

The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.

A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Example 1:

Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation:
The path with the maximum score is highlighted in yellow.
Example 2:

Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Example 3:

Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3

Note:

1 <= R, C <= 100
0 <= A[i][j] <= 10^9

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:
int maximumMinimumPath(vector<vector<int>>& A) {
int row = A.size(), col = A[0].size();

priority_queue<tuple<int,int,int>> pq;

int score = A[0][0];
pq.emplace(A[0][0], 0, 0);
A[0][0] = -1;

vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};

while (!pq.empty()) {
auto p = pq.top(); pq.pop();
score = min(get<0>(p), score);

if (get<1>(p) == row - 1 && get<2>(p) == col - 1)
break;

for (auto &dir : dirs) {
int x = get<1>(p) + dir[0];
int y = get<2>(p) + dir[1];

if (x < 0 || x >= row || y < 0 || y >= col || A[x][y] == -1)
continue;

pq.emplace(A[x][y], x, y);
A[x][y] = -1;
}
}

return score;
}
};

leetcode 1062 - Longest Repeating Substring

https://leetcode.com/problems/longest-repeating-substring/
https://leetcode.com/problems/longest-repeating-substring/solution/

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

Example 1:

Input: “abcd”
Output: 0
Explanation: There is no repeating substring.
Example 2:

Input: “abbaba”
Output: 2
Explanation: The longest repeating substrings are “ab” and “ba”, each of which occurs twice.
Example 3:

Input: “aabcaabdaab”
Output: 3
Explanation: The longest repeating substring is “aab”, which occurs 3 times.
Example 4:

Input: “aaaaa”
Output: 4
Explanation: The longest repeating substring is “aaaa”, which occurs twice.

Note:

The string S consists of only lowercase English letters from ‘a’ - ‘z’.
1 <= S.length <= 1500

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
struct Node {
vector<Node *> children;
int n;

Node() {
children.resize(26, NULL);
n = 0;
}
};

/* Memory limit exceed */
class Solution00 {
public:
int longestRepeatingSubstring(string S) {
Node *root = new Node;

buildTrie(root, S);

int len = INT_MIN;

for (int i = 0; i < (int)S.size(); i++) {
len = max(len, find(root, S, i));
remove(root, S, i+1);
}

return len;
}

void buildTrie(Node *root, string &s) {
for (int i = 1; i < (int)s.size(); i++)
insert(root, s, i);
}

void insert(Node *node, string &s, int i) {
while (i < (int)s.size()) {
int c = s[i] - 'a';

if (node->children[c] == NULL)
node->children[c] = new Node;

node->children[c]->n++;
node = node->children[c];

i++;
}
}

void remove(Node *node, string &s, int i) {
while (i < (int)s.size()) {
int c = s[i] - 'a';
Node *child = node->children[c];
if (--child->n == 0)
break;
node = child;
i++;
}
}

int find(Node *node, string &s, int i) {
int len = 0;

while (i < (int)s.size()) {
int c = s[i] - 'a';
Node *child = node->children[c];
if (child == NULL || child->n == 0)
break;
node = child;
i++;
len++;
}

return len;
}
};

class Solution {
public:
int longestRepeatingSubstring(string S) {
int low = 0, high = S.size();

while (low <= high) {
int mid = low + (high - low) / 2;

if (search(S, mid))
low = mid + 1;
else
high = mid - 1;
}

return low - 1;
}

bool search(string &s, int len) {
unordered_set<string> seen;

for (int i = 0; i <= s.size() - len; i++) {
string str = s.substr(i, len);
if (seen.count(str))
return true;
seen.insert(str);
}

return false;
}
};

leetcode 1100 - Find K-Length Substrings With No Repeated Characters

https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/

Given a string S, return the number of substrings of length K with no repeated characters.

Example 1:

Input: S = “havefunonleetcode”, K = 5
Output: 6
Explanation:
There are 6 substrings they are : ‘havef’,’avefu’,’vefun’,’efuno’,’etcod’,’tcode’.
Example 2:

Input: S = “home”, K = 5
Output: 0
Explanation:
Notice K can be larger than the length of S. In this case is not possible to find any substring.

Note:

1 <= S.length <= 10^4
All characters of S are lowercase English letters.
1 <= K <= 10^4

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
class Solution {
public:
int numKLenSubstrNoRepeats(string S, int K) {
int n = S.size();

int i = 0, j = 0;
int total = 0;

vector<int> count(256, 0);

while (j < n) {
int c = S[j];
count[c]++;

while (count[c] > 1 && i < j) {
count[S[i]]--;
i++;
}

if (j - i + 1 == K) {
count[S[i]]--;
i++;
total++;
}

j++;
}

return total;
}
};

leetcode 1101 - The Earliest Moment When Everyone Become Friends

https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

In a social group, there are N people, with unique integer ids from 0 to N-1.

We have a list of logs, where each logs[i] = [timestamp, id_A, id_B] contains a non-negative integer timestamp, and the ids of two different people.

Each log represents the time in which two different people became friends. Friendship is symmetric: if A is friends with B, then B is friends with A.

Let’s say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B.

Return the earliest time for which every person became acquainted with every other person. Return -1 if there is no such earliest time.

Example 1:

Input: logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
Output: 20190301
Explanation:
The first event occurs at timestamp = 20190101 and after 0 and 1 become friends we have the following friendship groups [0,1], [2], [3], [4], [5].
The second event occurs at timestamp = 20190104 and after 3 and 4 become friends we have the following friendship groups [0,1], [2], [3,4], [5].
The third event occurs at timestamp = 20190107 and after 2 and 3 become friends we have the following friendship groups [0,1], [2,3,4], [5].
The fourth event occurs at timestamp = 20190211 and after 1 and 5 become friends we have the following friendship groups [0,1,5], [2,3,4].
The fifth event occurs at timestamp = 20190224 and as 2 and 4 are already friend anything happens.
The sixth event occurs at timestamp = 20190301 and after 0 and 3 become friends we have that all become friends.

Note:

2 <= N <= 100
1 <= logs.length <= 10^4
0 <= logs[i][0] <= 10^9
0 <= logs[i][1], logs[i][2] <= N - 1
It’s guaranteed that all timestamps in logs[i][0] are different.
logs are not necessarily ordered by some criteria.
logs[i][1] != logs[i][2]

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
class UnionFind {
public:
UnionFind(int N) {
for (int i = 0; i < N; i++) {
parent.push_back(i);
size.push_back(1);
}
}

int Find(int i) {
if (parent[i] != i)
parent[i] = Find(parent[i]);
return parent[i];
}

void Union(int i, int j) {
int p1 = Find(i);
int p2 = Find(j);

parent[p1] = p2;
size[p2] += size[p1];
}

int Size(int i) {
return size[i];
}

private:
vector<int> parent;
vector<int> size;
};

class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int N) {
sort(logs.begin(), logs.end());

UnionFind uf(N);

for (auto &p : logs) {
int g1 = uf.Find(p[1]);
int g2 = uf.Find(p[2]);

if (g1 != g2) {
int s1 = uf.Size(g1);
int s2 = uf.Size(g2);

if (s1 + s2 == N) return p[0];

uf.Union(p[1], p[2]);
}
}

return -1;
}
};

leetcode 1120 - Maximum Average Subtree

Given the root of a binary tree, find the maximum average value of any subtree of that tree.

(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)

Example 1:

Input: [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

Note:

The number of nodes in the tree is between 1 and 5000.
Each node will have a value between 0 and 100000.
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
double max_avg = 0.0;

double maximumAverageSubtree(TreeNode* root) {
dfs(root);

return max_avg;
}

pair<int,int> dfs(TreeNode *root) {
if (!root) return {0, 0};

auto left = dfs(root->left);
auto right = dfs(root->right);

pair<int,int> p = {left.first + right.first + root->val, left.second + right.second + 1};

max_avg = max(max_avg, (p.first * 1.0) / p.second);

return p;
}
};