Huahua’s Tech Road

花花酱 LeetCode 1202. Smallest String With Swaps

By zxi on September 22, 2019

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

Solution: Connected Components

Use DFS / Union-Find to find all the connected components of swapable indices. For each connected components (index group), extract the subsequence of corresponding chars as a string, sort it and put it back to the original string in the same location.

e.g. s = “dcab”, pairs = [[0,3],[1,2]]
There are two connected components: {0,3}, {1,2}
subsequences:
1. 0,3 “db”, sorted: “bd”
2. 1,2 “ca”, sorted: “ac”
0 => b
1 => a
2 => c
3 => d
final = “bacd”

Time complexity: DFS: O(nlogn + k*(V+E)), Union-Find: O(nlogn + V+E)
Space complexity: O(n)

C++/DFS

// Author: Huahua, 268 ms, 89 MB

class Solution {

public:

string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {

vector<vector<int>> g(s.length());

for (const auto& e : pairs) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

unordered_set<int> seen;

vector<int> idx;

string tmp;

function<void(int)> dfs = [&](int cur) {

if (seen.count(cur)) return;

seen.insert(cur);

idx.push_back(cur);

tmp += s[cur];

for (int nxt : g[cur]) dfs(nxt);

};

for (int i = 0; i < s.length(); ++i) {

if (seen.count(i)) continue;

idx.clear();

tmp.clear();

dfs(i);

sort(begin(tmp), end(tmp));

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

for (int k = 0; k < idx.size(); ++k)

s[idx[k]] = tmp[k];

}

return s;

}

};

C++/Union-Find

// Author: Huahua, 152 ms, 48.2 MB

class Solution {

public:

string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {

int n = s.length();

vector<int> p(n);

iota(begin(p), end(p), 0); // p = {0, 1, 2, ... n - 1}

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (const auto& e : pairs)

p[find(e[0])] = find(e[1]); // union

vector<vector<int>> idx(n);

vector<string> ss(n);

for (int i = 0; i < s.length(); ++i) {

int id = find(i);

idx[id].push_back(i); // already sorted

ss[id].push_back(s[i]);

}

for (int i = 0; i < n; ++i) {

sort(begin(ss[i]), end(ss[i]));

for (int k = 0; k < idx[i].size(); ++k)

s[idx[i][k]] = ss[i][k];

}

return s;

}

};

花花酱 LeetCode 1200. Minimum Absolute Difference

By zxi on September 22, 2019

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

Solution: Sorting

The min abs difference could only happen between consecutive numbers in sorted form.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {

sort(begin(arr), end(arr));

vector<vector<int>> ans;

int best = INT_MAX;

for (int i = 1; i < arr.size(); ++i) {

int d = abs(arr[i] - arr[i - 1]);

if (d < best) {

ans.clear();

best = d;

}

if (d == best) ans.push_back({arr[i - 1], arr[i]});

}

return ans;

}

};

花花酱 LeetCode 1201. Ugly Number III

By zxi on September 22, 2019

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It’s guaranteed that the result will be in range [1, 2 * 10^9]

Solution: Binary Search

Number of ugly numbers that are <= m are:

m / a + m / b + m / c – (m / LCM(a,b) + m / LCM(a, c) + m / LCM(b, c) + m / LCM(a, LCM(b, c))

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int nthUglyNumber(int n, long a, long b, long c) {

long l = 1;

long r = INT_MAX;

long ab = lcm(a, b);

long ac = lcm(a, c);

long bc = lcm(b, c);

long abc = lcm(a, bc);

while (l < r) {

long m = l + (r - l) / 2;

long k = m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;

if (k >= n) r = m;

else l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1192. Critical Connections in a Network

By zxi on September 15, 2019

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.

Solution: Tarjan

Time complexity: O(v+e)
Space complexity: O(v+e)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {

vector<vector<int>> g(n);

vector<int> ts(n, INT_MAX);

vector<vector<int>> ans;

int t = 0;

function<int(int, int)> tarjan = [&](int i, int p) {

int min_i = ts[i] = ++t;

for (int j : g[i]) {

if (ts[j] == INT_MAX) {

int min_j = tarjan(j, i);

min_i = min(min_i, min_j);

if (ts[i] < min_j)

ans.push_back({i, j});

} else if (j != p) {

min_i = min(min_i, ts[j]);

}

return min_i;

};

for (const auto& e : connections) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

tarjan(0, -1);

return ans;

}

};

花花酱 LeetCode 1191. K-Concatenation Maximum Sum

By zxi on September 15, 2019

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

This problem can be reduced to maxSubarray.
If k < 3: return maxSubarray(arr * k)
ans1 = maxSubarray(arr * 1)
ans2 = maxSubarray(arr * 2)
ans = max([ans1, ans2, ans2 + sum(arr) * (k – 2)])

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int kConcatenationMaxSum(vector<int>& arr, int k) {

constexpr int kMod = 1e9 + 7;

auto maxSum = [&arr](int r) {

long sum = 0;

long ans = 0;

for (int i = 0; i < r; ++i) {

for (long a : arr) {

sum = max(0L, sum += a);

ans = max(ans, sum);

}

return ans;

};

if (k < 3) return maxSum(k) % kMod;

long ans1 = maxSum(1);

long ans2 = maxSum(2);

long sum = accumulate(begin(arr), end(arr), 0L);

return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod;

}

};

Huahua's Tech Road

花花酱 LeetCode 1202. Smallest String With Swaps

Solution: Connected Components

C++/DFS

C++/Union-Find

花花酱 LeetCode 1200. Minimum Absolute Difference

Solution: Sorting

C++

花花酱 LeetCode 1201. Ugly Number III

Solution: Binary Search

C++

花花酱 LeetCode 1192. Critical Connections in a Network

Solution: Tarjan

C++

花花酱 LeetCode 1191. K-Concatenation Maximum Sum

Solution: DP

C++