Leetcodeleetcode.ca
https://leetcode.ca/
3328 - Find Cities in Each State II
Welcome to Subscribe On Youtube
3328. Find Cities in Each State II ðŸ”’
Description
Table: cities
+-++
\| state \| varchar \|
\| city \| varchar \|
+-++
\| state \| city \|
+--++
Output:
+-+-+--+
\| Pennsylvania\| Philadelphia, Pittsburgh, Pottstown \| 3 \|
\| Texas \| Dallas, Taylor, Temple, Tyler \| 3 \|
\| New York \| Buffalo, Newark, New York City, Rochester \| 2 \|
+-+-+-----+
Explanation:
Pennsylvania:
Has 3 cities (meets minimum requirement)
All 3 cities start with 'P' (same as state)
matching_letter_count = 3
Texas:
Has 4 cities (meets minimum requirement)
3 cities (Taylor, Temple, Tyler) start with 'T' (same as state)
matching_letter_count = 3
New York:
Has 4 cities (meets minimum requirement)
2 cities (Newark, New York City) start with 'N' (same as state)
matching_letter_count = 2
California is not included in the output because:
Although it has 4 cities (meets minimum requirement)
No cities start with 'C' (doesn't meet the matching letter requirement)
Note:
Results are ordered by matching_letter_count in descending order
When matching_letter_count is the same (Texas and New York both have 2), they are ordered by state name alphabetically
Cities in each row are ordered alphabetically
</div>
Solutions
Solution 1: Group Aggregation + Filtering
We can group the cities table by the state field, then apply filtering on each group to retain only the groups that meet the specified conditions.
Python
SQL
import pandas as pd
def state_city_analysis(cities: pd.DataFrame) -> pd.DataFrame:
cities["matching_letter"] = cities["city"].str[0] == cities["state"].str[0]
result = (
cities.groupby("state")
.agg(
cities=("city", lambda x: ", ".join(sorted(x))),
matching_letter_count=("matching_letter", "sum"),
city_count=("city", "count"),
)
.reset_index()
)
result = result[(result["city_count"] >= 3) & (result["matching_letter_count"] > 0)]
result = result.sort_values(
by=["matching_letter_count", "state"], ascending=[False, True]
)
result = result.drop(columns=["city_count"])
return result
# Write your MySQL query statement below
SELECT
state,
GROUP_CONCAT(city ORDER BY city SEPARATOR ', ') AS cities,
COUNT(
CASE
WHEN LEFT(city, 1) = LEFT(state, 1) THEN 1
END
) AS matching_letter_count
FROM cities
GROUP BY 1
HAVING COUNT(city) >= 3 AND matching_letter_count > 0
ORDER BY 3 DESC, 1;
All Problems
All Solutions
Sun, 10 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-10-3328-Find-Cities-in-Each-State-II/
https://leetcode.ca/2024-11-10-3328-Find-Cities-in-Each-State-II/3327 - Check if DFS Strings Are Palindromes
Welcome to Subscribe On Youtube 3327. Check if DFS Strings Are Palindromes Description You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1. The tree is represented by an array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order: Iterate over each child y of x in increasing order of their numbers, and call dfs(y). Add the character s[x] to the end of the string dfsStr. Note that dfsStr is shared across all recursive calls of dfs. You need to find a boolean array answer of size n, where for each index i from 0 to n - 1, you do the following: Empty the string dfsStr and call dfs(i). If the resulting string dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false. Return the array answer. Example 1: Input: parent = [-1,0,0,1,1,2], s = "aababa" Output: [true,true,false,true,true,true] Explanation: Calling dfs(0) results in the string dfsStr = "abaaba", which is a palindrome. Calling dfs(1) results in the string dfsStr = "aba", which is a palindrome. Calling dfs(2) results in the string dfsStr = "ab", which is not a palindrome. Calling dfs(3) results in the string dfsStr = "a", which is a palindrome. Calling dfs(4) results in the string dfsStr = "b", which is a palindrome. Calling dfs(5) results in the string dfsStr = "a", which is a palindrome. Example 2: Input: parent = [-1,0,0,0,0], s = "aabcb" Output: [true,true,true,true,true] Explanation: Every call on dfs(x) results in a palindrome string. Constraints: n == parent.length == s.length 1 <= n <= 105 0 <= parent[i] <= n - 1 for all i >= 1. parent[0] == -1 parent represents a valid tree. s consists only of lowercase English letters. Solutions Solution 1: DFS + String Hashing We can use Depth-First Search (DFS) to traverse the tree and compute the entire $\textit{dfsStr}$, while also determining the interval $[l, r]$ for each node. Then, we use string hashing to compute the hash values of both $\textit{dfsStr}$ and the reverse of $\textit{dfsStr}$ to check if it is a palindrome. The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$. Java C++ Python Go class Hashing { private final long[] p; private final long[] h; private final long mod; public Hashing(String word, long base, int mod) { int n = word.length(); p = new long[n + 1]; h = new long[n + 1]; p[0] = 1; this.mod = mod; for (int i = 1; i <= n; i++) { p[i] = p[i - 1] * base % mod; h[i] = (h[i...
Sat, 09 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-09-3327-Check-if-DFS-Strings-Are-Palindromes/
https://leetcode.ca/2024-11-09-3327-Check-if-DFS-Strings-Are-Palindromes/3326 - Minimum Division Operations to Make Array Non Decreasing
Welcome to Subscribe On Youtube 3326. Minimum Division Operations to Make Array Non Decreasing Description You are given an integer array nums. Any positive divisor of a natural number x that is strictly less than x is called a proper divisor of x. For example, 2 is a proper divisor of 4, while 6 is not a proper divisor of 6. You are allowed to perform an operation any number of times on nums, where in each operation you select any one element from nums and divide it by its greatest proper divisor. Return the minimum number of operations required to make the array non-decreasing. If it is not possible to make the array non-decreasing using any number of operations, return -1. Example 1: Input: nums = [25,7] Output: 1 Explanation: Using a single operation, 25 gets divided by 5 and nums becomes [5, 7]. Example 2: Input: nums = [7,7,6] Output: -1 Example 3: Input: nums = [1,1,1,1] Output: 0 Constraints: 1 <= nums.length <= 105 1 <= nums[i] <= 106 Solutions Solution 1: Preprocessing + Greedy According to the problem description, If an integer $x$ is a prime number, then its largest proper divisor is $1$, so $x / 1 = x$, meaning $x$ cannot be divided further. If an integer $x$ is not a prime number, we assume the largest proper divisor of $x$ is $y$, then $x / y$ must be a prime number. Therefore, we find the smallest prime factor $\textit{lpf}[x]$ such that $x \bmod \textit{lpf}[x] = 0$, making $x$ become $\textit{lpf}[x]$, at which point it cannot be divided further. Thus, we can preprocess the smallest prime factor for each integer from $1$ to $10^6$. Then, we traverse the array from right to left. If the current element is greater than the next element, we change the current element to its smallest prime factor. If after changing the current element to its smallest prime factor it is still greater than the next element, it means the array cannot be made non-decreasing, and we return $-1$. Otherwise, we increment the operation count by one. Continue traversing until the entire array is processed. The time complexity for preprocessing is $O(M \times \log \log M)$, where $M = 10^6$. The time complexity for traversing the array is $O(n)$, where $n$ is the length of the array. The space complexity is $O(M)$. Java C++ Python Go TypeScript class Solution { private static final int MX = (int) 1e6 + 1; private static final int[] LPF = new int[MX + 1]; static { for (int i = 2; i <= MX; ++i) { for (int j = i; j <= MX; j += i) { if (LPF[j] == 0) { LPF[j] = i; } } } } public int minOperations(int[] nums) { int ans = 0; for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] > nums[i + 1]) { nums[i] = LPF[nums[i]]; if (nums[i] > nums[i + 1]) { return -1; }...
Sat, 09 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-09-3326-Minimum-Division-Operations-to-Make-Array-Non-Decreasing/
https://leetcode.ca/2024-11-09-3326-Minimum-Division-Operations-to-Make-Array-Non-Decreasing/3325 - Count Substrings With K-Frequency Characters I
Welcome to Subscribe On Youtube 3325. Count Substrings With K-Frequency Characters I Description Given a string s and an integer k, return the total number of substrings of s where at least one character appears at least k times. Example 1: Input: s = "abacb", k = 2 Output: 4 Explanation: The valid substrings are: "aba" (character 'a' appears 2 times). "abac" (character 'a' appears 2 times). "abacb" (character 'a' appears 2 times). "bacb" (character 'b' appears 2 times). Example 2: Input: s = "abcde", k = 1 Output: 15 Explanation: All substrings are valid because every character appears at least once. Constraints: 1 <= s.length <= 3000 1 <= k <= s.length s consists only of lowercase English letters. Solutions Solution 1: Sliding Window We can enumerate the right endpoint of the substring, and then use a sliding window to maintain the left endpoint of the substring, ensuring that the occurrence count of each character in the sliding window is less than $k$. We can use an array $\textit{cnt}$ to maintain the occurrence count of each character in the sliding window, then use a variable $\textit{l}$ to maintain the left endpoint of the sliding window, and use a variable $\textit{ans}$ to maintain the answer. When we enumerate the right endpoint, we can add the character at the right endpoint to the sliding window, then check if the occurrence count of the character at the right endpoint in the sliding window is greater than or equal to $k$. If it is, we remove the character at the left endpoint from the sliding window until the occurrence count of each character in the sliding window is less than $k$. At this point, for substrings with left endpoints in the range $[0, ..l - 1]$ and right endpoint $r$, all satisfy the problemâ€™s requirements, so we add $l$ to the answer. After enumeration, we return the answer. The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set, which in this case is the set of lowercase letters, so $|\Sigma| = 26$. Java C++ Python Go TypeScript class Solution { public int numberOfSubstrings(String s, int k) { int[] cnt = new int[26]; int ans = 0, l = 0; for (int r = 0; r < s.length(); ++r) { int c = s.charAt(r) - 'a'; ++cnt[c]; while (cnt[c] >= k) { --cnt[s.charAt(l) - 'a']; l++; } ans += l; } return ans; } } class Solution { public: int numberOfSubstrings(string s, int k) { int n = s.size(); int ans = 0, l = 0; int cnt[26]{}; for (char& c : s) { ++cnt[c - 'a']; while (cnt[c - 'a'] >= k) { --cnt[s[l++] - 'a']; } ans += l; } return ans; } }; class Solution: def numberOfSubstrings(self, s: str, k: int) -> int: cnt = Counter() ans = l = 0 for c in s: cnt[c] += 1 while cnt[c] >= k: cnt[s[l]] -=...
Sat, 09 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-09-3325-Count-Substrings-With-K-Frequency-Characters-I/
https://leetcode.ca/2024-11-09-3325-Count-Substrings-With-K-Frequency-Characters-I/3324 - Find the Sequence of Strings Appeared on the Screen
Welcome to Subscribe On Youtube 3324. Find the Sequence of Strings Appeared on the Screen Description You are given a string target. Alice is going to type target on her computer using a special keyboard that has only two keys: Key 1 appends the character "a" to the string on the screen. Key 2 changes the last character of the string on the screen to its next character in the English alphabet. For example, "c" changes to "d" and "z" changes to "a". Note that initially there is an empty string "" on the screen, so she can only press key 1. Return a list of all strings that appear on the screen as Alice types target, in the order they appear, using the minimum key presses. Example 1: Input: target = "abc" Output: ["a","aa","ab","aba","abb","abc"] Explanation: The sequence of key presses done by Alice are: Press key 1, and the string on the screen becomes "a". Press key 1, and the string on the screen becomes "aa". Press key 2, and the string on the screen becomes "ab". Press key 1, and the string on the screen becomes "aba". Press key 2, and the string on the screen becomes "abb". Press key 2, and the string on the screen becomes "abc". Example 2: Input: target = "he" Output: ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"] Constraints: 1 <= target.length <= 400 target consists only of lowercase English letters. Solutions Solution 1: Simulation We can simulate Aliceâ€™s typing process, starting from an empty string and updating the string after each keystroke until the target string is obtained. The time complexity is $O(n^2 \times |\Sigma|)$, where $n$ is the length of the target string and $\Sigma$ is the character set, which in this case is the set of lowercase letters, so $|\Sigma| = 26$. Java C++ Python Go TypeScript class Solution { public List<String> stringSequence(String target) { List<String> ans = new ArrayList<>(); for (char c : target.toCharArray()) { String s = ans.isEmpty() ? "" : ans.get(ans.size() - 1); for (char a = 'a'; a <= c; ++a) { String t = s + a; ans.add(t); } } return ans; } } class Solution { public: vector<string> stringSequence(string target) { vector<string> ans; for (char c : target) { string s = ans.empty() ? "" : ans.back(); for (char a = 'a'; a <= c; ++a) { string t = s + a; ans.push_back(t); } } return ans; } }; class Solution: def stringSequence(self, target: str) -> List[str]: ans = [] for c in target: s = ans[-1] if ans else "" for a in ascii_lowercase: t = s + a ans.append(t) if a == c: break return ans func stringSequence(target string) (ans []string) { for _, c := range target { s := "" if len(ans) > 0 { s = ans[len(ans)-1] } for a := 'a'; a <= c; a++ { t := s + string(a) ans = append(ans, t) } } return } function stringSequence(target: string): string[] { const ans: string[] = []; for (const...
Sat, 09 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-09-3324-Find-the-Sequence-of-Strings-Appeared-on-the-Screen/
https://leetcode.ca/2024-11-09-3324-Find-the-Sequence-of-Strings-Appeared-on-the-Screen/3323 - Minimize Connected Groups by Inserting Interval
Welcome to Subscribe On Youtube 3323. Minimize Connected Groups by Inserting Interval ðŸ”’ Description You are given a 2D array intervals, where intervals[i] = [starti, endi] represents the start and the end of interval i. You are also given an integer k. You must add exactly one new interval [startnew, endnew] to the array such that: The length of the new interval, endnew - startnew, is at most k. After adding, the number of connected groups in intervals is minimized. A connected group of intervals is a maximal collection of intervals that, when considered together, cover a continuous range from the smallest point to the largest point with no gaps between them. Here are some examples: A group of intervals [[1, 2], [2, 5], [3, 3]] is connected because together they cover the range from 1 to 5 without any gaps. However, a group of intervals [[1, 2], [3, 4]] is not connected because the segment (2, 3) is not covered. Return the minimum number of connected groups after adding exactly one new interval to the array. Example 1: Input: intervals = [[1,3],[5,6],[8,10]], k = 3 Output: 2 Explanation: After adding the interval [3, 5], we have two connected groups: [[1, 3], [3, 5], [5, 6]] and [[8, 10]]. Example 2: Input: intervals = [[5,10],[1,1],[3,3]], k = 1 Output: 3 Explanation: After adding the interval [1, 1], we have three connected groups: [[1, 1], [1, 1]], [[3, 3]], and [[5, 10]]. Constraints: 1 <= intervals.length <= 105 intervals[i] == [starti, endi] 1 <= starti <= endi <= 109 1 <= k <= 109 Solutions Solution 1: Sorting + Binary Search First, we sort the given set of intervals $\textit{intervals}$ by their left endpoints, then merge all overlapping intervals to obtain a new set of intervals $\textit{merged}$. We can then set the initial answer to the length of $\textit{merged}$. Next, we enumerate each interval $[_, e]$ in $\textit{merged}$. Using binary search, we find the first interval in $\textit{merged}$ whose left endpoint is greater than or equal to $e + k + 1$, and let its index be $j$. We can then update the answer as $\textit{ans} = \min(\textit{ans}, |\textit{merged}| - (j - i - 1))$. Finally, we return the answer $\textit{ans}$. The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of intervals. Java C++ Python Go TypeScript class Solution { public int minConnectedGroups(int[][] intervals, int k) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); merged.add(intervals[0]); for (int i = 1; i < intervals.length; i++) { int[] interval = intervals[i]; int[] last = merged.get(merged.size() - 1); if (last[1] < interval[0]) { merged.add(interval); } else { last[1] = Math.max(last[1], interval[1]); } } int ans = merged.size(); for (int i = 0; i < merged.size(); i++) { int[] interval = merged.get(i); int j = binarySearch(merged, interval[1] + k + 1); ans = Math.min(ans, merged.size() - (j - i - 1)); } return ans; } private int binarySearch(List<int[]> nums,...
Sat, 09 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-09-3323-Minimize-Connected-Groups-by-Inserting-Interval/
https://leetcode.ca/2024-11-09-3323-Minimize-Connected-Groups-by-Inserting-Interval/3322 - Premier League Table Ranking III
Welcome to Subscribe On Youtube
3322. Premier League Table Ranking III ðŸ”’
Description
Table: SeasonStats
+++
\| season_id \| int \|
\| team_id \| int \|
\| team_name \| varchar \|
\| matches_played \| int \|
\| wins \| int \|
\| draws \| int \|
\| losses \| int \|
\| goals_for \| int \|
\| goals_against \| int \|
+++-+--++-+--++-+--++-+--+-+
\| season_id \| team_id \| team_name \| points \| goal_difference \| position \|
++--++-+--+-+
Explanation:
For the 2021 season:
Manchester City has 93 points (29 * 3 + 6 * 1) and a goal difference of 73 (99 - 26).
Liverpool has 92 points (28 * 3 + 8 * 1) and a goal difference of 68 (94 - 26).
Chelsea has 74 points (21 * 3 + 11 * 1) and a goal difference of 43 (76 - 33).
Tottenham has 71 points (22 * 3 + 5 * 1) and a goal difference of 29 (69 - 40).
Arsenal has 69 points (22 * 3 + 3 * 1) and a goal difference of 13 (61 - 48).
For the 2022 season:
Manchester City has 89 points (28 * 3 + 5 * 1) and a goal difference of 61 (94 - 33).
Arsenal has 84 points (26 * 3 + 6 * 1) and a goal difference of 45 (88 - 43).
Manchester United has 75 points (23 * 3 + 6 * 1) and a goal difference of 15 (58 - 43).
Newcastle has 71 points (19 * 3 + 14 * 1) and a goal difference of 35 (68 - 33).
Liverpool has 67 points (19 * 3 + 10 * 1) and a goal difference of 28 (75 - 47).
The teams are ranked first by points, then by goal difference, and finally by team name.
The output is ordered by season_id ascending, then by rank ascending, and finally by team_name ascending.
Solutions
Solution 1: Window Function
We can use the window function RANK() to rank the teams by grouping them by season and sorting based on points, goal difference, and team name.
Finally, we just need to sort by season_id, position, and team_name.
Python
SQL
import pandas as pd
def process_team_standings(season_stats: pd.DataFrame) -> pd.DataFrame:
season_stats["points"] = season_stats["wins"] * 3 + season_stats["draws"]
season_stats["goal_difference"] = (
season_stats["goals_for"] - season_stats["goals_against"]
)
season_stats = season_stats.sort_values(
["season_id", "points", "goal_difference", "team_name"],
ascending=[True, False, False, True],
)
season_stats["position"] = season_stats.groupby("season_id").cumcount() + 1
return season_stats[
["season_id", "team_id", "team_name", "points", "goal_difference", "position"]
]
SELECT
season_id,
team_id,
team_name,
wins * 3 + draws points,
goals_for - goals_against goal_difference,
RANK() OVER (
PARTITION BY season_id
ORDER BY wins * 3 + draws DESC, goals_for - goals_against DESC, team_name
) position
FROM SeasonStats
ORDER BY 1, 6, 3;
All Problems
All Solutions
Fri, 08 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-08-3322-Premier-League-Table-Ranking-III/
https://leetcode.ca/2024-11-08-3322-Premier-League-Table-Ranking-III/3321 - Find X-Sum of All K-Long Subarrays II
Welcome to Subscribe On Youtube 3321. Find X-Sum of All K-Long Subarrays II Description You are given an array nums of n integers and two integers k and x. The x-sum of an array is calculated by the following procedure: Count the occurrences of all elements in the array. Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent. Calculate the sum of the resulting array. Note that if an array has less than x distinct elements, its x-sum is the sum of the array. Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1]. Example 1: Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2 Output: [6,10,12] Explanation: For subarray [1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2. For subarray [1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times. For subarray [2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3. Example 2: Input: nums = [3,8,7,8,7,5], k = 2, x = 2 Output: [11,15,15,15,12] Explanation: Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1]. Constraints: nums.length == n 1 <= n <= 105 1 <= nums[i] <= 109 1 <= x <= k <= nums.length Solutions Solution 1: Hash Table + Ordered Set We use a hash table $\textit{cnt}$ to count the occurrences of each element in the window, an ordered set $\textit{l}$ to store the $x$ elements with the highest occurrences in the window, and another ordered set $\textit{r}$ to store the remaining elements. We maintain a variable $\textit{s}$ to represent the sum of the elements in $\textit{l}$. Initially, we add the first $k$ elements to the window, update the ordered sets $\textit{l}$ and $\textit{r}$, and calculate the value of $\textit{s}$. If the size of $\textit{l}$ is less than $x$ and $\textit{r}$ is not empty, we repeatedly move the largest element from $\textit{r}$ to $\textit{l}$ until the size of $\textit{l}$ equals $x$, updating the value of $\textit{s}$ in the process. If the size of $\textit{l}$ is greater than $x$, we repeatedly move the smallest element from $\textit{l}$ to $\textit{r}$ until the size of $\textit{l}$ equals $x$, updating the value of $\textit{s}$ in the process. At this point, we can calculate the current windowâ€™s $\textit{x-sum}$ and add it to the answer array. Then we remove the left boundary element of...
Thu, 07 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-07-3321-Find-X-Sum-of-All-K-Long-Subarrays-II/
https://leetcode.ca/2024-11-07-3321-Find-X-Sum-of-All-K-Long-Subarrays-II/3320 - Count The Number of Winning Sequences
Welcome to Subscribe On Youtube 3320. Count The Number of Winning Sequences Description Alice and Bob are playing a fantasy battle game consisting of n rounds where they summon one of three magical creatures each round: a Fire Dragon, a Water Serpent, or an Earth Golem. In each round, players simultaneously summon their creature and are awarded points as follows: If one player summons a Fire Dragon and the other summons an Earth Golem, the player who summoned the Fire Dragon is awarded a point. If one player summons a Water Serpent and the other summons a Fire Dragon, the player who summoned the Water Serpent is awarded a point. If one player summons an Earth Golem and the other summons a Water Serpent, the player who summoned the Earth Golem is awarded a point. If both players summon the same creature, no player is awarded a point. You are given a string s consisting of n characters 'F', 'W', and 'E', representing the sequence of creatures Alice will summon in each round: If s[i] == 'F', Alice summons a Fire Dragon. If s[i] == 'W', Alice summons a Water Serpent. If s[i] == 'E', Alice summons an Earth Golem. Bob’s sequence of moves is unknown, but it is guaranteed that Bob will never summon the same creature in two consecutive rounds. Bob beats Alice if the total number of points awarded to Bob after n rounds is strictly greater than the points awarded to Alice. Return the number of distinct sequences Bob can use to beat Alice. Since the answer may be very large, return it modulo 109 + 7. Example 1: Input: s = "FFF" Output: 3 Explanation: Bob can beat Alice by making one of the following sequences of moves: "WFW", "FWF", or "WEW". Note that other winning sequences like "WWE" or "EWW" are invalid since Bob cannot make the same move twice in a row. Example 2: Input: s = "FWEFW" Output: 18 Explanation: Bob can beat Alice by making one of the following sequences of moves: "FWFWF", "FWFWE", "FWEFE", "FWEWE", "FEFWF", "FEFWE", "FEFEW", "FEWFE", "WFEFE", "WFEWE", "WEFWF", "WEFWE", "WEFEF", "WEFEW", "WEWFW", "WEWFE", "EWFWE", or "EWEWE". Constraints: 1 <= s.length <= 1000 s[i] is one of 'F', 'W', or 'E'. Solutions Solution 1: Memoization Search We design a function $\textit{dfs}(i, j, k)$, where $i$ represents starting from the $i$-th character of the string $s$, $j$ represents the current score difference between $\textit{Alice}$ and $\textit{Bob}$, and $k$ represents the last creature summoned by $\textit{Bob}$. The function calculates how many sequences of moves $\textit{Bob}$ can make to defeat $\textit{Alice}$. The answer is $\textit{dfs}(0, 0, -1)$, where $-1$ indicates that $\textit{Bob}$ has not summoned any creatures yet. In languages other than Python, since the score difference can be negative, we can add $n$ to the score difference to ensure it is non-negative. The calculation process of the function $\textit{dfs}(i, j, k)$ is as follows: If $n - i \leq j$, then the remaining rounds are not enough...
Wed, 06 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-06-3320-Count-The-Number-of-Winning-Sequences/
https://leetcode.ca/2024-11-06-3320-Count-The-Number-of-Winning-Sequences/3319 - K-th Largest Perfect Subtree Size in Binary Tree
Welcome to Subscribe On Youtube 3319. K-th Largest Perfect Subtree Size in Binary Tree Description You are given the root of a binary tree and an integer k. Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist. A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children. Example 1: Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2 Output: 3 Explanation: The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non-increasing order are [3, 3, 1, 1, 1, 1, 1, 1]. The 2nd largest size is 3. Example 2: Input: root = [1,2,3,4,5,6,7], k = 1 Output: 7 Explanation: The sizes of the perfect binary subtrees in non-increasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7. Example 3: Input: root = [1,2,3,null,4], k = 3 Output: -1 Explanation: The sizes of the perfect binary subtrees in non-increasing order are [1, 1]. There are fewer than 3 perfect binary subtrees. Constraints: The number of nodes in the tree is in the range [1, 2000]. 1 <= Node.val <= 2000 1 <= k <= 1024 Solutions Solution 1: DFS + Sorting We define a function $\textit{dfs}$ to calculate the size of the perfect binary subtree rooted at the current node, using an array $\textit{nums}$ to record the sizes of all perfect binary subtrees. If the subtree rooted at the current node is not a perfect binary subtree, it returns $-1$. The execution process of the function $\textit{dfs}$ is as follows: If the current node is null, return $0$; Recursively calculate the sizes of the perfect binary subtrees of the left and right subtrees, denoted as $l$ and $r$ respectively; If the sizes of the left and right subtrees are not equal, or if the sizes of the left and right subtrees are less than $0$, return $-1$; Calculate the size of the perfect binary subtree rooted at the current node $\textit{cnt} = l + r + 1$, and add $\textit{cnt}$ to the array $\textit{nums}$; Return $\textit{cnt}$. We call the $\textit{dfs}$ function to calculate the sizes of all perfect binary subtrees. If the length of the array $\textit{nums}$ is less than $k$, return $-1$. Otherwise, sort the array $\textit{nums}$ in descending order and return the $k$-th largest perfect binary subtree size. The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. Java C++ Python Go TypeScript /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List<Integer> nums =...
Tue, 05 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-05-3319-K-th-Largest-Perfect-Subtree-Size-in-Binary-Tree/
https://leetcode.ca/2024-11-05-3319-K-th-Largest-Perfect-Subtree-Size-in-Binary-Tree/3318 - Find X-Sum of All K-Long Subarrays I
Welcome to Subscribe On Youtube 3318. Find X-Sum of All K-Long Subarrays I Description You are given an array nums of n integers and two integers k and x. The x-sum of an array is calculated by the following procedure: Count the occurrences of all elements in the array. Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent. Calculate the sum of the resulting array. Note that if an array has less than x distinct elements, its x-sum is the sum of the array. Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1]. Example 1: Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2 Output: [6,10,12] Explanation: For subarray [1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2. For subarray [1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times. For subarray [2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3. Example 2: Input: nums = [3,8,7,8,7,5], k = 2, x = 2 Output: [11,15,15,15,12] Explanation: Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1]. Constraints: 1 <= n == nums.length <= 50 1 <= nums[i] <= 50 1 <= x <= k <= nums.length Solutions Solution 1: Hash Table + Ordered Set We use a hash table $\textit{cnt}$ to count the occurrences of each element in the window, an ordered set $\textit{l}$ to store the $x$ elements with the highest occurrences in the window, and another ordered set $\textit{r}$ to store the remaining elements. We maintain a variable $\textit{s}$ to represent the sum of the elements in $\textit{l}$. Initially, we add the first $k$ elements to the window, update the ordered sets $\textit{l}$ and $\textit{r}$, and calculate the value of $\textit{s}$. If the size of $\textit{l}$ is less than $x$ and $\textit{r}$ is not empty, we repeatedly move the largest element from $\textit{r}$ to $\textit{l}$ until the size of $\textit{l}$ equals $x$, updating the value of $\textit{s}$ in the process. If the size of $\textit{l}$ is greater than $x$, we repeatedly move the smallest element from $\textit{l}$ to $\textit{r}$ until the size of $\textit{l}$ equals $x$, updating the value of $\textit{s}$ in the process. At this point, we can calculate the current windowâ€™s $\textit{x-sum}$ and add it to the answer array. Then we remove the left boundary element of the...
Mon, 04 Nov 2024 00:00:00 -0800
https://leetcode.ca/2024-11-04-3318-Find-X-Sum-of-All-K-Long-Subarrays-I/
https://leetcode.ca/2024-11-04-3318-Find-X-Sum-of-All-K-Long-Subarrays-I/3317 - Find the Number of Possible Ways for an Event
Welcome to Subscribe On Youtube 3317. Find the Number of Possible Ways for an Event Description You are given three integers n, x, and y. An event is being held for n performers. When a performer arrives, they are assigned to one of the x stages. All performers assigned to the same stage will perform together as a band, though some stages might remain empty. After all performances are completed, the jury will award each band a score in the range [1, y]. Return the total number of possible ways the event can take place. Since the answer may be very large, return it modulo 109 + 7. Note that two events are considered to have been held differently if either of the following conditions is satisfied: Any performer is assigned a different stage. Any band is awarded a different score. Example 1: Input: n = 1, x = 2, y = 3 Output: 6 Explanation: There are 2 ways to assign a stage to the performer. The jury can award a score of either 1, 2, or 3 to the only band. Example 2: Input: n = 5, x = 2, y = 1 Output: 32 Explanation: Each performer will be assigned either stage 1 or stage 2. All bands will be awarded a score of 1. Example 3: Input: n = 3, x = 3, y = 4 Output: 684 Constraints: 1 <= n, x, y <= 1000 Solutions Solution 1: Dynamic Programming We define $f[i][j]$ to represent the number of ways to arrange the first $i$ performers into $j$ programs. Initially, $f[0][0] = 1$, and the rest $f[i][j] = 0$. For $f[i][j]$, where $1 \leq i \leq n$ and $1 \leq j \leq x$, we consider the $i$-th performer: If the performer is assigned to a program that already has performers, there are $j$ choices, i.e., $f[i - 1][j] \times j$; If the performer is assigned to a program that has no performers, there are $x - (j - 1)$ choices, i.e., $f[i - 1][j - 1] \times (x - (j - 1))$. So the state transition equation is: \[f[i][j] = f[i - 1][j] \times j + f[i - 1][j - 1] \times (x - (j - 1))\] For each $j$, there are $y^j$ choices, so the final answer is: \[\sum_{j = 1}^{x} f[n][j] \times y^j\] Note that since the answer can be very large, we need to take the modulo $10^9 + 7$. The time complexity is $O(n \times x)$, and the space complexity is $O(n \times x)$. Here, $n$ and $x$ represent the number of performers and the number of programs, respectively. Java C++ Python Go TypeScript class Solution { public int numberOfWays(int n, int x, int y) { final int mod = (int) 1e9 + 7; long[][] f = new long[n + 1][x + 1]; f[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= x; ++j) { f[i][j] = (f[i -...
Sun, 03 Nov 2024 00:00:00 -0700
https://leetcode.ca/2024-11-03-3317-Find-the-Number-of-Possible-Ways-for-an-Event/
https://leetcode.ca/2024-11-03-3317-Find-the-Number-of-Possible-Ways-for-an-Event/3316 - Find Maximum Removals From Source String
Welcome to Subscribe On Youtube 3316. Find Maximum Removals From Source String Description You are given a string source of size n, a string pattern that is a subsequence of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1]. We define an operation as removing a character at an index idx from source such that: idx is an element of targetIndices. pattern remains a subsequence of source after removing the character. Performing an operation does not change the indices of the other characters in source. For example, if you remove 'c' from "acb", the character at index 2 would still be 'b'. Return the maximum number of operations that can be performed. Example 1: Input: source = "abbaa", pattern = "aba", targetIndices = [0,1,2] Output: 1 Explanation: We can't remove source[0] but we can do either of these two operations: Remove source[1], so that source becomes "a_baa". Remove source[2], so that source becomes "ab_aa". Example 2: Input: source = "bcda", pattern = "d", targetIndices = [0,3] Output: 2 Explanation: We can remove source[0] and source[3] in two operations. Example 3: Input: source = "dda", pattern = "dda", targetIndices = [0,1,2] Output: 0 Explanation: We can't remove any character from source. Example 4: Input: source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4] Output: 2 Explanation: We can remove source[2] and source[3] in two operations. Constraints: 1 <= n == source.length <= 3 * 103 1 <= pattern.length <= n 1 <= targetIndices.length <= n targetIndices is sorted in ascending order. The input is generated such that targetIndices contains distinct elements in the range [0, n - 1]. source and pattern consist only of lowercase English letters. The input is generated such that pattern appears as a subsequence in source. Solutions Solution 1: Dynamic Programming We define $f[i][j]$ to represent the maximum number of deletions in the first $i$ characters of $\textit{source}$ that match the first $j$ characters of $\textit{pattern}$. Initially, $f[0][0] = 0$, and the rest $f[i][j] = -\infty$. For $f[i][j]$, we have two choices: We can skip the $i$-th character of $\textit{source}$, in which case $f[i][j] = f[i-1][j] + \text{int}(i-1 \in \textit{targetIndices})$; If $\textit{source}[i-1] = \textit{pattern}[j-1]$, we can match the $i$-th character of $\textit{source}$, in which case $f[i][j] = \max(f[i][j], f[i-1][j-1])$. The final answer is $f[m][n]$. The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the lengths of $\textit{source}$ and $\textit{pattern}$, respectively. Java C++ Python Go TypeScript class Solution { public int maxRemovals(String source, String pattern, int[] targetIndices) { int m = source.length(), n = pattern.length(); int[][] f = new int[m + 1][n + 1]; final int inf = Integer.MAX_VALUE / 2; for (var g : f) { Arrays.fill(g, -inf); } f[0][0] = 0; int[] s = new int[m]; for (int i : targetIndices) { s[i] = 1; } for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n;...
Sat, 02 Nov 2024 00:00:00 -0700
https://leetcode.ca/2024-11-02-3316-Find-Maximum-Removals-From-Source-String/
https://leetcode.ca/2024-11-02-3316-Find-Maximum-Removals-From-Source-String/3315 - Construct the Minimum Bitwise Array II
Welcome to Subscribe On Youtube 3315. Construct the Minimum Bitwise Array II Description You are given an array nums consisting of n prime integers. You need to construct an array ans of length n, such that, for each index i, the bitwise OR of ans[i] and ans[i] + 1 is equal to nums[i], i.e. ans[i] OR (ans[i] + 1) == nums[i]. Additionally, you must minimize each value of ans[i] in the resulting array. If it is not possible to find such a value for ans[i] that satisfies the condition, then set ans[i] = -1. Example 1: Input: nums = [2,3,5,7] Output: [-1,1,4,3] Explanation: For i = 0, as there is no value for ans[0] that satisfies ans[0] OR (ans[0] + 1) = 2, so ans[0] = -1. For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 3 is 1, because 1 OR (1 + 1) = 3. For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 5 is 4, because 4 OR (4 + 1) = 5. For i = 3, the smallest ans[3] that satisfies ans[3] OR (ans[3] + 1) = 7 is 3, because 3 OR (3 + 1) = 7. Example 2: Input: nums = [11,13,31] Output: [9,12,15] Explanation: For i = 0, the smallest ans[0] that satisfies ans[0] OR (ans[0] + 1) = 11 is 9, because 9 OR (9 + 1) = 11. For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 13 is 12, because 12 OR (12 + 1) = 13. For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 31 is 15, because 15 OR (15 + 1) = 31. Constraints: 1 <= nums.length <= 100 2 <= nums[i] <= 109 nums[i] is a prime number. Solutions Solution 1: Bit Manipulation For an integer $a$, the result of $a \lor (a + 1)$ is always odd. Therefore, if $\text{nums[i]}$ is even, then $\text{ans}[i]$ does not exist, and we directly return $-1$. In this problem, $\textit{nums}[i]$ is a prime number, so to check if it is even, we only need to check if it equals $2$. If $\text{nums[i]}$ is odd, suppose $\text{nums[i]} = \text{0b1101101}$. Since $a \lor (a + 1) = \text{nums[i]}$, this is equivalent to changing the last $0$ bit of $a$ to $1$. To solve for $a$, we need to change the bit after the last $0$ in $\text{nums[i]}$ to $0$. We start traversing from the least significant bit (index $1$) and find the first $0$ bit. If it is at position $i$, we change the $(i - 1)$-th bit of $\text{nums[i]}$ to $1$, i.e., $\text{ans}[i] = \text{nums[i]} \oplus 2^{i - 1}$. By traversing all elements in $\text{nums}$, we can obtain the answer. The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the length of the array $\text{nums}$ and the maximum value in the array, respectively. Ignoring the space consumption of...
Fri, 01 Nov 2024 00:00:00 -0700
https://leetcode.ca/2024-11-01-3315-Construct-the-Minimum-Bitwise-Array-II/
https://leetcode.ca/2024-11-01-3315-Construct-the-Minimum-Bitwise-Array-II/3314 - Construct the Minimum Bitwise Array I
Welcome to Subscribe On Youtube 3314. Construct the Minimum Bitwise Array I Description You are given an array nums consisting of n prime integers. You need to construct an array ans of length n, such that, for each index i, the bitwise OR of ans[i] and ans[i] + 1 is equal to nums[i], i.e. ans[i] OR (ans[i] + 1) == nums[i]. Additionally, you must minimize each value of ans[i] in the resulting array. If it is not possible to find such a value for ans[i] that satisfies the condition, then set ans[i] = -1. Example 1: Input: nums = [2,3,5,7] Output: [-1,1,4,3] Explanation: For i = 0, as there is no value for ans[0] that satisfies ans[0] OR (ans[0] + 1) = 2, so ans[0] = -1. For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 3 is 1, because 1 OR (1 + 1) = 3. For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 5 is 4, because 4 OR (4 + 1) = 5. For i = 3, the smallest ans[3] that satisfies ans[3] OR (ans[3] + 1) = 7 is 3, because 3 OR (3 + 1) = 7. Example 2: Input: nums = [11,13,31] Output: [9,12,15] Explanation: For i = 0, the smallest ans[0] that satisfies ans[0] OR (ans[0] + 1) = 11 is 9, because 9 OR (9 + 1) = 11. For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 13 is 12, because 12 OR (12 + 1) = 13. For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 31 is 15, because 15 OR (15 + 1) = 31. Constraints: 1 <= nums.length <= 100 2 <= nums[i] <= 1000 nums[i] is a prime number. Solutions Solution 1: Bit Manipulation For an integer $a$, the result of $a \lor (a + 1)$ is always odd. Therefore, if $\text{nums[i]}$ is even, then $\text{ans}[i]$ does not exist, and we directly return $-1$. In this problem, $\textit{nums}[i]$ is a prime number, so to check if it is even, we only need to check if it equals $2$. If $\text{nums[i]}$ is odd, suppose $\text{nums[i]} = \text{0b1101101}$. Since $a \lor (a + 1) = \text{nums[i]}$, this is equivalent to changing the last $0$ bit of $a$ to $1$. To solve for $a$, we need to change the bit after the last $0$ in $\text{nums[i]}$ to $0$. We start traversing from the least significant bit (index $1$) and find the first $0$ bit. If it is at position $i$, we change the $(i - 1)$-th bit of $\text{nums[i]}$ to $1$, i.e., $\text{ans}[i] = \text{nums[i]} \oplus 2^{i - 1}$. By traversing all elements in $\text{nums}$, we can obtain the answer. The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the length of the array $\text{nums}$ and the maximum value in the array, respectively. Ignoring the space consumption of...
Thu, 31 Oct 2024 00:00:00 -0700
https://leetcode.ca/2024-10-31-3314-Construct-the-Minimum-Bitwise-Array-I/
https://leetcode.ca/2024-10-31-3314-Construct-the-Minimum-Bitwise-Array-I/3313 - Find the Last Marked Nodes in Tree
Welcome to Subscribe On Youtube 3313. Find the Last Marked Nodes in Tree ðŸ”’ Description There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree. Initially, all nodes are unmarked. After every second, you mark all unmarked nodes which have at least one marked node adjacent to them. Return an array nodes where nodes[i] is the last node to get marked in the tree, if you mark node i at time t = 0. If nodes[i] has multiple answers for any node i, you can choose any one answer. Example 1: Input: edges = [[0,1],[0,2]] Output: [2,2,1] Explanation: For i = 0, the nodes are marked in the sequence: [0] -> [0,1,2]. Either 1 or 2 can be the answer. For i = 1, the nodes are marked in the sequence: [1] -> [0,1] -> [0,1,2]. Node 2 is marked last. For i = 2, the nodes are marked in the sequence: [2] -> [0,2] -> [0,1,2]. Node 1 is marked last. Example 2: Input: edges = [[0,1]] Output: [1,0] Explanation: For i = 0, the nodes are marked in the sequence: [0] -> [0,1]. For i = 1, the nodes are marked in the sequence: [1] -> [0,1]. Example 3: Input: edges = [[0,1],[0,2],[2,3],[2,4]] Output: [3,3,1,1,1] Explanation: For i = 0, the nodes are marked in the sequence: [0] -> [0,1,2] -> [0,1,2,3,4]. For i = 1, the nodes are marked in the sequence: [1] -> [0,1] -> [0,1,2] -> [0,1,2,3,4]. For i = 2, the nodes are marked in the sequence: [2] -> [0,2,3,4] -> [0,1,2,3,4]. For i = 3, the nodes are marked in the sequence: [3] -> [2,3] -> [0,2,3,4] -> [0,1,2,3,4]. For i = 4, the nodes are marked in the sequence: [4] -> [2,4] -> [0,2,3,4] -> [0,1,2,3,4]. Constraints: 2 <= n <= 105 edges.length == n - 1 edges[i].length == 2 0 <= edges[i][0], edges[i][1] <= n - 1 The input is generated such that edges represents a valid tree. Solutions Solution 1: Find the Diameter of the Tree + DFS According to the problem description, the last marked node must be one endpoint of the treeâ€™s diameter, because the distance from any node on the diameter to any other node on the diameter is the greatest. We can start a depth-first search (DFS) from any node to find the farthest node $a$, which is one endpoint of the treeâ€™s diameter. Then, starting from node $a$, we perform another depth-first search to find the farthest node $b$, which is the other endpoint of the treeâ€™s diameter. During this process, we calculate the distance from each node to node $a$, denoted as $\textit{dist2}$. Next, we perform a depth-first search starting from node $b$ to calculate the distance from each node to node $b$, denoted as $\textit{dist3}$....
Wed, 30 Oct 2024 00:00:00 -0700
https://leetcode.ca/2024-10-30-3313-Find-the-Last-Marked-Nodes-in-Tree/
https://leetcode.ca/2024-10-30-3313-Find-the-Last-Marked-Nodes-in-Tree/3312 - Sorted GCD Pair Queries
Welcome to Subscribe On Youtube 3312. Sorted GCD Pair Queries Description You are given an integer array nums of length n and an integer array queries. Let gcdPairs denote an array obtained by calculating the GCD of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order. For each query queries[i], you need to find the element at index queries[i] in gcdPairs. Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query. The term gcd(a, b) denotes the greatest common divisor of a and b. Example 1: Input: nums = [2,3,4], queries = [0,2,2] Output: [1,2,2] Explanation: gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1]. After sorting in ascending order, gcdPairs = [1, 1, 2]. So, the answer is [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2]. Example 2: Input: nums = [4,4,2,1], queries = [5,3,1,0] Output: [4,2,1,1] Explanation: gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4]. Example 3: Input: nums = [2,2], queries = [0,0] Output: [2,2] Explanation: gcdPairs = [2]. Constraints: 2 <= n == nums.length <= 105 1 <= nums[i] <= 5 * 104 1 <= queries.length <= 105 0 <= queries[i] < n * (n - 1) / 2 Solutions Solution 1: Preprocessing + Prefix Sum + Binary Search We can preprocess to obtain the occurrence count of the greatest common divisor (GCD) of all pairs in the array $\textit{nums}$, recorded in the array $\textit{cntG}$. Then, we calculate the prefix sum of the array $\textit{cntG}$. Finally, for each query, we can use binary search to find the index of the first element in the array $\textit{cntG}$ that is greater than $\textit{queries}[i]$, which is the answer. Let $\textit{mx}$ denote the maximum value in the array $\textit{nums}$, and let $\textit{cnt}$ record the occurrence count of each number in the array $\textit{nums}$. Let $\textit{cntG}[i]$ denote the number of pairs in the array $\textit{nums}$ whose GCD is equal to $i$. To calculate $\textit{cntG}[i]$, we can follow these steps: Calculate the occurrence count $v$ of multiples of $i$ in the array $\textit{nums}$. Then, the number of pairs formed by any two elements from these multiples must have a GCD that is a multiple of $i$, i.e., $\textit{cntG}[i]$ needs to be increased by $v \times (v - 1) / 2$; We need to exclude pairs whose GCD is a multiple of $i$ and greater than $i$. Therefore, for multiples $j$ of $i$, we need to subtract $\textit{cntG}[j]$. The above steps require us to traverse $i$ from large to small so that when calculating $\textit{cntG}[i]$, we have already calculated all $\textit{cntG}[j]$. Finally, we calculate the prefix sum of the array $\textit{cntG}$, and for each query, we can use binary search to find the index of the first element in the array $\textit{cntG}$ that is greater than $\textit{queries}[i]$, which is the answer. The time complexity is $O(n + (M + q) \times \log M)$, and the space complexity is...
Tue, 29 Oct 2024 00:00:00 -0700
https://leetcode.ca/2024-10-29-3312-Sorted-GCD-Pair-Queries/
https://leetcode.ca/2024-10-29-3312-Sorted-GCD-Pair-Queries/3311 - Construct 2D Grid Matching Graph Layout
Welcome to Subscribe On Youtube 3311. Construct 2D Grid Matching Graph Layout Description You are given a 2D integer array edges representing an undirected graph having n nodes, where edges[i] = [ui, vi] denotes an edge between nodes ui and vi. Construct a 2D grid that satisfies these conditions: The grid contains all nodes from 0 to n - 1 in its cells, with each node appearing exactly once. Two nodes should be in adjacent grid cells (horizontally or vertically) if and only if there is an edge between them in edges. It is guaranteed that edges can form a 2D grid that satisfies the conditions. Return a 2D integer array satisfying the conditions above. If there are multiple solutions, return any of them. Example 1: Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]] Output: [[3,1],[2,0]] Explanation: Example 2: Input: n = 5, edges = [[0,1],[1,3],[2,3],[2,4]] Output: [[4,2,3,1,0]] Explanation: Example 3: Input: n = 9, edges = [[0,1],[0,4],[0,5],[1,7],[2,3],[2,4],[2,5],[3,6],[4,6],[4,7],[6,8],[7,8]] Output: [[8,6,3],[7,4,2],[1,0,5]] Explanation: Constraints: 2 <= n <= 5 * 104 1 <= edges.length <= 105 edges[i] = [ui, vi] 0 <= ui < vi < n All the edges are distinct. The input is generated such that edges can form a 2D grid that satisfies the conditions. Solutions Solution 1 Java C++ Python Go TypeScript class Solution { public int[][] constructGridLayout(int n, int[][] edges) { List<Integer>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] e : edges) { int u = e[0], v = e[1]; g[u].add(v); g[v].add(u); } int[] deg = new int[5]; Arrays.fill(deg, -1); for (int x = 0; x < n; x++) { deg[g[x].size()] = x; } List<Integer> row = new ArrayList<>(); if (deg[1] != -1) { row.add(deg[1]); } else if (deg[4] == -1) { int x = deg[2]; for (int y : g[x]) { if (g[y].size() == 2) { row.add(x); row.add(y); break; } } } else { int x = deg[2]; row.add(x); int pre = x; x = g[x].get(0); while (g[x].size() > 2) { row.add(x); for (int y : g[x]) { if (y != pre && g[y].size() < 4) { pre = x; x = y; break; } } } row.add(x); } List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>(row)); boolean[] vis = new boolean[n]; int rowSize = row.size(); for (int i = 0; i < n / rowSize - 1; i++) { for (int x : row) { vis[x] = true; } List<Integer> nxt = new ArrayList<>(); for (int x : row) { for (int y : g[x]) { if (!vis[y]) { nxt.add(y); break; } } } res.add(new ArrayList<>(nxt)); row = nxt; } int[][] ans = new int[res.size()][rowSize]; for (int i = 0; i < res.size(); i++) { for (int j = 0; j < rowSize; j++) { ans[i][j] = res.get(i).get(j); } } return ans; } } class Solution { public: vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) { vector<vector<int>> g(n); for (auto& e : edges) { int u = e[0], v = e[1]; g[u].push_back(v); g[v].push_back(u); } vector<int> deg(5, -1); for (int x = 0; x...
Mon, 28 Oct 2024 00:00:00 -0700
https://leetcode.ca/2024-10-28-3311-Construct-2D-Grid-Matching-Graph-Layout/
https://leetcode.ca/2024-10-28-3311-Construct-2D-Grid-Matching-Graph-Layout/3310 - Remove Methods From Project
Welcome to Subscribe On Youtube 3310. Remove Methods From Project Description You are maintaining a project that has n methods numbered from 0 to n - 1. You are given two integers n and k, and a 2D integer array invocations, where invocations[i] = [ai, bi] indicates that method ai invokes method bi. There is a known bug in method k. Method k, along with any method invoked by it, either directly or indirectly, are considered suspicious and we aim to remove them. A group of methods can only be removed if no method outside the group invokes any methods within it. Return an array containing all the remaining methods after removing all the suspicious methods. You may return the answer in any order. If it is not possible to remove all the suspicious methods, none should be removed. Example 1: Input: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]] Output: [0,1,2,3] Explanation: Method 2 and method 1 are suspicious, but they are directly invoked by methods 3 and 0, which are not suspicious. We return all elements without removing anything. Example 2: Input: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]] Output: [3,4] Explanation: Methods 0, 1, and 2 are suspicious and they are not directly invoked by any other method. We can remove them. Example 3: Input: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]] Output: [] Explanation: All methods are suspicious. We can remove them. Constraints: 1 <= n <= 105 0 <= k <= n - 1 0 <= invocations.length <= 2 * 105 invocations[i] == [ai, bi] 0 <= ai, bi <= n - 1 ai != bi invocations[i] != invocations[j] Solutions Solution 1: Two DFS We can start from $k$ and find all suspicious methods, recording them in the array $\textit{suspicious}$. Then, we traverse from $0$ to $n-1$, starting from all non-suspicious methods, and mark all reachable methods as non-suspicious. Finally, we return all non-suspicious methods. The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$. Here, $n$ and $m$ represent the number of methods and the number of call relationships, respectively. Java C++ Python Go TypeScript class Solution { private boolean[] suspicious; private boolean[] vis; private List<Integer>[] f; private List<Integer>[] g; public List<Integer> remainingMethods(int n, int k, int[][] invocations) { suspicious = new boolean[n]; vis = new boolean[n]; f = new List[n]; g = new List[n]; Arrays.setAll(f, i -> new ArrayList<>()); Arrays.setAll(g, i -> new ArrayList<>()); for (var e : invocations) { int a = e[0], b = e[1]; f[a].add(b); f[b].add(a); g[a].add(b); } dfs(k); for (int i = 0; i < n; ++i) { if (!suspicious[i] && !vis[i]) { dfs2(i); } } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (!suspicious[i]) { ans.add(i); } } return ans; } private void dfs(int i) { suspicious[i] = true; for (int j : g[i]) { if (!suspicious[j]) { dfs(j); } } } private void dfs2(int i) { vis[i]...
Sun, 27 Oct 2024 00:00:00 -0700
https://leetcode.ca/2024-10-27-3310-Remove-Methods-From-Project/
https://leetcode.ca/2024-10-27-3310-Remove-Methods-From-Project/3309 - Maximum Possible Number by Binary Concatenation
Welcome to Subscribe On Youtube 3309. Maximum Possible Number by Binary Concatenation Description You are given an array of integers nums of size 3. Return the maximum possible number whose binary representation can be formed by concatenating the binary representation of all elements in nums in some order. Note that the binary representation of any number does not contain leading zeros. Example 1: Input: nums = [1,2,3] Output: 30 Explanation: Concatenate the numbers in the order [3, 1, 2] to get the result "11110", which is the binary representation of 30. Example 2: Input: nums = [2,8,16] Output: 1296 Explanation: Concatenate the numbers in the order [2, 8, 16] to get the result "10100010000", which is the binary representation of 1296. Constraints: nums.length == 3 1 <= nums[i] <= 127 Solutions Solution 1: Enumeration According to the problem description, the length of the array $\textit{nums}$ is $3$. We can enumerate all permutations of $\textit{nums}$, which has $3! = 6$ permutations. Then, we convert the elements of the permuted array into binary strings, concatenate these binary strings, and finally convert the concatenated binary string into a decimal number to get the maximum value. The time complexity is $O(\log M)$, where $M$ represents the maximum value of the elements in $\textit{nums}$. The space complexity is $O(1)$. Java C++ Python Go TypeScript class Solution { private int[] nums; public int maxGoodNumber(int[] nums) { this.nums = nums; int ans = f(0, 1, 2); ans = Math.max(ans, f(0, 2, 1)); ans = Math.max(ans, f(1, 0, 2)); ans = Math.max(ans, f(1, 2, 0)); ans = Math.max(ans, f(2, 0, 1)); ans = Math.max(ans, f(2, 1, 0)); return ans; } private int f(int i, int j, int k) { String a = Integer.toBinaryString(nums[i]); String b = Integer.toBinaryString(nums[j]); String c = Integer.toBinaryString(nums[k]); return Integer.parseInt(a + b + c, 2); } } class Solution { public: int maxGoodNumber(vector<int>& nums) { int ans = 0; auto f = [&](vector<int>& nums) { int res = 0; vector<int> t; for (int x : nums) { for (; x; x >>= 1) { t.push_back(x & 1); } } while (t.size()) { res = res * 2 + t.back(); t.pop_back(); } return res; }; for (int i = 0; i < 6; ++i) { ans = max(ans, f(nums)); next_permutation(nums.begin(), nums.end()); } return ans; } }; class Solution: def maxGoodNumber(self, nums: List[int]) -> int: ans = 0 for arr in permutations(nums): num = int("".join(bin(i)[2:] for i in arr), 2) ans = max(ans, num) return ans func maxGoodNumber(nums []int) int { f := func(i, j, k int) int { a := strconv.FormatInt(int64(nums[i]), 2) b := strconv.FormatInt(int64(nums[j]), 2) c := strconv.FormatInt(int64(nums[k]), 2) res, _ := strconv.ParseInt(a+b+c, 2, 64) return int(res) } ans := f(0, 1, 2) ans = max(ans, f(0, 2, 1)) ans = max(ans, f(1, 0, 2)) ans = max(ans, f(1, 2, 0)) ans = max(ans, f(2, 0, 1)) ans = max(ans, f(2, 1, 0)) return ans } function maxGoodNumber(nums: number[]): number { const f = (i: number, j: number, k: number): number => {...
Sat, 26 Oct 2024 00:00:00 -0700
https://leetcode.ca/2024-10-26-3309-Maximum-Possible-Number-by-Binary-Concatenation/
https://leetcode.ca/2024-10-26-3309-Maximum-Possible-Number-by-Binary-Concatenation/