leetcode 1353 - Maximum Number of Events That Can Be Attended

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/discuss/510263/JavaC%2B%2BPython-Priority-Queue

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
Example 2:

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

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

Input: events = [[1,100000]]
Output: 1
Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7

Constraints:

1 <= events.length <= 10^5
events[i].length == 2
1 <= startDayi <= endDayi <= 10^5

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 maxEvents(vector<vector<int>>& events) {
int size = events.size();
sort(events.begin(), events.end());

priority_queue<int, vector<int>, greater<int>> pq;

int total = 0;

int i = 0;
for (int d = 1; d <= 100000; d++) {
while (!pq.empty() && pq.top() < d)
pq.pop();

while (i < size && events[i][0] == d) {
pq.push(events[i][1]);
i++;
}

if (!pq.empty()) {
pq.pop();
total++;
}
}

return total;
}
};

leetcode 763 - Partition Labels

https://leetcode.com/problems/partition-labels/

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = “ababcbacadefegdehijhklij”
Output: [9,7,8]
Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.

Note:

S will have length in range [1, 500].
S will consist of lowercase English letters (‘a’ to ‘z’) only.

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<int> partitionLabels(string S) {
vector<int> count(26, 0);

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

unordered_map<char, int> maps;

int prev = 0;

vector<int> result;

for (int i = 0; i < S.size(); i++) {
char c = S[i];

if (++maps[c] == count[c-'a'])
maps.erase(c);

if (maps.size() == 0) {
result.push_back(i - prev + 1);
prev = i + 1;
}
}

return result;
}
};

leetcode 1673 - Find the Most Competitive Subsequence

https://leetcode.com/problems/find-the-most-competitive-subsequence/

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.
Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
1 <= k <= nums.length

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
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
stack<int> stk;

int size = nums.size();

for (int i = 0; i < size; i++) {
while (!stk.empty() && nums[i] < stk.top() && stk.size() - 1 + size - i >= k)
stk.pop();

if (stk.size() < k)
stk.push(nums[i]);
}

vector<int> result;
while (!stk.empty()) {
result.push_back(stk.top());
stk.pop();
}

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

return result;
}
};

leetcode 1664 - Ways to Make a Fair Array

https://leetcode.com/problems/ways-to-make-a-fair-array/

You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.

For example, if nums = [6,1,7,4,1]:

Choosing to remove index 1 results in nums = [6,7,4,1].
Choosing to remove index 2 results in nums = [6,1,4,1].
Choosing to remove index 4 results in nums = [6,1,7,4].
An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.

Return the number of indices that you could choose such that after the removal, nums is fair.

Example 1:

Input: nums = [2,1,6,4]
Output: 1
Explanation:
Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.
Example 2:

Input: nums = [1,1,1]
Output: 3
Explanation: You can remove any index and the remaining array is fair.
Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: You cannot make a fair array after removing any index.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int size = nums.size();

vector<vector<int>> left(size + 1, vector<int>(2));
vector<vector<int>> right(size + 1, vector<int>(2)); //{even, odd}
left[0] = {0, 0};
right[0] = {0, 0};

for (int len = 1; len <= size; len++) {
int i = len - 1;
int j = size - len;

if (i % 2 == 0) {
left[len][0] = left[len-1][0] + nums[i];
left[len][1] = left[len-1][1];
} else {
left[len][0] = left[len-1][0];
left[len][1] = left[len-1][1] + nums[i];
}

if (j % 2 == (size - 1) % 2) {
right[len][0] = right[len-1][0] + nums[j];
right[len][1] = right[len-1][1];
} else {
right[len][0] = right[len-1][0];
right[len][1] = right[len-1][1] + nums[j];
}
}

int total = 0;

for (int i = 0; i < size; i++) {
int len = size - i - 1; //right len
int even, odd;

if (i % 2 == 0) {
even = right[len][!(len % 2)];
odd = right[len][len % 2];
} else {
even = right[len][(len % 2)];
odd = right[len][!(len % 2)];
}

even += left[i][0];
odd += left[i][1];

if (even == odd)
total++;
}

return total;
}
};

leetcode 1647 - Minimum Deletions to Make Character Frequencies Unique

https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string “aab”, the frequency of ‘a’ is 2, while the frequency of ‘b’ is 1.

Example 1:

Input: s = “aab”
Output: 0
Explanation: s is already good.
Example 2:

Input: s = “aaabbbcc”
Output: 2
Explanation: You can delete two ‘b’s resulting in the good string “aaabcc”.
Another way it to delete one ‘b’ and one ‘c’ resulting in the good string “aaabbc”.
Example 3:

Input: s = “ceabaacb”
Output: 2
Explanation: You can delete both ‘c’s resulting in the good string “eabaab”.
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints:

1 <= s.length <= 10^5
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
class Solution {
public:
int minDeletions(string s) {
vector<int> count(26, 0);

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

int total = 0;
unordered_set<int> used;

for (int i = 0; i < 26; i++) {
while (count[i] > 0) {
if (used.count(count[i])) {
count[i]--;
total++;
} else {
used.insert(count[i]);
break;
}
}
}

return total;
}
};

leetcode 402 - Remove K Digits

https://leetcode.com/problems/remove-k-digits/

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:

Input: num = “1432219”, k = 3
Output: “1219”
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = “10200”, k = 1
Output: “200”
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:

Input: num = “10”, k = 2
Output: “0”
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

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
class Solution {
public:
string removeKdigits(string num, int k) {
stack<char> stk;

for (char n : num) {
while (!stk.empty() && k > 0 && stk.top() > n) {
stk.pop();
k--;
}

stk.push(n);
}

while (k--)
stk.pop();

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

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

int i = 0;
while (i < result.size()) {
if (result[i] != '0')
break;
i++;
}

if (i == result.size())
return "0";
else
return result.substr(i);
}
};

leetcode 1400 - Construct K Palindrome Strings

https://leetcode.com/problems/construct-k-palindrome-strings/
https://leetcode.com/problems/construct-k-palindrome-strings/discuss/563379/JavaC%2B%2BPython-Straight-Forward

Given a string s and an integer k. You should construct k non-empty palindrome strings using all the characters in s.

Return True if you can use all the characters in s to construct k palindrome strings or False otherwise.

Example 1:

Input: s = “annabelle”, k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions “anna” + “elble”, “anbna” + “elle”, “anellena” + “b”
Example 2:

Input: s = “leetcode”, k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.
Example 3:

Input: s = “true”, k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.
Example 4:

Input: s = “yzyzyzyzyzyzyzy”, k = 2
Output: true
Explanation: Simply you can put all z’s in one string and all y’s in the other string. Both strings will be palindrome.
Example 5:

Input: s = “cr”, k = 7
Output: false
Explanation: We don’t have enough characters in s to construct 7 palindromes.

Constraints:

1 <= s.length <= 10^5
All characters in s are lower-case English letters.
1 <= k <= 10^5

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool canConstruct(string s, int k) {
bitset<26> bits;

for (char c : s)
bits.flip(c-'a');

int odd = bits.count();

return odd <= k && k <= s.size();
}
};

leetcode 134 - Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

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
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int remain = 0;
int size = gas.size();

for (int i = 0; i < size; i++) {
remain += gas[i] - cost[i];
}

if (remain < 0) return -1;

remain = 0;
int start = 0;

for (int i = 0; i < size; i++) {
remain += gas[i] - cost[i];
if (remain < 0) {
remain = 0;
start = i + 1;
}
}

return start;
}
};

leetcode 991 - Broken Calculator

https://leetcode.com/problems/broken-calculator/

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.
Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.
Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.
Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 10^9
1 <= Y <= 10^9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int brokenCalc(int X, int Y) {
int ops = 0;

while (X < Y) {
ops++;

if (Y % 2 == 0)
Y = Y / 2;
else
Y++;
}

return ops + (X - Y);
}
};

leetcode 513 - Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:
Input:

2

/
1 3

Output:
1
Example 2:
Input:

    1
   / \
  2   3
 /   / \
4   5   6
   /
  7

Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.

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
/**
* 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 findBottomLeftValue(TreeNode* root) {
queue<TreeNode *> q;

q.push(root);
TreeNode *left_most;

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

for (int i = 0; i < size; i++) {
TreeNode *node = q.front(); q.pop();

if (i == 0)
left_most = node;

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

return left_most->val;
}
};