leetcode 1081 - Smallest Subsequence of Distinct Characters

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Example 1:

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

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

Constraints:

1 <= s.length <= 1000
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
class Solution {
public:
string smallestSubsequence(string s) {
string result;

vector<int> count(26, 0);
for (char c : s)
count[c - 'a']++;

vector<bool> used(26, false);

for (char c : s) {
count[c - 'a']--;
if (used[c - 'a'])
continue;
while (!result.empty() && c < result.back() && count[result.back() - 'a'] > 0) {
used[result.back() - 'a'] = false;
result.pop_back();
}

result.push_back(c);
used[c - 'a'] = true;
}

return result;
}
};

leetcode 995 - Minimum Number of K Consecutive Bit Flips

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/239284/C%2B%2B-greedy-stack-and-O(1)-memory

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].
Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can’t make the array become [1,1,1].
Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

1 <= A.length <= 30000
1 <= K <= A.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int size = A.size();
int flip = 0;
queue<int> q;

for (int i = 0; i < size; i++) {
if (A[i] != (q.size() % 2 ? 0 : 1)) {
flip++;
q.push(i + K - 1);
}

if (!q.empty() && i >= q.front())
q.pop();
}

return q.empty() ? flip : -1;
}
};

leetcode 960 - Delete Columns to Make Sorted III

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“babca”,”bbazb”] and deletion indices {0, 1, 4}, then the final array after deletions is [“bc”,”az”].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= … <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= … <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

Input: [“babca”,”bbazb”]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = [“bc”, “az”].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn’t necessarily in lexicographic order.
Example 2:

Input: [“edcba”]
Output: 4
Explanation: If we delete less than 4 columns, the only row won’t be lexicographically sorted.
Example 3:

Input: [“ghi”,”def”,”abc”]
Output: 0
Explanation: All rows are already lexicographically sorted.

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

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

int max_len = 0;

vector<int> dp(col);
dp[0] = 1;

for (int c = 1; c < col; c++) {
dp[c] = 1;

for (int k = 0; k < c; k++) {
if (greater(A, c, k))
dp[c] = max(dp[c], dp[k] + 1);
}

max_len = max(max_len, dp[c]);
}

return col - max_len;
}

bool greater(vector<string>& A, int c1, int c2) {
int row = A.size();

for (int r = 0; r < row; r++) {
if (A[r][c1] < A[r][c2])
return false;
}

return true;
}
};

leetcode 955 - Delete Columns to Make Sorted II

https://leetcode.com/problems/delete-columns-to-make-sorted-ii/
https://leetcode.com/problems/delete-columns-to-make-sorted-ii/discuss/203182/JavaC%2B%2BPython-Greedy-Solution-O(MN)

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”,”vyz”].

Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] … <= A[A.length - 1]).

Return the minimum possible value of D.length.

Example 1:

Input: [“ca”,”bb”,”ac”]
Output: 1
Explanation:
After deleting the first column, A = [“a”, “b”, “c”].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.
Example 2:

Input: [“xc”,”yb”,”za”]
Output: 0
Explanation:
A is already in lexicographic order, so we don’t need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= …)
Example 3:

Input: [“zyx”,”wvu”,”tsr”]
Output: 3
Explanation:
We have to delete every column.

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

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 minDeletionSize(vector<string>& A) {
int row = A.size(), col = A[0].size();
vector<bool> sorted(row - 1, false);
int del = 0;

for (int c = 0; c < col; c++) {
int r;
for (r = 0; r < row - 1; r++) {
if (!sorted[r] && A[r][c] > A[r+1][c]) {
del++;
break;
}
}

if (r < row - 1)
continue;

for (r = 0; r < row - 1; r++) {
sorted[r] = sorted[r] || (A[r][c] < A[r+1][c]);
}
}

return del;
}
};

leetcode 941 - Valid Mountain Array

https://leetcode.com/problems/valid-mountain-array/

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false
Example 2:

Input: arr = [3,5,5]
Output: false
Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

1 <= arr.length <= 10^4
0 <= arr[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
class Solution {
public:
bool validMountainArray(vector<int>& arr) {
int size = arr.size();
int i = 0;

while (i < size) {
if (i > 0 && arr[i] <= arr[i - 1])
break;
i++;
}

if (i == 1 || i == size)
return false;

while (i < size) {
if (arr[i] >= arr[i-1])
break;
i++;
}

return i == size;
}
};

leetcode 502 - IPO

https://leetcode.com/problems/ipo/

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:
Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Note:
You may assume all numbers in the input are non-negative integers.
The length of Profits array and Capital array will not exceed 50,000.
The answer is guaranteed to fit in a 32-bit signed integer.

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
class Solution {
public:
int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
int size = Capital.size();

vector<int> idx(size);
for (int i = 0; i < size; i++)
idx[i] = i;

auto mycomp = [&](int i, int j) {
return Capital[i] < Capital[j];
};

sort(idx.begin(), idx.end(), mycomp);

priority_queue<int> pq;

int i = 0;
while (k > 0 || i < size) {
while (i < size && Capital[idx[i]] <= W) {
pq.push(Profits[idx[i]]);
i++;
}

if (pq.empty())
break;

W += pq.top();
pq.pop();

if (--k == 0)
break;
}

return W;
}
};

leetcode 330 - Patching Array

https://leetcode.com/problems/patching-array/
https://leetcode.com/problems/patching-array/discuss/78488/Solution-%2B-explanation

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].
Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

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

while (miss <= n) {
if (i < size && nums[i] <= miss)
miss += nums[i++];
else {
miss += miss;
add++;
}
}

return add;
}
};

leetcode 321 - Create Maximum Number

https://leetcode.com/problems/create-maximum-number/

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output:
[9, 8, 6, 5, 3]
Example 2:

Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output:
[6, 7, 6, 0, 4]
Example 3:

Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output:
[9, 8, 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
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int size1 = nums1.size();
int size2 = nums2.size();

vector<int> max_num;

for (int len1 = 0; len1 <= min(size1, k); len1++) {
int len2 = k - len1;

if (len2 < 0 || len2 > size2) continue;

vector<int> n1 = get_k_max_num(nums1, len1);
vector<int> n2 = get_k_max_num(nums2, len2);
vector<int> n = merge(n1, n2);
if (greater(n, 0, max_num, 0))
max_num = n;
}

return max_num;
}

vector<int> get_k_max_num(vector<int> &num, int k) {
vector<int> stk;
int size = num.size();

for (int i = 0; i < size; i++) {
int remain = size - i - 1;

while (!stk.empty() && num[i] > stk.back() &&
(int)stk.size() + remain >= k) {
stk.pop_back();
}

stk.push_back(num[i]);
}

if (stk.size() > k)
stk.resize(k);

return stk;
}

vector<int> merge(vector<int> &nums1, vector<int> &nums2) {
int size1 = nums1.size();
int size2 = nums2.size();

vector<int> result;

int i = 0, j = 0;
while (i < size1 || j < size2) {
if (greater(nums1, i, nums2, j))
result.push_back(nums1[i++]);
else
result.push_back(nums2[j++]);
}

return result;
}

bool greater(vector<int> &nums1, int i, vector<int> &nums2, int j) {
int size1 = nums1.size();
int size2 = nums2.size();

while (i < size1 || j < size2) {
if (i == size1) return false;
if (j == size2) return true;

if (nums1[i] > nums2[j]) return true;
if (nums1[i] < nums2[j]) return false;

i++;
j++;
}

return false;
}
};

leetcode 765 - Couples Holding Hands

https://leetcode.com/problems/couples-holding-hands/

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0…len(row)-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
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int size = row.size();
vector<int> pos(size);

for (int i = 0; i < size; i++)
pos[row[i]] = i;

int min_swap = 0;

for (int i = 0; i < size; i += 2) {
int val;
if (row[i] % 2 == 0)
val = row[i] + 1;
else
val = row[i] - 1;

int idx = pos[val];

if (idx != i + 1) {
pos[row[i+1]] = idx;
swap(row[idx], row[i+1]);
min_swap++;
}
}

return min_swap;
}
};

leetcode 380 - Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/

Implement the RandomizedSet class:

bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
Follow up: Could you implement the functions of the class with each function works in average O(1) time?

Example 1:

Input
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

-2^31 <= val <= 2^31 - 1
At most 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

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
class RandomizedSet {
public:
/** Initialize your data structure here. */
RandomizedSet() {

}

/** Inserts a value to the set.
Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if (maps.count(val) > 0)
return false;

data.push_back(val);
maps[val] = data.size() - 1;
return true;
}

/** Removes a value from the set.
Returns true if the set contained the specified element. */
bool remove(int val) {
if (maps.count(val) > 0) {
int idx = maps[val];
maps.erase(val);

if (idx != data.size() - 1) {
data[idx] = data.back();
maps[data.back()] = idx;
}

data.pop_back();

return true;
}

return false;
}

/** Get a random element from the set. */
int getRandom() {
int size = data.size();
int idx = rand() % size;

return data[idx];
}
private:
unordered_map<int, int> maps; //val -> pos
vector<int> data;
};

/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/