leetcode 1457 - Pseudo-Palindromic Paths in a Binary Tree

https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 3:

Input: root = [9]
Output: 1

Constraints:

The given binary tree will have between 1 and 10^5 nodes.
Node values are digits from 1 to 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
/**
* 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:
int total;

int pseudoPalindromicPaths (TreeNode* root) {
total = 0;

vector<int> path;

dfs(root, path);

return total;
}

void dfs(TreeNode *root, vector<int> &path) {
if (!root) {
return;
}

path.push_back(root->val);
if (!root->left && !root->right && check(path))
total++;

dfs(root->left, path);
dfs(root->right, path);

path.pop_back();
}

bool check(vector<int> &path) {
vector<int> count(10, 0);

int odd = 0;
for (int n : path) {
if (++count[n] % 2)
odd++;
else
odd--;
}

return odd <= 1;
}
};

leetcode 1296 - Divide Array in Sets of K Consecutive Numbers

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possible otherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
Example 3:

Input: nums = [3,3,2,2,1,1], k = 3
Output: true
Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length
Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
map<int,int> maps;

for (int num : nums)
maps[num]++;

for (auto m : maps) {
int count = m.second;
if (count > 0) {
for (int i = 0; i < k; i++) {
int key = m.first + i;
if (maps[key] < count)
return false;

maps[key] -= count;
}
}
}

return true;
}
};

leetcode 316 - Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

Input: s = “bcabc”
Output: “abc”
Example 2:

Input: s = “cbacdcbc”
Output: “acdb”

Constraints:

1 <= s.length <= 104
s consists of 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
36
37
38
39
40
41
42
43
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> count(256, 0);
vector<bool> used(256, false);

for (int c : s)
count[c]++;

stack<char> stk;

for (char c : s) {
if (used[c]) {
count[c]--;
continue;
}

while (!stk.empty()) {
char tmp = stk.top();
if (tmp > c && count[tmp] > 0) {
stk.pop();
used[tmp] = false;
} else {
break;
}
}

stk.push(c);
count[c]--;
used[c] = true;
}

string result;
while (!stk.empty()) {
result.push_back(stk.top());
stk.pop();
}

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

return result;
}
};

leetcode 1578 - Minimum Deletion Cost to Avoid Repeating Letters

https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/

Given a string s and an array of integers cost where cost[i] is the cost of deleting the ith character in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = “abaac”, cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter “a” with cost 3 to get “abac” (String without two identical letters next to each other).
Example 2:

Input: s = “abc”, cost = [1,2,3]
Output: 0
Explanation: You don’t need to delete any character because there are no identical letters next to each other.
Example 3:

Input: s = “aabaa”, cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string (“aba”).

Constraints:

s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
int minCost(string s, vector<int>& cost) {
int i = 0, j = 1;
int size = s.size();

int min_cost = 0;

while (j < size) {
if (s[j] == s[i]) {
if (cost[j] < cost[i]) {
min_cost += cost[j];
} else {
min_cost += cost[i];
i = j;
}
} else {
i = j;
}

j++;
}

return min_cost;
}
};

class Solution01 {
public:
int minCost(string s, vector<int>& cost) {
stack<int> stk;

int total = 0;

for (int i = 0; i < s.size(); i++) {
if (stk.empty())
stk.push(i);
else {
int k = stk.top();
if (s[k] != s[i])
stk.push(i);
else {
if (cost[k] > cost[i])
total += cost[i];
else {
total += cost[k];
stk.pop();
stk.push(i);
}
}
}
}

return total;
}
};

leetcode 1171 - Remove Zero Sum Consecutive Nodes from Linked List

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

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
/**
*
Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
stack<ListNode *> stk;
unordered_map<int, ListNode *> maps;

ListNode *new_head = NULL;
ListNode *node = head;
int total = 0;

maps[0] = (ListNode *)-1; //special node

while (node) {
ListNode *next = node->next;

int tmp = total + node->val;
if (ListNode *n = maps[tmp]) {
while (!stk.empty()) {
ListNode *top_node = stk.top();
if (top_node == n) {
break;
}
stk.pop();
maps.erase(total);
total -= top_node->val;
}
} else {
if (!stk.empty())
stk.top()->next = node;
else
new_head = node;
stk.push(node);

total += node->val;
maps[total] = node;
}

node = next;
}

if (!stk.empty())
stk.top()->next = NULL;
else
new_head = NULL;

return new_head;
}
};

leetcode 767 - Reorganize String

https://leetcode.com/problems/reorganize-string/

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = “aab”
Output: “aba”
Example 2:

Input: S = “aaab”
Output: “”
Note:

S will consist of lowercase letters and have length in range [1, 500].

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
class Solution {
public:
string reorganizeString(string S) {
auto mycomp = [](const pair<char,int> &p1, const pair<char,int> &p2) {
return p1.second < p2.second;
};

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

vector<int> count(26, 0);

for (char c : S)
count[c-'a']++;

for (int i = 0; i < 26; i++) {
if (count[i] != 0)
pq.push({i+'a', count[i]});
}

string result;
pair<char, int> wait = {0, -1};

while (!pq.empty()) {
auto p = pq.top(); pq.pop();
if (!result.empty() && result.back() == p.first)
return "";

result.push_back(p.first);

if (wait.second != -1) {
pq.push(wait);
wait = {0, -1};
}

if (--p.second > 0)
wait = {p.first, p.second};
}

return wait.second != -1 ? "" : result;
}
};

leetcode 1052 - Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[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
28
29
30
31
32
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int size = customers.size();

vector<int> satisfied(size+1);
vector<int> satisfied_not_grumpy(size+1);

satisfied[0] = satisfied_not_grumpy[0] = 0;

for (int len = 1; len <= size; len++) {
int s = 0;
if (grumpy[len-1] == 0)
s = customers[len-1];

satisfied[len] = satisfied[len-1] + s;
satisfied_not_grumpy[len] = satisfied_not_grumpy[len-1] + customers[len-1];
}

int max_satisfied = 0;

for (int i = 0; i <= size - X; i++) {
int part0 = satisfied[i];
int part1 = satisfied_not_grumpy[i+X] - satisfied_not_grumpy[i];
int part2 = satisfied[size] - satisfied[i+X];

max_satisfied = max(max_satisfied, part0 + part1 + part2);
}

return max_satisfied;
}
};

leetcode 827 - Making A Large Island

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can’t change any 0 to 1, only one island with area = 4.

Notes:

1 <= grid.length = grid[0].length <= 50.
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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
class Solution {
public:
vector<int> leader;
vector<int> total;

int largestIsland(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();
int size = row * col;

leader.resize(size);
total.resize(size, 1);

for (int i = 0; i < size; i++) {
leader[i] = i;
}

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

for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 1) {
for (auto d : dirs) {
int rr = r + d[0];
int cc = c + d[1];

if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0)
continue;

Union(find(r*row + c), find(rr*row + cc));
}
}
}
}

int max_island = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 0) {
unordered_set<int> set;

for (auto d : dirs) {
int rr = r + d[0];
int cc = c + d[1];

if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0)
continue;

set.insert(find(rr * row + cc));
}

int cnt = 1;
for (auto i : set)
cnt += total[i];

max_island = max(max_island, cnt);
}
}
}

return max_island == 0 ? size : max_island;
}

int find(int i) {
if (leader[i] != i)
leader[i] = find(leader[i]);

return leader[i];
}

void Union(int i, int j) {
int x = leader[i];
int y = leader[j];

if (x == y) return;

leader[x] = y;
total[y] += total[x];
}
};

class Solution2 {
public:
int largestIsland(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();

vector<vector<bool>> seen(row, vector<bool>(col, false));
vector<vector<int>> ids(row, vector<int>(col));
unordered_map<int, int> maps;
int max_islands = 0;

int id = 0;

for (int r = 0; r < row; r++) {
for (int c = 0; c < row; c++) {
if (grid[r][c] == 0 || seen[r][c] == true)
continue;

int total = 0;
dfs(grid, r, c, seen, total, ids, id);
maps[id] = total;
max_islands = max(max_islands, total);
id++;
}
}

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

for (int r = 0; r < row; r++) {
for (int c = 0; c < row; c++) {
if (grid[r][c] == 0) {
unordered_set<int> sets;

for (auto &dir : dirs) {
int x = r + dir[0];
int y = c + dir[1];

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

int id = ids[x][y];
sets.insert(id);
}

int islands = 1;
for (int id : sets)
islands += maps[id];

max_islands = max(max_islands, islands);
}
}
}

return max_islands;
}

void dfs(vector<vector<int>>& grid, int r, int c,
vector<vector<bool>> &seen, int &total, vector<vector<int>> &ids, int id) {

int row = grid.size(), col = grid[0].size();

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

seen[r][c] = true;
total++;
ids[r][c] = id;

for (auto &dir : dirs) {
int x = r + dir[0];
int y = c + dir[1];

if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0 || seen[x][y] == true)
continue;

dfs(grid, x, y, seen, total, ids, id);
}
}
};

leetcode 1376 - Time Needed to Inform All Employees

https://leetcode.com/problems/time-needed-to-inform-all-employees/

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.
Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.
Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.
Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.
Example 5:

Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

Constraints:

1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
informTime[i] == 0 if employee i has no subordinates.
It is guaranteed that all the employees can be informed.

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
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
vector<vector<int>> tree(n);

int size = manager.size();
for (int i = 0; i < size; i++) {
if (manager[i] == -1) continue;

tree[manager[i]].push_back(i);
}

return recursive(tree, headID, informTime);
}

int recursive(vector<vector<int>> &tree, int i, vector<int>& informTime) {
int time = 0;

for (int k : tree[i]) {
time = max(time, recursive(tree, k, informTime));
}

return time + informTime[i];
}
};

leetcode 1582 - Special Positions in a Binary Matrix

https://leetcode.com/problems/special-positions-in-a-binary-matrix/

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],
[0,0,1],
[1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.
Example 2:

Input: mat = [[1,0,0],
[0,1,0],
[0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.
Example 3:

Input: mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
Output: 2
Example 4:

Input: mat = [[0,0,0,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
Output: 3

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 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
class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int r = mat.size();
int c = mat[0].size();

vector<int> rows(r, 0), cols(c, 0);

for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (mat[i][j] == 1) {
rows[i]++;
cols[j]++;
}
}
}

int total = 0;

for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1)
total++;
}
}

return total;
}
};