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

leetcode 1151 - Minimum Swaps to Group All 1's Together

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

Example 1:

Input: [1,0,1,0,1]
Output: 1
Explanation:
There are 3 ways to group all 1’s together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.
Example 2:

Input: [0,0,0,1,0]
Output: 0
Explanation:
Since there is only one 1 in the array, no swaps needed.
Example 3:

Input: [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation:
One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Note:

1 <= data.length <= 10^5
0 <= data[i] <= 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
class Solution {
public:
int minSwaps(vector<int>& data) {
int ones = 0;
for (int i : data)
ones += (i == 1);

int zeros = 0;
int min_swap;

for (int i = 0; i < data.size(); i++) {
if (i < ones) {
if (data[i] == 0)
zeros++;
min_swap = zeros;
} else {
if (data[i] == 0)
zeros++;
if (data[i-ones] == 0)
zeros--;
min_swap = min(min_swap, zeros);
}
}

return min_swap;
}
};

leetcode 1166 - Design File System

https://leetcode.com/problems/design-file-system/

You are asked to design a file system which provides two functions:

createPath(path, value): Creates a new path and associates a value to it if possible and returns True. Returns False if the path already exists or its parent path doesn’t exist.
get(path): Returns the value associated with a path or returns -1 if the path doesn’t exist.
The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Implement the two functions.

Please refer to the examples for clarifications.

Example 1:

Input:
[“FileSystem”,”createPath”,”get”]
[[],[“/a”,1],[“/a”]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();

fileSystem.createPath(“/a”, 1); // return true
fileSystem.get(“/a”); // return 1
Example 2:

Input:
[“FileSystem”,”createPath”,”createPath”,”get”,”createPath”,”get”]
[[],[“/leet”,1],[“/leet/code”,2],[“/leet/code”],[“/c/d”,1],[“/c”]]
Output:
[null,true,true,2,false,-1]
Explanation:
FileSystem fileSystem = new FileSystem();

fileSystem.createPath(“/leet”, 1); // return true
fileSystem.createPath(“/leet/code”, 2); // return true
fileSystem.get(“/leet/code”); // return 2
fileSystem.createPath(“/c/d”, 1); // return false because the parent path “/c” doesn’t exist.
fileSystem.get(“/c”); // return -1 because this path doesn’t exist.

Constraints:

The number of calls to the two functions is less than or equal to 10^4 in total.
2 <= path.length <= 100
1 <= value <= 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
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
struct Node {
unordered_map<string, Node *> children;
int value;
};

class FileSystem {
public:
FileSystem() {
root = new Node;
}

bool createPath(string path, int value) {
if (path[0] != '/') return false;

size_t curr = 1;
size_t next;
Node *node = root;
string name;

do {
next = path.find("/", curr);
if (next == string::npos) {
name = path.substr(curr);
break;
} else {
name = path.substr(curr, next - curr);
curr = next + 1;

if (node->children.count(name) == 0)
return false;

node = node->children[name];
}

} while (next != string::npos);

if (node->children.count(name))
return false;

Node *new_node = new Node;
new_node->value = value;
node->children[name] = new_node;

return true;
}

int get(string path) {
if (path[0] != '/') return -1;

size_t curr = 1;
size_t next;
Node *node = root;
string name;

do {
next = path.find("/", curr);
if (next == string::npos) {
name = path.substr(curr);
} else {
name = path.substr(curr, next - curr);
curr = next + 1;
}

if (node->children.count(name) == 0)
return -1;
node = node->children[name];

} while (next != string::npos);

return node->value;
}

private:
Node *root;
};

/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem* obj = new FileSystem();
* bool param_1 = obj->createPath(path,value);
* int param_2 = obj->get(path);
*/

leetcode 1167 - Minimum Cost to Connect Sticks

https://leetcode.com/problems/minimum-cost-to-connect-sticks/

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3]
Output: 14
Example 2:

Input: sticks = [1,8,3,5]
Output: 30

Constraints:

1 <= sticks.length <= 10^4
1 <= sticks[i] <= 10^4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int connectSticks(vector<int>& sticks) {
priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
int cost = 0;

while (pq.size() > 1) {
int s1 = pq.top(); pq.pop();
int s2 = pq.top(); pq.pop();

cost += s1 + s2;
pq.push(s1 + s2);
}

return cost;
}
};

leetcode 1198 - Find Smallest Common Element in All Rows

https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
https://leetcode.com/problems/find-smallest-common-element-in-all-rows/solution/

Given a matrix mat where every row is sorted in increasing order, return the smallest common element in all rows.

If there is no common element, return -1.

Example 1:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

Constraints:

1 <= mat.length, mat[i].length <= 500
1 <= mat[i][j] <= 10^4
mat[i] is sorted in increasing order.

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

vector<int> idx(row, 0);

auto mycomp = [&](const pair<int,int> &p1, const pair<int,int> &p2) {
return mat[p1.first][p1.second] > mat[p2.first][p2.second];
};

typedef priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(mycomp)> pq_t;
pq_t pq(mycomp);

for (int r = 0; r < row; r++)
pq.push({r, 0});

while (!pq.empty()) {
if (check(mat, idx))
return mat[0][idx[0]];

auto p = pq.top(); pq.pop();
if (++p.second < col) {
pq.push(p);
idx[p.first] = p.second;
}
}

return -1;
}

bool check(vector<vector<int>>& mat, vector<int> &idx) {
int row = mat.size();

for (int r = 1; r < row; r++) {
int c = idx[r];

if (mat[r][c] != mat[0][idx[0]])
return false;
}

return true;
}
};

leetcode 1182 - Shortest Distance to Target Color

https://leetcode.com/problems/shortest-distance-to-target-color/

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation:
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).
Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.

Constraints:

1 <= colors.length <= 510^4
1 <= colors[i] <= 3
1 <= queries.length <= 5
10^4
queries[i].length == 2
0 <= queries[i][0] < colors.length
1 <= queries[i][1] <= 3

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
class Solution {
public:
vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
int n = colors.size();

vector<vector<int>> dist(n, vector<int>(4, -1));

vector<int> idx(4, -1);

for (int i = 0; i < n; i++) {
int c = colors[i];
idx[c] = i;

for (int j = 1; j <= 3; j++) {
if (idx[j] != -1)
dist[i][j] = i - idx[j];
}
}

fill(idx.begin(), idx.end(), -1);

for (int i = n - 1; i >= 0; i--) {
int c = colors[i];
idx[c] = i;

for (int j = 1; j <= 3; j++) {
if (idx[j] != -1) {
int d = idx[j] - i;
if (dist[i][j] == -1)
dist[i][j] = d;
else
dist[i][j] = min(dist[i][j], d);
}
}
}

n = queries.size();
vector<int> ret(n);

for (int i = 0; i < n; i++) {
int k = queries[i][0];
int p = queries[i][1];

ret[i] = dist[k][p];
}

return ret;
}
};

leetcode 1214 - Two Sum BSTs

https://leetcode.com/problems/two-sum-bsts/

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.
Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

Constraints:

Each tree has at most 5000 nodes.
-10^9 <= target, node.val <= 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
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class TreeNodeIterator {
public:
TreeNodeIterator(TreeNode *root) {
TreeNode *node = root;

while (node) {
small.push(node);
node = node->left;
}

node = root;

while (node) {
large.push(node);
node = node->right;
}
}

TreeNode *next() {
TreeNode *node = NULL;

if (!small.empty()) {
node = small.top(); small.pop();

TreeNode *n = node->right;
while (n) {
small.push(n);
n = n->left;
}
}

return node;
}

TreeNode *prev() {
TreeNode *node = NULL;

if (!large.empty()) {
node = large.top(); large.pop();

TreeNode *n = node->left;
while (n) {
large.push(n);
n = n->right;
}
}

return node;
}

private:
stack<TreeNode *> small, large;
};

class Solution {
public:
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
TreeNodeIterator it1(root1), it2(root2);

TreeNode *n1 = it1.next(), *n2 = it2.prev();

while (n1 && n2) {
int tmp = n1->val + n2->val;

if (tmp == target) return true;

if (tmp < target)
n1 = it1.next();
else
n2 = it2.prev();
}

return false;
}
};

leetcode 1215 - Stepping Numbers

A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.

Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.

Example 1:

Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]

Constraints:

0 <= low <= high <= 2 * 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
class Solution {
public:
vector<int> countSteppingNumbers(int low, int high) {
vector<int> res;

queue<int> q;
for (int i = 1; i <= 9; i++)
q.push(i);

if (low == 0) res.push_back(0);

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

int d = n % 10;
long next;
if (d > 0) {
next = (long)n * 10 + d - 1;
if (next <= high)
q.push(next);
}
if (d < 9) {
next = (long)n * 10 + d + 1;
if (next <= high)
q.push(next);
}

if (n >= low && n <= high)
res.push_back(n);
}

return res;
}
};

leetcode 1229 - Meeting Scheduler

https://leetcode.com/problems/meeting-scheduler/

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.

If there is no common time slot that satisfies the requirements, return an empty array.

The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]
Example 2:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Constraints:

1 <= slots1.length, slots2.length <= 10^4
slots1[i].length, slots2[i].length == 2
slots1[i][0] < slots1[i][1]
slots2[i][0] < slots2[i][1]
0 <= slots1[i][j], slots2[i][j] <= 10^9
1 <= duration <= 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
class Solution {
public:
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
sort(slots1.begin(), slots1.end());
sort(slots2.begin(), slots2.end());

int i = 0, j = 0;

while (i < slots1.size() && j < slots2.size()) {
auto d = overlap(slots1[i], slots2[j]);

if (d[0] >= 0 && d[1] - d[0] >= duration) {
d[1] = d[0] + duration;
return d;
} else {
if (slots1[i][0] < slots2[j][0])
i++;
else
j++;
}
}

return vector<int>{};
}

vector<int> overlap(vector<int> &s1, vector<int> &s2) {
vector<int> d = {max(s1[0], s2[0]), min(s1[1], s2[1])};

if (d[0] > d[1])
d[0] = -1;

return d;
}
};

leetcode 1230 - Toss Strange Coins

https://leetcode.com/problems/toss-strange-coins/

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:

Input: prob = [0.4], target = 1
Output: 0.40000
Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
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
33
34
35
36
37
38
39
40
41
42
43
44
/* 2D space */
class Solution {
public:
double probabilityOfHeads(vector<double>& prob, int target) {
int n = prob.size();
vector<vector<double>> dp(n, vector<double>(target+2));

dp[0][0] = 1 - prob[0];
dp[0][1] = prob[0];

for (int i = 1; i < n; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i-1][j] * (1 - prob[i]);
if (j > 0)
dp[i][j] += dp[i-1][j-1] * prob[i];
}
}

return dp[n-1][target];
}
};

/* 1D space */
class Solution {
public:
double probabilityOfHeads(vector<double>& prob, int target) {
int n = prob.size();
vector<double> dp(target+2);

dp[0] = 1 - prob[0];
dp[1] = prob[0];

for (int i = 1; i < n; i++) {
for (int j = 0; j <= target; j++) {
double tmp = dp[j] * (1 - prob[i]);
if (j > 0)
tmp += dp[j-1] * prob[i];
dp[j] = tmp;
}
}

return dp[target];
}
};