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();
*/

leetcode 1520 - Maximum Number of Non-Overlapping Substrings

https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/
https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/discuss/743223/C%2B%2BJava-Greedy-O(n)

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = “adefaddaccc”
Output: [“e”,”f”,”ccc”]
Explanation: The following are all the possible substrings that meet the conditions:
[
“adefaddaccc”
“adefadda”,
“ef”,
“e”,
“f”,
“ccc”,
]
If we choose the first string, we cannot choose anything else and we’d get only 1. If we choose “adefadda”, we are left with “ccc” which is the only one that doesn’t overlap, thus obtaining 2 substrings. Notice also, that it’s not optimal to choose “ef” since it can be split into two. Therefore, the optimal way is to choose [“e”,”f”,”ccc”] which gives us 3 substrings. No other solution of the same number of substrings exist.
Example 2:

Input: s = “abbaccd”
Output: [“d”,”bb”,”cc”]
Explanation: Notice that while the set of substrings [“d”,”abba”,”cc”] also has length 3, it’s considered incorrect since it has larger total length.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
vector<int> left_idx(26, -1);
vector<int> right_idx(26, -1);
int size = s.size();

for (int i = 0; i < size; i++) {
int c = s[i] - 'a';
if (left_idx[c] == -1)
left_idx[c] = i;
right_idx[c] = i;
}

vector<string> result;
int prev_right_idx;

for (int i = 0; i < size; i++) {
int c = s[i] - 'a';

if (left_idx[c] == i) {
int j = get_right_idx(s, i, left_idx, right_idx);
if (j != -1) {
if (result.empty() || j > prev_right_idx)
result.push_back(s.substr(i, j - i + 1));
else
result.back() = s.substr(i, j - i + 1);

prev_right_idx = j;
}
}
}

return result;
}

int get_right_idx(string &s, int i, vector<int> &left_idx,
vector<int> &right_idx) {
int right = right_idx[s[i] - 'a'];

for (int left = i; left <= right; left++) {
int c = s[left] - 'a';
if (left_idx[c] < i)
return -1;
right = max(right, right_idx[c]);
}

return right;
}
};

leetcode 1591 - Strange Printer II

https://leetcode.com/problems/strange-printer-ii/
https://leetcode.com/problems/strange-printer-ii/discuss/854151/C%2B%2B-O(n3)-solution-checking-cycle-in-dependency-graph

There is a strange printer with the following two special requirements:

On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
Once the printer has used a color for the above operation, the same color cannot be used again.
You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true
Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true
Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

Constraints:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

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
class Solution {
public:
bool isPrintable(vector<vector<int>>& targetGrid) {
int row = targetGrid.size();
int col = targetGrid[0].size();
vector<unordered_set<int>> edges(61);

for (int i = 1; i <= 60; i++) {
int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;

for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (targetGrid[r][c] == i) {
minx = min(minx, r);
maxx = max(maxx, r);
miny = min(miny, c);
maxy = max(maxy, c);
}
}
}

for (int r = minx; r <= maxx; r++) {
for (int c = miny; c <= maxy; c++) {
if (targetGrid[r][c] != i) {
edges[i].insert(targetGrid[r][c]);
}
}
}
}

vector<int> seen(61, 0);

for (int i = 1; i <= 60; i++) {
if (seen[i] == 0 && hasCycle(i, edges, seen) == true)
return false;
}

return true;
}

bool hasCycle(int i, vector<unordered_set<int>> &edges, vector<int> &seen) {
if (seen[i] == 1)
return true;

seen[i] = 1;
for (int k : edges[i]) {
if (hasCycle(k, edges, seen))
return true;
}
seen[i] = 2;

return false;
}
};

leetcode 664 - Strange Printer

https://leetcode.com/problems/strange-printer/
https://leetcode.com/problems/strange-printer/discuss/106810/Java-O(n3)-DP-Solution-with-Explanation-and-Simple-Optimization

There is a strange printer with the following two special requirements:

The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.
Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:
Input: “aaabbb”
Output: 2
Explanation: Print “aaa” first and then print “bbb”.
Example 2:
Input: “aba”
Output: 2
Explanation: Print “aaa” first and then print “b” from the second place of the string, which will cover the existing character ‘a’.
Hint: Length of the given string will not exceed 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
class Solution {
public:
int strangePrinter(string s) {
int size = s.size();

if (size == 0) return 0;

vector<vector<int>> memo(size, vector<int>(size, -1));

return strangePrinter(s, 0, size - 1, memo);
}

int strangePrinter(string &s, int i, int j, vector<vector<int>> &memo) {
if (i == j) return 1;

if (memo[i][j] != -1) return memo[i][j];

int prints = INT_MAX;

for (int k = i; k <= j - 1; k++) {
prints = min(prints, strangePrinter(s, i, k, memo) +
strangePrinter(s, k+1, j, memo) - (s[k] == s[j]));
}

memo[i][j] = prints;

return prints;
}
};

leetcode 1722 - Minimize Hamming Distance After Swap Operations

https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:

  • Swap indices 0 and 1: source = [2,1,3,4]
  • Swap indices 2 and 3: source = [2,1,4,3]
    The Hamming distance of source and target is 1 as they differ in 1 position: index 3.
    Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.
Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0

Constraints:

n == source.length == target.length
1 <= n <= 10^5
1 <= source[i], target[i] <= 10^5
0 <= allowedSwaps.length <= 10^5
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

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
class Solution {
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target,
vector<vector<int>>& allowedSwaps) {
unordered_map<int, vector<int>> graph;

for (auto &p : allowedSwaps) {
graph[p[0]].push_back(p[1]);
graph[p[1]].push_back(p[0]);
}

unordered_set<int> seen;
int same = 0;

int size = source.size();
for (int i = 0; i < size; i++) {
if (graph.count(i) == 0) {
same += source[i] == target[i];
continue;
}
if (seen.count(i) > 0)
continue;

vector<int> indexs;

dfs(graph, i, seen, indexs);
same += count_same(source, target, indexs);
}

return size - same;
}

void dfs(unordered_map<int, vector<int>> &graph, int i,
unordered_set<int> &seen, vector<int> &indexs) {
if (seen.count(i))
return;

seen.insert(i);
indexs.push_back(i);

for (int j : graph[i])
dfs(graph, j, seen, indexs);
}

int count_same(vector<int>& source, vector<int>& target, vector<int> &indexs) {
int same = 0;
unordered_map<int, int> count;

for (int i : indexs) {
if (count[source[i]] < 0)
same++;
count[source[i]]++;

if (count[target[i]] > 0)
same++;
count[target[i]]--;
}

return same;
}
};

leetcode 1674 - Minimum Moves to Make Array Complementary

https://leetcode.com/problems/minimum-moves-to-make-array-complementary/
https://leetcode.com/problems/minimum-moves-to-make-array-complementary/discuss/952773/PythonJava-simple-O(max(n-k))-method

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.
Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.
Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

Constraints:

n == nums.length
2 <= n <= 10^5
1 <= nums[i] <= limit <= 10^5
n is even.

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:
int minMoves(vector<int>& nums, int limit) {
vector<int> delta(2 * limit + 2, 0);
int n = nums.size();

for (int i = 0; i < n / 2; i++) {
int a = nums[i], b = nums[n - 1 - i];
delta[2] += 2;
delta[min(a, b) + 1]--;
delta[a + b]--;
delta[a + b + 1]++;
delta[max(a, b) + limit + 1]++;
}

int res = 2 * n, curr = 0;
for (int i = 2; i <= 2 * limit; i++) {
curr += delta[i];
res = min(res, curr);
}

return res;
}
};

leetcode 1685 - Sum of Absolute Differences in a Sorted Array

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.
Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

Constraints:

2 <= nums.length <= 10^5
1 <= nums[i] <= nums[i + 1] <= 10^4

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

int sum = 0;
for (int i = 1; i < size; i++) {
sum += i * abs(nums[i] - nums[i-1]);
result[i] = sum;
}

sum = 0;
for (int i = size - 2; i >= 0; i--) {
sum += (size - i - 1) * abs(nums[i] - nums[i+1]);
result[i] += sum;
}

return result;
}
};

leetcode 1404 - Number of Steps to Reduce a Number in Binary Representation to One

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/
https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/discuss/564287/C%2B%2BJava-O(n)

Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.

If the current number is odd, you have to add 1 to it.

It’s guaranteed that you can always reach to one for all testcases.

Example 1:

Input: s = “1101”
Output: 6
Explanation: “1101” corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.
Step 5) 4 is even, divide by 2 and obtain 2.
Step 6) 2 is even, divide by 2 and obtain 1.
Example 2:

Input: s = “10”
Output: 1
Explanation: “10” corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.
Example 3:

Input: s = “1”
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters ‘0’ or ‘1’
s[0] == ‘1’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int numSteps(string s) {
int size = s.size();
int total = 0;
int carry = 0;

for (int i = size - 1; i > 0; i--) {
total++;

if (s[i] - '0' + carry == 1) {
carry = 1;
total++;
}
}

return total + carry;
}
};

leetcode 1358 - Number of Substrings Containing All Three Characters

https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = “abcabc”
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” and “abc” (again).
Example 2:

Input: s = “aaacb”
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “aaacb”, “aacb” and “acb”.
Example 3:

Input: s = “abc”
Output: 1

Constraints:

3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.

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
class Solution {
public:
int numberOfSubstrings(string s) {
int size = s.size();

return ((long)size * (size + 1)) / 2 - noneABC(s);
}

int noneABC(string &s) {
int size = s.size();
vector<int> count(3, 0);
int total = 0;

int i = 0;
for (int j = 0; j < size; j++) {
int k = s[j] - 'a';
count[k]++;

while (count[0] >= 1 && count[1] >= 1 && count[2] >= 1) {
k = s[i++] - 'a';
count[k]--;
}

total += j - i + 1;
}

return total;
}
};

class Solution {
public:
int numberOfSubstrings(string s) {
int size = s.size();
int total = 0;

int count[3] = {0, 0, 0};
int i = 0;
for (int j = 0; j < size; j++) {
int k = s[j] - 'a';
count[k]++;

while (count[0] && count[1] && count[2]) {
k = s[i++] - 'a';
count[k]--;
}

total += i;
}

return total;
}
};