Huahua’s Tech Road

花花酱 LeetCode 1857. Largest Color Value in a Directed Graph

By zxi on May 29, 2021

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.

A valid path in the graph is a sequence of nodes x₁ -> x₂ -> x₃ -> ... -> x_k such that there is a directed edge from x_i to x_i+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2:

Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.

Constraints:

n == colors.length
m == edges.length
1 <= n <= 10⁵
0 <= m <= 10⁵
colors consists of lowercase English letters.
0 <= a_j, b_j < n

Solution: Topological Sorting

freq[n][c] := max freq of color c after visiting node n.

Time complexity: O(n)
Space complexity: O(n*26)

python

class Solution:

def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:

INF = 1e9

n = len(colors)

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

visited = [0] * n

freq = [[0] * 26 for _ in range(n)]

def dfs(u: int) -> int:

idx = ord(colors[u]) - ord('a')

if not visited[u]:

visited[u] = 1 # visiting

for v in g[u]:

if (dfs(v) == INF):

return INF

for c in range(26):

freq[u][c] = max(freq[u][c], freq[v][c])

freq[u][idx] += 1

visited[u] = 2 # done

return freq[u][idx] if visited[u] == 2 else INF

ans = 0

for u in range(n):

ans = max(ans, dfs(u))

if ans == INF: break

return -1 if ans == INF else ans

花花酱 LeetCode 1855. Maximum Distance Between a Pair of Values

By zxi on May 8, 2021

You are given two non-increasing 0-indexed integer arrays nums1 and nums2.

A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length, is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] >= arr[i] for every 1 <= i < arr.length.

Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
The maximum distance is 2 with pair (2,4).

Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation: The valid pairs are (0,0), (0,1), and (1,1).
The maximum distance is 1 with pair (0,1).

Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation: The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4).
The maximum distance is 2 with pair (2,4).

Example 4:

Input: nums1 = [5,4], nums2 = [3,2]
Output: 0
Explanation: There are no valid pairs, so return 0.

Constraints:

1 <= nums1.length <= 10⁵
1 <= nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁵
Both nums1 and nums2 are non-increasing.

Solution: Two Pointers

For each i, find the largest j such that nums[j] >= nums[i].

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

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& nums1, vector<int>& nums2) {

int ans = 0;

for (int i = 0, j = -1; i < nums1.size(); ++i) {

while (j + 1 < nums2.size() && nums2[j + 1] >= nums1[i]) ++j;

if (j >= i) ans = max(ans, j - i);

}

return ans;

}

};

花花酱 LeetCode 1854. Maximum Population Year

By zxi on May 8, 2021

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i^th person.

The population of some year x is the number of people alive during that year. The i^th person is counted in year x‘s population if x is in the inclusive range [birth_i, death_i - 1]. Note that the person is not counted in the year that they die.

Return the earliest year with the maximum population.

Example 1:

Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2:

Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation: 
The maximum population is 2, and it had happened in years 1960 and 1970.
The earlier year between them is 1960.

Constraints:

1 <= logs.length <= 100
1950 <= birth_i < death_i <= 2050

Solution: Simulation

Time complexity: O(n*y)
Space complexity: O(y)

C++

// Author: Huahua

class Solution {

public:

int maximumPopulation(vector<vector<int>>& logs) {

vector<int> pop(2051);

for (const auto& log : logs) {

for (int y = log[0]; y < log[1]; ++y)

++pop[y];

}

int ans = -1;

int max_pop = 0;

for (int y = 1950; y <= 2050; ++y) {

if (pop[y] > max_pop) {

max_pop = pop[y];

ans = y;

}

return ans;

}

};

花花酱 LeetCode 1851. Minimum Interval to Include Each Query

By zxi on May 8, 2021

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i^th interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as the number of integers it contains, or more formally right_i - left_i + 1.

You are also given an integer array queries. The answer to the j^th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

1 <= intervals.length <= 10⁵
1 <= queries.length <= 10⁵
intervals[i].length == 2
1 <= left_i <= right_i <= 10⁷
1 <= queries[j] <= 10⁷

Solution: Offline Processing + Priority Queue

Sort intervals by right in descending order, sort queries in descending. Add valid intervals into the priority queue (or treeset) ordered by size in ascending order. Erase invalid ones. The first one (if any) will be the one with the smallest size that contains the current query.

Time complexity: O(nlogn + mlogm + mlogn)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {

const int n = intervals.size();

const int m = queries.size();

sort(begin(intervals), end(intervals), [](const auto& a, const auto& b){

return a[1] > b[1];

});

vector<pair<int, int>> qs(m); // {query, i}

for (int i = 0; i < m; ++i)

qs[i] = {queries[i], i};

sort(rbegin(qs), rend(qs));

vector<int> ans(m);

int j = 0;

priority_queue<pair<int, int>> pq; // {-size, left}

for (const auto& [query, i] : qs) {

while (j < n && intervals[j][1] >= query) {

pq.emplace(-(intervals[j][1] - intervals[j][0] + 1),

intervals[j][0]);

++j;

}

while (!pq.empty() && pq.top().second > query)

pq.pop();

ans[i] = pq.empty() ? -1 : -pq.top().first;

}

return ans;

}

};

花花酱 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

By zxi on May 8, 2021

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":
- The 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4^th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1^st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

Constraints:

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Solution: Next Permutation + Greedy

Time complexity: O(k*n + n^2)
Space complexity: O(n)

C++

class Solution {

public:

int getMinSwaps(string s, int k) {

string t(s);

while (k--) next_permutation(begin(t), end(t));

const int n = s.length();

int ans = 0;

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

if (s[i] == t[i]) continue;

for (int j = i + 1; j < n; ++j) {

if (s[i] != t[j]) continue;

ans += j - i;

t = t.substr(0, i + 1) + t.substr(i, j - i) + t.substr(j + 1);

break;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1857. Largest Color Value in a Directed Graph

Solution: Topological Sorting

python

花花酱 LeetCode 1855. Maximum Distance Between a Pair of Values

Solution: Two Pointers

C++

花花酱 LeetCode 1854. Maximum Population Year

Solution: Simulation

C++

花花酱 LeetCode 1851. Minimum Interval to Include Each Query

Solution: Offline Processing + Priority Queue

C++

花花酱 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Solution: Next Permutation + Greedy

C++