2023-12-10
867. Transpose Matrix
Topic: Array, Matrix, Simulation
Difficulty: Easy
Problem:
Given a 2D integer array
The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.
Image: https://assets.leetcode.com/uploads/2021/02/10/hint_transpose.png
Example 1:
Example 2:
Constraints:
•
•
•
•
•
867. Transpose Matrix
Topic: Array, Matrix, Simulation
Difficulty: Easy
Problem:
Given a 2D integer array
matrix, return the transpose of matrix.The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.
Image: https://assets.leetcode.com/uploads/2021/02/10/hint_transpose.png
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
Example 2:
Input: matrix = [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]
Constraints:
•
m == matrix.length•
n == matrix[i].length•
1 <= m, n <= 1000•
1 <= m * n <= 10^5•
-10^9 <= matrix[i][j] <= 10^92023-12-11
1287. Element Appearing More Than 25% In Sorted Array
Topic: Array
Difficulty: Easy
Problem:
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.
Example 1:
Example 2:
Constraints:
•
•
1287. Element Appearing More Than 25% In Sorted Array
Topic: Array
Difficulty: Easy
Problem:
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.
Example 1:
Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6
Example 2:
Input: arr = [1,1]
Output: 1
Constraints:
•
1 <= arr.length <= 10^4•
0 <= arr[i] <= 10^52023-12-12
1464. Maximum Product of Two Elements in an Array
Topic: Array, Sorting, Heap (Priority Queue)
Difficulty: Easy
Problem:
Given the array of integers
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1464. Maximum Product of Two Elements in an Array
Topic: Array, Sorting, Heap (Priority Queue)
Difficulty: Easy
Problem:
Given the array of integers
nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).Example 1:
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.
Example 2:
Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.
Example 3:
Input: nums = [3,7]
Output: 12
Constraints:
•
2 <= nums.length <= 500•
1 <= nums[i] <= 10^32023-12-13
1582. Special Positions in a Binary Matrix
Topic: Array, Matrix
Difficulty: Easy
Problem:
Given an
A position
Example 1:
Image: https://assets.leetcode.com/uploads/2021/12/23/special1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/12/24/special-grid.jpg
Constraints:
•
•
•
•
1582. Special Positions in a Binary Matrix
Topic: Array, Matrix
Difficulty: Easy
Problem:
Given an
m x n binary matrix mat, return the number of special positions in mat.A position
(i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).Example 1:
Image: https://assets.leetcode.com/uploads/2021/12/23/special1.jpg
Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.
Example 2:
Image: https://assets.leetcode.com/uploads/2021/12/24/special-grid.jpg
Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: (0, 0), (1, 1) and (2, 2) are special positions.
Constraints:
•
m == mat.length•
n == mat[i].length•
1 <= m, n <= 100•
mat[i][j] is either 0 or 1.2023-12-14
2482. Difference Between Ones and Zeros in Row and Column
Topic: Array, Matrix, Simulation
Difficulty: Medium
Problem:
You are given a 0-indexed
A 0-indexed
• Let the number of ones in the
• Let the number of ones in the
• Let the number of zeros in the
• Let the number of zeros in the
•
Return the difference matrix
Example 1:
Image: https://assets.leetcode.com/uploads/2022/11/06/image-20221106171729-5.png
Example 2:
Image: https://assets.leetcode.com/uploads/2022/11/06/image-20221106171747-6.png
Constraints:
•
•
•
•
•
2482. Difference Between Ones and Zeros in Row and Column
Topic: Array, Matrix, Simulation
Difficulty: Medium
Problem:
You are given a 0-indexed
m x n binary matrix grid.A 0-indexed
m x n difference matrix diff is created with the following procedure:• Let the number of ones in the
i^th row be onesRow_i.• Let the number of ones in the
j^th column be onesCol_j.• Let the number of zeros in the
i^th row be zerosRow_i.• Let the number of zeros in the
j^th column be zerosCol_j.•
diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_jReturn the difference matrix
diff.Example 1:
Image: https://assets.leetcode.com/uploads/2022/11/06/image-20221106171729-5.png
Input: grid = [[0,1,1],[1,0,1],[0,0,1]]
Output: [[0,0,4],[0,0,4],[-2,-2,2]]
Explanation:
- diff[0][0] = onesRow_0 + onesCol_0 - zerosRow_0 - zerosCol_0 = 2 + 1 - 1 - 2 = 0
- diff[0][1] = onesRow_0 + onesCol_1 - zerosRow_0 - zerosCol_1 = 2 + 1 - 1 - 2 = 0
- diff[0][2] = onesRow_0 + onesCol_2 - zerosRow_0 - zerosCol_2 = 2 + 3 - 1 - 0 = 4
- diff[1][0] = onesRow_1 + onesCol_0 - zerosRow_1 - zerosCol_0 = 2 + 1 - 1 - 2 = 0
- diff[1][1] = onesRow_1 + onesCol_1 - zerosRow_1 - zerosCol_1 = 2 + 1 - 1 - 2 = 0
- diff[1][2] = onesRow_1 + onesCol_2 - zerosRow_1 - zerosCol_2 = 2 + 3 - 1 - 0 = 4
- diff[2][0] = onesRow_2 + onesCol_0 - zerosRow_2 - zerosCol_0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow_2 + onesCol_1 - zerosRow_2 - zerosCol_1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow_2 + onesCol_2 - zerosRow_2 - zerosCol_2 = 1 + 3 - 2 - 0 = 2
Example 2:
Image: https://assets.leetcode.com/uploads/2022/11/06/image-20221106171747-6.png
Input: grid = [[1,1,1],[1,1,1]]
Output: [[5,5,5],[5,5,5]]
Explanation:
- diff[0][0] = onesRow_0 + onesCol_0 - zerosRow_0 - zerosCol_0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow_0 + onesCol_1 - zerosRow_0 - zerosCol_1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow_0 + onesCol_2 - zerosRow_0 - zerosCol_2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow_1 + onesCol_0 - zerosRow_1 - zerosCol_0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow_1 + onesCol_1 - zerosRow_1 - zerosCol_1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow_1 + onesCol_2 - zerosRow_1 - zerosCol_2 = 3 + 2 - 0 - 0 = 5
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 10^5•
1 <= m * n <= 10^5•
grid[i][j] is either 0 or 1.2023-12-15
1436. Destination City
Topic: Hash Table, String
Difficulty: Easy
Problem:
You are given the array
It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
• All strings consist of lowercase and uppercase English letters and the space character.
1436. Destination City
Topic: Hash Table, String
Difficulty: Easy
Problem:
You are given the array
paths, where paths[i] = [cityA_i, cityB_i] means there exists a direct path going from cityA_i to cityB_i. Return the destination city, that is, the city without any path outgoing to another city.It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.
Example 1:
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".
Example 2:
Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are:
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
Clearly the destination city is "A".
Example 3:
Input: paths = [["A","Z"]]
Output: "Z"
Constraints:
•
1 <= paths.length <= 100•
paths[i].length == 2•
1 <= cityA_i.length, cityB_i.length <= 10•
cityA_i != cityB_i• All strings consist of lowercase and uppercase English letters and the space character.
2023-12-16
242. Valid Anagram
Topic: Hash Table, String, Sorting
Difficulty: Easy
Problem:
Given two strings
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Example 2:
Constraints:
•
•
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
242. Valid Anagram
Topic: Hash Table, String, Sorting
Difficulty: Easy
Problem:
Given two strings
s and t, return true if t is an anagram of s, and false otherwise.An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
•
1 <= s.length, t.length <= 5 * 10^4•
s and t consist of lowercase English letters.Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
2023-12-17
2353. Design a Food Rating System
Topic: Hash Table, Design, Heap (Priority Queue), Ordered Set
Difficulty: Medium
Problem:
Design a food rating system that can do the following:
• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.
Implement the
•
•
•
•
•
•
Note that a string
Example 1:
Constraints:
•
•
•
•
•
• All the strings in
•
•
• At most
2353. Design a Food Rating System
Topic: Hash Table, Design, Heap (Priority Queue), Ordered Set
Difficulty: Medium
Problem:
Design a food rating system that can do the following:
• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.
Implement the
FoodRatings class:•
FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.•
foods[i] is the name of the i^th food,•
cuisines[i] is the type of cuisine of the i^th food, and•
ratings[i] is the initial rating of the i^th food.•
void changeRating(String food, int newRating) Changes the rating of the food item with the name food.•
String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.Note that a string
x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.Example 1:
Input
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
Output
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]
Explanation
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // return "kimchi"
// "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
// "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
// "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
// Both "sushi" and "ramen" have a rating of 16.
// However, "ramen" is lexicographically smaller than "sushi".
Constraints:
•
1 <= n <= 2 * 10^4•
n == foods.length == cuisines.length == ratings.length•
1 <= foods[i].length, cuisines[i].length <= 10•
foods[i], cuisines[i] consist of lowercase English letters.•
1 <= ratings[i] <= 10^8• All the strings in
foods are distinct.•
food will be the name of a food item in the system across all calls to changeRating.•
cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.• At most
2 * 10^4 calls in total will be made to changeRating and highestRated.2023-12-18
1913. Maximum Product Difference Between Two Pairs
Topic: Array, Sorting
Difficulty: Easy
Problem:
The product difference between two pairs
• For example, the product difference between
Given an integer array
Return the maximum such product difference.
Example 1:
Example 2:
Constraints:
•
•
1913. Maximum Product Difference Between Two Pairs
Topic: Array, Sorting
Difficulty: Easy
Problem:
The product difference between two pairs
(a, b) and (c, d) is defined as (a * b) - (c * d).• For example, the product difference between
(5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.Given an integer array
nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.Return the maximum such product difference.
Example 1:
Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.
Example 2:
Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.
Constraints:
•
4 <= nums.length <= 10^4•
1 <= nums[i] <= 10^42023-12-19
661. Image Smoother
Topic: Array, Matrix
Difficulty: Easy
Problem:
An image smoother is a filter of the size
Image: https://assets.leetcode.com/uploads/2021/05/03/smoother-grid.jpg
Given an
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/smooth-grid.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/smooth2-grid.jpg
Constraints:
•
•
•
•
661. Image Smoother
Topic: Array, Matrix
Difficulty: Easy
Problem:
An image smoother is a filter of the size
3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).Image: https://assets.leetcode.com/uploads/2021/05/03/smoother-grid.jpg
Given an
m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/smooth-grid.jpg
Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/smooth2-grid.jpg
Input: img = [[100,200,100],[200,50,200],[100,200,100]]
Output: [[137,141,137],[141,138,141],[137,141,137]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138
Constraints:
•
m == img.length•
n == img[i].length•
1 <= m, n <= 200•
0 <= img[i][j] <= 2552023-12-20
2706. Buy Two Chocolates
Topic: Array, Sorting
Difficulty: Easy
Problem:
You are given an integer array
You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return
Example 1:
Example 2:
Constraints:
•
•
•
2706. Buy Two Chocolates
Topic: Array, Sorting
Difficulty: Easy
Problem:
You are given an integer array
prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return
money. Note that the leftover must be non-negative.Example 1:
Input: prices = [1,2,2], money = 3
Output: 0
Explanation: Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.
Example 2:
Input: prices = [3,2,3], money = 3
Output: 3
Explanation: You cannot buy 2 chocolates without going in debt, so we return 3.
Constraints:
•
2 <= prices.length <= 50•
1 <= prices[i] <= 100•
1 <= money <= 1002023-12-21
1637. Widest Vertical Area Between Two Points Containing No Points
Topic: Array, Sorting
Difficulty: Medium
Problem:
Given
A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.
Note that points on the edge of a vertical area are not considered included in the area.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/19/points3.png
Example 2:
Constraints:
•
•
•
•
1637. Widest Vertical Area Between Two Points Containing No Points
Topic: Array, Sorting
Difficulty: Medium
Problem:
Given
n points on a 2D plane where points[i] = [x_i, y_i], Return the widest vertical area between two points such that no points are inside the area.A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.
Note that points on the edge of a vertical area are not considered included in the area.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/19/points3.png
Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.
Example 2:
Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3
Constraints:
•
n == points.length•
2 <= n <= 10^5•
points[i].length == 2•
0 <= x_i, y_i <= 10^92023-12-22
1422. Maximum Score After Splitting a String
Topic: String
Difficulty: Easy
Problem:
Given a string
The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.
Example 1:
Example 2:
Example 3:
Constraints:
•
• The string
1422. Maximum Score After Splitting a String
Topic: String
Difficulty: Easy
Problem:
Given a string
s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.
Example 1:
Input: s = "011101"
Output: 5
Explanation:
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5
left = "01" and right = "1101", score = 1 + 3 = 4
left = "011" and right = "101", score = 1 + 2 = 3
left = "0111" and right = "01", score = 1 + 1 = 2
left = "01110" and right = "1", score = 2 + 1 = 3
Example 2:
Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5
Example 3:
Input: s = "1111"
Output: 3
Constraints:
•
2 <= s.length <= 500• The string
s consists of characters '0' and '1' only.2023-12-23
1496. Path Crossing
Topic: Hash Table, String
Difficulty: Easy
Problem:
Given a string
Return
Example 1:
Image: https://assets.leetcode.com/uploads/2020/06/10/screen-shot-2020-06-10-at-123929-pm.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/06/10/screen-shot-2020-06-10-at-123843-pm.png
Constraints:
•
•
1496. Path Crossing
Topic: Hash Table, String
Difficulty: Easy
Problem:
Given a string
path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.Return
true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.Example 1:
Image: https://assets.leetcode.com/uploads/2020/06/10/screen-shot-2020-06-10-at-123929-pm.png
Input: path = "NES"
Output: false
Explanation: Notice that the path doesn't cross any point more than once.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/06/10/screen-shot-2020-06-10-at-123843-pm.png
Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.
Constraints:
•
1 <= path.length <= 10^4•
path[i] is either 'N', 'S', 'E', or 'W'.2023-12-24
1758. Minimum Changes To Make Alternating Binary String
Topic: String
Difficulty: Easy
Problem:
You are given a string
The string is called alternating if no two adjacent characters are equal. For example, the string
Return the minimum number of operations needed to make
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1758. Minimum Changes To Make Alternating Binary String
Topic: String
Difficulty: Easy
Problem:
You are given a string
s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.The string is called alternating if no two adjacent characters are equal. For example, the string
"010" is alternating, while the string "0100" is not.Return the minimum number of operations needed to make
s alternating.Example 1:
Input: s = "0100"
Output: 1
Explanation: If you change the last character to '1', s will be "0101", which is alternating.
Example 2:
Input: s = "10"
Output: 0
Explanation: s is already alternating.
Example 3:
Input: s = "1111"
Output: 2
Explanation: You need two operations to reach "0101" or "1010".
Constraints:
•
1 <= s.length <= 10^4•
s[i] is either '0' or '1'.2023-12-25
91. Decode Ways
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
A message containing letters from
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example,
•
•
Note that the grouping
Given a string
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
91. Decode Ways
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
A message containing letters from
A-Z can be encoded into numbers using the following mapping:'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example,
"11106" can be mapped into:•
"AAJF" with the grouping (1 1 10 6)•
"KJF" with the grouping (11 10 6)Note that the grouping
(1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".Given a string
s containing only digits, return the number of ways to decode it.The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Constraints:
•
1 <= s.length <= 100•
s contains only digits and may contain leading zero(s).2023-12-26
1155. Number of Dice Rolls With Target Sum
Topic: Dynamic Programming
Difficulty: Medium
Problem:
You have
Given three integers
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1155. Number of Dice Rolls With Target Sum
Topic: Dynamic Programming
Difficulty: Medium
Problem:
You have
n dice, and each die has k faces numbered from 1 to k.Given three integers
n, k, and target, return the number of possible ways (out of the k^n total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 10^9 + 7.Example 1:
Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.
Example 2:
Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
Example 3:
Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 10^9 + 7.
Constraints:
•
1 <= n, k <= 30•
1 <= target <= 10002023-12-27
1578. Minimum Time to Make Rope Colorful
Topic: Array, String, Dynamic Programming, Greedy
Difficulty: Medium
Problem:
Alice has
Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array
Return the minimum time Bob needs to make the rope colorful.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/12/13/ballon1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/12/13/balloon2.jpg
Example 3:
Image: https://assets.leetcode.com/uploads/2021/12/13/balloon3.jpg
Constraints:
•
•
•
•
1578. Minimum Time to Make Rope Colorful
Topic: Array, String, Dynamic Programming, Greedy
Difficulty: Medium
Problem:
Alice has
n balloons arranged on a rope. You are given a 0-indexed string colors where colors[i] is the color of the i^th balloon.Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array
neededTime where neededTime[i] is the time (in seconds) that Bob needs to remove the i^th balloon from the rope.Return the minimum time Bob needs to make the rope colorful.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/12/13/ballon1.jpg
Input: colors = "abaac", neededTime = [1,2,3,4,5]
Output: 3
Explanation: In the above image, 'a' is blue, 'b' is red, and 'c' is green.
Bob can remove the blue balloon at index 2. This takes 3 seconds.
There are no longer two consecutive balloons of the same color. Total time = 3.
Example 2:
Image: https://assets.leetcode.com/uploads/2021/12/13/balloon2.jpg
Input: colors = "abc", neededTime = [1,2,3]
Output: 0
Explanation: The rope is already colorful. Bob does not need to remove any balloons from the rope.
Example 3:
Image: https://assets.leetcode.com/uploads/2021/12/13/balloon3.jpg
Input: colors = "aabaa", neededTime = [1,2,3,4,1]
Output: 2
Explanation: Bob will remove the ballons at indices 0 and 4. Each ballon takes 1 second to remove.
There are no longer two consecutive balloons of the same color. Total time = 1 + 1 = 2.
Constraints:
•
n == colors.length == neededTime.length•
1 <= n <= 10^5•
1 <= neededTime[i] <= 10^4•
colors contains only lowercase English letters.2023-12-29
1335. Minimum Difficulty of a Job Schedule
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You want to schedule a list of jobs in
You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the
You are given an integer array
Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/16/untitled.png
Example 2:
Example 3:
Constraints:
•
•
•
1335. Minimum Difficulty of a Job Schedule
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You want to schedule a list of jobs in
d days. Jobs are dependent (i.e To work on the i^th job, you have to finish all the jobs j where 0 <= j < i).You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the
d days. The difficulty of a day is the maximum difficulty of a job done on that day.You are given an integer array
jobDifficulty and an integer d. The difficulty of the i^th job is jobDifficulty[i].Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return
-1.Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/16/untitled.png
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
Example 2:
Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
Example 3:
Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.
Constraints:
•
1 <= jobDifficulty.length <= 300•
0 <= jobDifficulty[i] <= 1000•
1 <= d <= 102023-12-30
1897. Redistribute Characters to Make All Strings Equal
Topic: Hash Table, String, Counting
Difficulty: Easy
Problem:
You are given an array of strings
In one operation, pick two distinct indices
Return
Example 1:
Example 2:
Constraints:
•
•
•
1897. Redistribute Characters to Make All Strings Equal
Topic: Hash Table, String, Counting
Difficulty: Easy
Problem:
You are given an array of strings
words (0-indexed).In one operation, pick two distinct indices
i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].Return
true if you can make every string in words equal using any number of operations, and false otherwise.Example 1:
Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Move the first 'a' in words[1] to the front of words[2],
to make words[1] = "abc" and words[2] = "abc".
All the strings are now equal to "abc", so return true.
Example 2:
Input: words = ["ab","a"]
Output: false
Explanation: It is impossible to make all the strings equal using the operation.
Constraints:
•
1 <= words.length <= 100•
1 <= words[i].length <= 100•
words[i] consists of lowercase English letters.2023-12-31
1624. Largest Substring Between Two Equal Characters
Topic: Hash Table, String
Difficulty: Easy
Problem:
Given a string
A substring is a contiguous sequence of characters within a string.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1624. Largest Substring Between Two Equal Characters
Topic: Hash Table, String
Difficulty: Easy
Problem:
Given a string
s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.
Example 2:
Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".
Example 3:
Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.
Constraints:
•
1 <= s.length <= 300•
s contains only lowercase English letters.