leetcode 1604 - Alert Using Same Key-Card Three or More Times in a One Hour Period

https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/

LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format “HH:MM”, such as “23:51” and “09:49”.

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that “10:00” - “11:00” is considered to be within a one-hour period, while “22:51” - “23:52” is not considered to be within a one-hour period.

Example 1:

Input: keyName = [“daniel”,”daniel”,”daniel”,”luis”,”luis”,”luis”,”luis”], keyTime = [“10:00”,”10:40”,”11:00”,”09:00”,”11:00”,”13:00”,”15:00”]
Output: [“daniel”]
Explanation: “daniel” used the keycard 3 times in a one-hour period (“10:00”,”10:40”, “11:00”).
Example 2:

Input: keyName = [“alice”,”alice”,”alice”,”bob”,”bob”,”bob”,”bob”], keyTime = [“12:01”,”12:00”,”18:00”,”21:00”,”21:20”,”21:30”,”23:00”]
Output: [“bob”]
Explanation: “bob” used the keycard 3 times in a one-hour period (“21:00”,”21:20”, “21:30”).
Example 3:

Input: keyName = [“john”,”john”,”john”], keyTime = [“23:58”,”23:59”,”00:01”]
Output: []
Example 4:

Input: keyName = [“leslie”,”leslie”,”leslie”,”clare”,”clare”,”clare”,”clare”], keyTime = [“13:00”,”13:20”,”14:00”,”18:00”,”18:51”,”19:30”,”19:49”]
Output: [“clare”,”leslie”]

Constraints:

1 <= keyName.length, keyTime.length <= 105
keyName.length == keyTime.length
keyTime are in the format “HH:MM”.
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase 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
class Solution {
public:
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
unordered_map<string, vector<int>> maps;

int size = keyName.size();

for (int i = 0; i < size; i++) {
int time = stoi(keyTime[i].substr(0, 2)) * 60 + stoi(keyTime[i].substr(3));
maps[keyName[i]].push_back(time);
}

vector<string> result;

for (auto v : maps) {
sort(v.second.begin(), v.second.end());

int i = 0;
for (int j = 1; j < v.second.size(); j++) {
while (v.second[j] - v.second[i] > 60) {
i++;
}

if (j - i + 1 >= 3) {
result.push_back(v.first);
break;
}
}
}

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

return result;
}
};

leetcode 1608 - Special Array With X Elements Greater Than or Equal X

https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.
Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.
Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.
Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int specialArray(vector<int>& nums) {
int size = nums.size();
vector<int> count(1001, 0);

for (int i : nums)
count[i]++;

int remain = size;
for (int i = 0; i <= 1000; i++) {
if (i == remain)
return i;
remain -= count[i];
}

return -1;
}
};

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 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;
}
};