2023-07-31
712. Minimum ASCII Delete Sum for Two Strings
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
Given two strings
Example 1:
Example 2:
Constraints:
•
•
712. Minimum ASCII Delete Sum for Two Strings
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
Given two strings
s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.Example 1:
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
Example 2:
Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
Constraints:
•
1 <= s1.length, s2.length <= 1000•
s1 and s2 consist of lowercase English letters.2023-08-01
77. Combinations
Topic: Backtracking
Difficulty: Medium
Problem:
Given two integers
You may return the answer in any order.
Example 1:
Example 2:
Constraints:
•
•
77. Combinations
Topic: Backtracking
Difficulty: Medium
Problem:
Given two integers
n and k, return all possible combinations of k numbers chosen from the range [1, n].You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
•
1 <= n <= 20•
1 <= k <= n2023-08-02
46. Permutations
Topic: Array, Backtracking
Difficulty: Medium
Problem:
Given an array
Example 1:
Example 2:
Example 3:
Constraints:
•
•
• All the integers of
46. Permutations
Topic: Array, Backtracking
Difficulty: Medium
Problem:
Given an array
nums of distinct integers, return all the possible permutations. You can return the answer in any order.Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
•
1 <= nums.length <= 6•
-10 <= nums[i] <= 10• All the integers of
nums are unique.2023-08-03
17. Letter Combinations of a Phone Number
Topic: Hash Table, String, Backtracking
Difficulty: Medium
Problem:
Given a string containing digits from
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Image: https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png
Example 1:
Example 2:
Example 3:
Constraints:
•
•
17. Letter Combinations of a Phone Number
Topic: Hash Table, String, Backtracking
Difficulty: Medium
Problem:
Given a string containing digits from
2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Image: https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
•
0 <= digits.length <= 4•
digits[i] is a digit in the range ['2', '9'].2023-08-04
139. Word Break
Topic: Array, Hash Table, String, Dynamic Programming, Trie, Memoization
Difficulty: Medium
Problem:
Given a string
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
• All the strings of
139. Word Break
Topic: Array, Hash Table, String, Dynamic Programming, Trie, Memoization
Difficulty: Medium
Problem:
Given a string
s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Constraints:
•
1 <= s.length <= 300•
1 <= wordDict.length <= 1000•
1 <= wordDict[i].length <= 20•
s and wordDict[i] consist of only lowercase English letters.• All the strings of
wordDict are unique.2023-08-05
95. Unique Binary Search Trees II
Topic: Dynamic Programming, Backtracking, Tree, Binary Search Tree, Binary Tree
Difficulty: Medium
Problem:
Given an integer
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg
Example 2:
Constraints:
•
95. Unique Binary Search Trees II
Topic: Dynamic Programming, Backtracking, Tree, Binary Search Tree, Binary Tree
Difficulty: Medium
Problem:
Given an integer
n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
•
1 <= n <= 82023-08-06
920. Number of Music Playlists
Topic: Math, Dynamic Programming, Combinatorics
Difficulty: Hard
Problem:
Your music player contains
• Every song is played at least once.
• A song can only be played again only if
Given
Example 1:
Example 2:
Example 3:
Constraints:
•
920. Number of Music Playlists
Topic: Math, Dynamic Programming, Combinatorics
Difficulty: Hard
Problem:
Your music player contains
n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:• Every song is played at least once.
• A song can only be played again only if
k other songs have been played.Given
n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 10^9 + 7.Example 1:
Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
Example 2:
Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].
Example 3:
Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].
Constraints:
•
0 <= k < n <= goal <= 1002023-08-07
74. Search a 2D Matrix
Topic: Array, Binary Search, Matrix
Difficulty: Medium
Problem:
You are given an
• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.
Given an integer
You must write a solution in
Example 1:
Image: https://assets.leetcode.com/uploads/2020/10/05/mat.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/10/05/mat2.jpg
Constraints:
•
•
•
•
74. Search a 2D Matrix
Topic: Array, Binary Search, Matrix
Difficulty: Medium
Problem:
You are given an
m x n integer matrix matrix with the following two properties:• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.
Given an integer
target, return true if target is in matrix or false otherwise.You must write a solution in
O(log(m * n)) time complexity.Example 1:
Image: https://assets.leetcode.com/uploads/2020/10/05/mat.jpg
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Image: https://assets.leetcode.com/uploads/2020/10/05/mat2.jpg
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
•
m == matrix.length•
n == matrix[i].length•
1 <= m, n <= 100•
-10^4 <= matrix[i][j], target <= 10^42023-08-08
33. Search in Rotated Sorted Array
Topic: Array, Binary Search
Difficulty: Medium
Problem:
There is an integer array
Prior to being passed to your function,
Given the array
You must write an algorithm with
Example 1:
Example 2:
Example 3:
Constraints:
•
•
• All values of
•
•
33. Search in Rotated Sorted Array
Topic: Array, Binary Search
Difficulty: Medium
Problem:
There is an integer array
nums sorted in ascending order (with distinct values).Prior to being passed to your function,
nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].Given the array
nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.You must write an algorithm with
O(log n) runtime complexity.Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
•
1 <= nums.length <= 5000•
-10^4 <= nums[i] <= 10^4• All values of
nums are unique.•
nums is an ascending array that is possibly rotated.•
-10^4 <= target <= 10^42023-08-09
2616. Minimize the Maximum Difference of Pairs
Topic: Array, Binary Search, Greedy
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
Note that for a pair of elements at the index
Return the minimum maximum difference among all
Example 1:
Example 2:
Constraints:
•
•
•
2616. Minimize the Maximum Difference of Pairs
Topic: Array, Binary Search, Greedy
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.Note that for a pair of elements at the index
i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.Return the minimum maximum difference among all
p pairs. We define the maximum of an empty set to be zero.Example 1:
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5.
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.
Example 2:
Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.
Constraints:
•
1 <= nums.length <= 10^5•
0 <= nums[i] <= 10^9•
0 <= p <= (nums.length)/22023-08-10
81. Search in Rotated Sorted Array II
Topic: Array, Binary Search
Difficulty: Medium
Problem:
There is an integer array
Before being passed to your function,
Given the array
You must decrease the overall operation steps as much as possible.
Example 1:
Example 2:
Constraints:
•
•
•
•
Follow up: This problem is similar to Search in Rotated Sorted Array, but
81. Search in Rotated Sorted Array II
Topic: Array, Binary Search
Difficulty: Medium
Problem:
There is an integer array
nums sorted in non-decreasing order (not necessarily with distinct values).Before being passed to your function,
nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].Given the array
nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Constraints:
•
1 <= nums.length <= 5000•
-10^4 <= nums[i] <= 10^4•
nums is guaranteed to be rotated at some pivot.•
-10^4 <= target <= 10^4Follow up: This problem is similar to Search in Rotated Sorted Array, but
nums may contain duplicates. Would this affect the runtime complexity? How and why?2023-08-11
518. Coin Change II
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
You are given an integer array
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
• All the values of
•
518. Coin Change II
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
You are given an integer array
coins representing coins of different denominations and an integer amount representing a total amount of money.Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return
0.You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints:
•
1 <= coins.length <= 300•
1 <= coins[i] <= 5000• All the values of
coins are unique.•
0 <= amount <= 50002023-08-12
63. Unique Paths II
Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium
Problem:
You are given an
An obstacle and space are marked as
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to
Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg
Constraints:
•
•
•
•
63. Unique Paths II
Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium
Problem:
You are given an
m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.An obstacle and space are marked as
1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to
2 * 10^9.Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Example 2:
Image: https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Constraints:
•
m == obstacleGrid.length•
n == obstacleGrid[i].length•
1 <= m, n <= 100•
obstacleGrid[i][j] is 0 or 1.2023-08-13
2369. Check if There is a Valid Partition For The Array
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:
1. The subarray consists of exactly
2. The subarray consists of exactly
3. The subarray consists of exactly
Return
Example 1:
Example 2:
Constraints:
•
•
2369. Check if There is a Valid Partition For The Array
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
nums. You have to partition the array into one or more contiguous subarrays.We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:
1. The subarray consists of exactly
2 equal elements. For example, the subarray [2,2] is good.2. The subarray consists of exactly
3 equal elements. For example, the subarray [4,4,4] is good.3. The subarray consists of exactly
3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.Return
true if the array has at least one valid partition. Otherwise, return false.Example 1:
Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.
Example 2:
Input: nums = [1,1,1,2]
Output: false
Explanation: There is no valid partition for this array.
Constraints:
•
2 <= nums.length <= 10^5•
1 <= nums[i] <= 10^62023-08-14
215. Kth Largest Element in an Array
Topic: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect
Difficulty: Medium
Problem:
Given an integer array
Note that it is the
Can you solve it without sorting?
Example 1:
Example 2:
Constraints:
•
•
215. Kth Largest Element in an Array
Topic: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect
Difficulty: Medium
Problem:
Given an integer array
nums and an integer k, return the k^th largest element in the array.Note that it is the
k^th largest element in the sorted order, not the k^th distinct element.Can you solve it without sorting?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
•
1 <= k <= nums.length <= 10^5•
-10^4 <= nums[i] <= 10^42023-08-15
86. Partition List
Topic: Linked List, Two Pointers
Difficulty: Medium
Problem:
Given the
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/04/partition.jpg
Example 2:
Constraints:
• The number of nodes in the list is in the range
•
•
86. Partition List
Topic: Linked List, Two Pointers
Difficulty: Medium
Problem:
Given the
head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/04/partition.jpg
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
Constraints:
• The number of nodes in the list is in the range
[0, 200].•
-100 <= Node.val <= 100•
-200 <= x <= 2002023-08-16
239. Sliding Window Maximum
Topic: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
Difficulty: Hard
Problem:
You are given an array of integers
Return the max sliding window.
Example 1:
Example 2:
Constraints:
•
•
•
239. Sliding Window Maximum
Topic: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
Difficulty: Hard
Problem:
You are given an array of integers
nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
•
1 <= nums.length <= 10^5•
-10^4 <= nums[i] <= 10^4•
1 <= k <= nums.length2023-08-17
542. 01 Matrix
Topic: Array, Dynamic Programming, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
Given an
The distance between two adjacent cells is
Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg
Constraints:
•
•
•
•
•
• There is at least one
542. 01 Matrix
Topic: Array, Dynamic Programming, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
Given an
m x n binary matrix mat, return the distance of the nearest 0 for each cell.The distance between two adjacent cells is
1.Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Constraints:
•
m == mat.length•
n == mat[i].length•
1 <= m, n <= 10^4•
1 <= m * n <= 10^4•
mat[i][j] is either 0 or 1.• There is at least one
0 in mat.2023-08-18
1615. Maximal Network Rank
Topic: Graph
Difficulty: Medium
Problem:
There is an infrastructure of
The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex2.png
Example 3:
Constraints:
•
•
•
•
•
• Each pair of cities has at most one road connecting them.
1615. Maximal Network Rank
Topic: Graph
Difficulty: Medium
Problem:
There is an infrastructure of
n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer
n and the array roads, return the maximal network rank of the entire infrastructure.Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex1.png
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex2.png
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.
Example 3:
Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
Constraints:
•
2 <= n <= 100•
0 <= roads.length <= n * (n - 1) / 2•
roads[i].length == 2•
0 <= a_i, b_i <= n-1•
a_i != b_i• Each pair of cities has at most one road connecting them.
2023-08-19
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Topic: Union Find, Graph, Sorting, Minimum Spanning Tree, Strongly Connected Component
Difficulty: Hard
Problem:
Given a weighted undirected connected graph with
Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex2.png
Constraints:
•
•
•
•
•
• All pairs
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Topic: Union Find, Graph, Sorting, Minimum Spanning Tree, Strongly Connected Component
Difficulty: Hard
Problem:
Given a weighted undirected connected graph with
n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [a_i, b_i, weight_i] represents a bidirectional and weighted edge between nodes a_i and b_i. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex1.png
Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:
Image: [https://assets.leetcode.com/uploads/2020/06/04/msts.png](https://assets.leetcode.com/uploads/2020/06/04/msts.png)
Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex2.png
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
Constraints:
•
2 <= n <= 100•
1 <= edges.length <= min(200, n * (n - 1) / 2)•
edges[i].length == 3•
0 <= a_i < b_i < n•
1 <= weight_i <= 1000• All pairs
(a_i, b_i) are distinct.