2022-08-27
363. Max Sum of Rectangle No Larger Than K
Topic: Array, Binary Search, Matrix, Prefix Sum, Ordered Set
Difficulty: Hard
Problem:
Given an
It is guaranteed that there will be a rectangle with a sum no larger than
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/18/sum-grid.jpg
Example 2:
Constraints:
•
•
•
•
•
Follow up: What if the number of rows is much larger than the number of columns?
363. Max Sum of Rectangle No Larger Than K
Topic: Array, Binary Search, Matrix, Prefix Sum, Ordered Set
Difficulty: Hard
Problem:
Given an
m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.It is guaranteed that there will be a rectangle with a sum no larger than
k.Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/18/sum-grid.jpg
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
Example 2:
Input: matrix = [[2,2,-1]], k = 3
Output: 3
Constraints:
•
m == matrix.length•
n == matrix[i].length•
1 <= m, n <= 100•
-100 <= matrix[i][j] <= 100•
-10^5 <= k <= 10^5Follow up: What if the number of rows is much larger than the number of columns?
2022-08-28
1329. Sort the Matrix Diagonally
Topic: Array, Sorting, Matrix
Difficulty: Medium
Problem:
A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from
Given an
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/21/1482_example_1_2.png
Example 2:
Constraints:
•
•
•
•
1329. Sort the Matrix Diagonally
Topic: Array, Sorting, Matrix
Difficulty: Medium
Problem:
A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from
mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].Given an
m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/21/1482_example_1_2.png
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Example 2:
Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]
Constraints:
•
m == mat.length•
n == mat[i].length•
1 <= m, n <= 100•
1 <= mat[i][j] <= 1002022-08-29
200. Number of Islands
Topic: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix
Difficulty: Medium
Problem:
Given an
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Example 2:
Constraints:
•
•
•
•
200. Number of Islands
Topic: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix
Difficulty: Medium
Problem:
Given an
m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 300•
grid[i][j] is '0' or '1'.2022-08-30
48. Rotate Image
Topic: Array, Math, Matrix
Difficulty: Medium
Problem:
You are given an
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg
Constraints:
•
•
•
48. Rotate Image
Topic: Array, Math, Matrix
Difficulty: Medium
Problem:
You are given an
n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
•
n == matrix.length == matrix[i].length•
1 <= n <= 20•
-1000 <= matrix[i][j] <= 10002022-08-31
417. Pacific Atlantic Water Flow
Topic: Array, Depth-First Search, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
There is an
The island is partitioned into a grid of square cells. You are given an
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates
Example 1:
Image: https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg
Example 2:
Constraints:
•
•
•
•
417. Pacific Atlantic Water Flow
Topic: Array, Depth-First Search, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
There is an
m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.The island is partitioned into a grid of square cells. You are given an
m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates
result where result[i] = [r_i, c_i] denotes that rain water can flow from cell (r_i, c_i) to both the Pacific and Atlantic oceans.Example 1:
Image: https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
•
m == heights.length•
n == heights[r].length•
1 <= m, n <= 200•
0 <= heights[r][c] <= 10^52022-09-01
1448. Count Good Nodes in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree
Return the number of good nodes in the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_2.png
Example 3:
Constraints:
• The number of nodes in the binary tree is in the range
• Each node's value is between
1448. Count Good Nodes in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree
root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.Return the number of good nodes in the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_1.png
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_2.png
Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Constraints:
• The number of nodes in the binary tree is in the range
[1, 10^5].• Each node's value is between
[-10^4, 10^4].2022-09-02
637. Average of Levels in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg1-tree.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg2-tree.jpg
Constraints:
• The number of nodes in the tree is in the range
•
637. Average of Levels in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg1-tree.jpg
Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg2-tree.jpg
Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]
Constraints:
• The number of nodes in the tree is in the range
[1, 10^4].•
-2^31 <= Node.val <= 2^31 - 12022-09-03
967. Numbers With Same Consecutive Differences
Topic: Backtracking, Breadth-First Search
Difficulty: Medium
Problem:
Return all non-negative integers of length
Note that every number in the answer must not have leading zeros. For example,
You may return the answer in any order.
Example 1:
Example 2:
Constraints:
•
•
967. Numbers With Same Consecutive Differences
Topic: Backtracking, Breadth-First Search
Difficulty: Medium
Problem:
Return all non-negative integers of length
n such that the absolute difference between every two consecutive digits is k.Note that every number in the answer must not have leading zeros. For example,
01 has one leading zero and is invalid.You may return the answer in any order.
Example 1:
Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Example 2:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
Constraints:
•
2 <= n <= 9•
0 <= k <= 92022-09-04
987. Vertical Order Traversal of a Binary Tree
Topic: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Hard
Problem:
Given the
For each node at position
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree2.jpg
Example 3:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree3.jpg
Constraints:
• The number of nodes in the tree is in the range
•
987. Vertical Order Traversal of a Binary Tree
Topic: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Hard
Problem:
Given the
root of a binary tree, calculate the vertical order traversal of the binary tree.For each node at position
(row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree1.jpg
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.
Example 2:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree2.jpg
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.
Example 3:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree3.jpg
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
Constraints:
• The number of nodes in the tree is in the range
[1, 1000].•
0 <= Node.val <= 10002022-09-05
429. N-ary Tree Level Order Traversal
Topic: Tree, Breadth-First Search
Difficulty: Medium
Problem:
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
Example 2:
Image: https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
Constraints:
• The height of the n-ary tree is less than or equal to
• The total number of nodes is between
429. N-ary Tree Level Order Traversal
Topic: Tree, Breadth-First Search
Difficulty: Medium
Problem:
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
Example 2:
Image: https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
Constraints:
• The height of the n-ary tree is less than or equal to
1000• The total number of nodes is between
[0, 10^4]2022-09-06
814. Binary Tree Pruning
Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
A subtree of a node
Example 1:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png
Example 2:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png
Example 3:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png
Constraints:
• The number of nodes in the tree is in the range
•
814. Binary Tree Pruning
Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.A subtree of a node
node is node plus every node that is a descendant of node.Example 1:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
Example 2:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
Example 3:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png
Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]
Constraints:
• The number of nodes in the tree is in the range
[1, 200].•
Node.val is either 0 or 1.2022-09-07
606. Construct String from Binary Tree
Topic: String, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg
Constraints:
• The number of nodes in the tree is in the range
•
606. Construct String from Binary Tree
Topic: String, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg
Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Constraints:
• The number of nodes in the tree is in the range
[1, 10^4].•
-1000 <= Node.val <= 10002022-09-08
94. Binary Tree Inorder Traversal
Topic: Stack, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
Example 2:
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
Follow up: Recursive solution is trivial, could you do it iteratively?
94. Binary Tree Inorder Traversal
Topic: Stack, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, return the inorder traversal of its nodes' values.Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
• The number of nodes in the tree is in the range
[0, 100].•
-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
2022-09-09
1996. The Number of Weak Characters in the Game
Topic: Array, Stack, Greedy, Sorting, Monotonic Stack
Difficulty: Medium
Problem:
You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array
A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character
Return the number of weak characters.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
1996. The Number of Weak Characters in the Game
Topic: Array, Stack, Greedy, Sorting, Monotonic Stack
Difficulty: Medium
Problem:
You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array
properties where properties[i] = [attack_i, defense_i] represents the properties of the i^th character in the game.A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character
i is said to be weak if there exists another character j where attack_j > attack_i and defense_j > defense_i.Return the number of weak characters.
Example 1:
Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.
Example 2:
Input: properties = [[2,2],[3,3]]
Output: 1
Explanation: The first character is weak because the second character has a strictly greater attack and defense.
Example 3:
Input: properties = [[1,5],[10,4],[4,3]]
Output: 1
Explanation: The third character is weak because the second character has a strictly greater attack and defense.
Constraints:
•
2 <= properties.length <= 10^5•
properties[i].length == 2•
1 <= attack_i, defense_i <= 10^52022-09-10
188. Best Time to Buy and Sell Stock IV
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are given an integer array
Find the maximum profit you can achieve. You may complete at most
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Example 2:
Constraints:
•
•
•
188. Best Time to Buy and Sell Stock IV
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are given an integer array
prices where prices[i] is the price of a given stock on the i^th day, and an integer k.Find the maximum profit you can achieve. You may complete at most
k transactions.Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
•
0 <= k <= 100•
0 <= prices.length <= 1000•
0 <= prices[i] <= 10002022-09-11
1383. Maximum Performance of a Team
Topic: Array, Greedy, Sorting, Heap (Priority Queue)
Difficulty: Hard
Problem:
You are given two integers
Choose at most
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
1383. Maximum Performance of a Team
Topic: Array, Greedy, Sorting, Heap (Priority Queue)
Difficulty: Hard
Problem:
You are given two integers
n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the i^th engineer respectively.Choose at most
k different engineers out of the n engineers to form a team with the maximum performance.The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
10^9 + 7.Example 1:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
Example 2:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
Example 3:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72
Constraints:
•
1 <= k <= n <= 10^5•
speed.length == n•
efficiency.length == n•
1 <= speed[i] <= 10^5•
1 <= efficiency[i] <= 10^82022-09-12
948. Bag of Tokens
Topic: Array, Two Pointers, Greedy, Sorting
Difficulty: Medium
Problem:
You have an initial power of
Your goal is to maximize your total score by potentially playing each token in one of two ways:
• If your current power is at least
• If your current score is at least
Each token may be played at most once and in any order. You do not have to play all the tokens.
Return the largest possible score you can achieve after playing any number of tokens.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
948. Bag of Tokens
Topic: Array, Two Pointers, Greedy, Sorting
Difficulty: Medium
Problem:
You have an initial power of
power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the i^th token (0-indexed).Your goal is to maximize your total score by potentially playing each token in one of two ways:
• If your current power is at least
tokens[i], you may play the i^th token face up, losing tokens[i] power and gaining 1 score.• If your current score is at least
1, you may play the i^th token face down, gaining tokens[i] power and losing 1 score.Each token may be played at most once and in any order. You do not have to play all the tokens.
Return the largest possible score you can achieve after playing any number of tokens.
Example 1:
Input: tokens = [100], power = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.
Example 2:
Input: tokens = [100,200], power = 150
Output: 1
Explanation: Play the 0^th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1^st token since you cannot play it face up to add to your score.
Example 3:
Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0^th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3^rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1^st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2^nd token (300) face up, your power becomes 0 and score becomes 2.
Constraints:
•
0 <= tokens.length <= 1000•
0 <= tokens[i], power < 10^42022-09-13
393. UTF-8 Validation
Topic: Array, Bit Manipulation
Difficulty: Medium
Problem:
Given an integer array
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
1. For a 1-byte character, the first bit is a
2. For an n-bytes character, the first
This is how the UTF-8 encoding would work:
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
Example 2:
Constraints:
•
•
393. UTF-8 Validation
Topic: Array, Bit Manipulation
Difficulty: Medium
Problem:
Given an integer array
data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
1. For a 1-byte character, the first bit is a
0, followed by its Unicode code.2. For an n-bytes character, the first
n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.This is how the UTF-8 encoding would work:
Number of Bytes | UTF-8 Octet Sequence
| (binary)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x denotes a bit in the binary form of a byte that may be either 0 or 1.Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.
Constraints:
•
1 <= data.length <= 2 * 10^4•
0 <= data[i] <= 2552022-09-14
1457. Pseudo-Palindromic Paths in a Binary Tree
Topic: Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/05/06/palindromic_paths_1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/05/07/palindromic_paths_2.png
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
1457. Pseudo-Palindromic Paths in a Binary Tree
Topic: Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/05/06/palindromic_paths_1.png
Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 2:
Image: https://assets.leetcode.com/uploads/2020/05/07/palindromic_paths_2.png
Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 3:
Input: root = [9]
Output: 1
Constraints:
• The number of nodes in the tree is in the range
[1, 10^5].•
1 <= Node.val <= 92022-09-15
2007. Find Original Array From Doubled Array
Topic: Array, Hash Table, Greedy, Sorting
Difficulty: Medium
Problem:
An integer array
Given an array
Example 1:
Example 2:
Example 3:
Constraints:
•
•
2007. Find Original Array From Doubled Array
Topic: Array, Hash Table, Greedy, Sorting
Difficulty: Medium
Problem:
An integer array
original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.Given an array
changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.Example 1:
Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].
Example 2:
Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.
Example 3:
Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.
Constraints:
•
1 <= changed.length <= 10^5•
0 <= changed[i] <= 10^5