Huahua’s Tech Road

花花酱 LeetCode 1859. Sorting the Sentence

By zxi on May 29, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.

A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.

For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Example 1:

Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"
Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Example 2:

Input: s = "Myself2 Me1 I4 and3"
Output: "Me Myself and I"
Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.

Constraints:

2 <= s.length <= 200
s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
The number of words in s is between 1 and 9.
The words in s are separated by a single space.
s contains no leading or trailing spaces.

Solution: String

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

Python3

class Solution:

def sortSentence(self, s: str) -> str:

p = [(w[:-1], int(w[-1])) for w in s.split()]

p.sort(key=lambda x : x[1])

return " ".join((w for w, _ in p))

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 1859. Sorting the Sentence

Solution: String

Python3

花花酱 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++