2023-12-01
1662. Check If Two String Arrays are Equivalent
Topic: Array, String
Difficulty: Easy
Problem:
Given two string arrays
A string is represented by an array if the array elements concatenated in order forms the string.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
1662. Check If Two String Arrays are Equivalent
Topic: Array, String
Difficulty: Easy
Problem:
Given two string arrays
word1 and word2, return true if the two arrays represent the same string, and false otherwise.A string is represented by an array if the array elements concatenated in order forms the string.
Example 1:
Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.
Example 2:
Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false
Example 3:
Input: word1 = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true
Constraints:
•
1 <= word1.length, word2.length <= 10^3•
1 <= word1[i].length, word2[i].length <= 10^3•
1 <= sum(word1[i].length), sum(word2[i].length) <= 10^3•
word1[i] and word2[i] consist of lowercase letters.2023-12-02
1160. Find Words That Can Be Formed by Characters
Topic: Array, Hash Table, String
Difficulty: Easy
Problem:
You are given an array of strings
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
Example 1:
Example 2:
Constraints:
•
•
•
1160. Find Words That Can Be Formed by Characters
Topic: Array, Hash Table, String
Difficulty: Easy
Problem:
You are given an array of strings
words and a string chars.A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
Constraints:
•
1 <= words.length <= 1000•
1 <= words[i].length, chars.length <= 100•
words[i] and chars consist of lowercase English letters.2023-12-03
1266. Minimum Time Visiting All Points
Topic: Array, Math, Geometry
Difficulty: Easy
Problem:
On a 2D plane, there are
You can move according to these rules:
• In
• move vertically by one unit,
• move horizontally by one unit, or
• move diagonally
• You have to visit the points in the same order as they appear in the array.
• You are allowed to pass through points that appear later in the order, but these do not count as visits.
Example 1:
Image: https://assets.leetcode.com/uploads/2019/11/14/1626_example_1.PNG
Example 2:
Constraints:
•
•
•
•
1266. Minimum Time Visiting All Points
Topic: Array, Math, Geometry
Difficulty: Easy
Problem:
On a 2D plane, there are
n points with integer coordinates points[i] = [x_i, y_i]. Return the minimum time in seconds to visit all the points in the order given by points.You can move according to these rules:
• In
1 second, you can either:• move vertically by one unit,
• move horizontally by one unit, or
• move diagonally
sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).• You have to visit the points in the same order as they appear in the array.
• You are allowed to pass through points that appear later in the order, but these do not count as visits.
Example 1:
Image: https://assets.leetcode.com/uploads/2019/11/14/1626_example_1.PNG
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds
Example 2:
Input: points = [[3,2],[-2,2]]
Output: 5
Constraints:
•
points.length == n•
1 <= n <= 100•
points[i].length == 2•
-1000 <= points[i][0], points[i][1] <= 10002023-12-04
2264. Largest 3-Same-Digit Number in String
Topic: String
Difficulty: Easy
Problem:
You are given a string
• It is a substring of
• It consists of only one unique digit.
Return the maximum good integer as a string or an empty string
Note:
• A substring is a contiguous sequence of characters within a string.
• There may be leading zeroes in
Example 1:
Example 2:
Example 3:
Constraints:
•
•
2264. Largest 3-Same-Digit Number in String
Topic: String
Difficulty: Easy
Problem:
You are given a string
num representing a large integer. An integer is good if it meets the following conditions:• It is a substring of
num with length 3.• It consists of only one unique digit.
Return the maximum good integer as a string or an empty string
"" if no such integer exists.Note:
• A substring is a contiguous sequence of characters within a string.
• There may be leading zeroes in
num or a good integer.Example 1:
Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".
Example 2:
Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.
Example 3:
Input: num = "42352338"
Output: ""
Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.
Constraints:
•
3 <= num.length <= 1000•
num only consists of digits.2023-12-05
1688. Count of Matches in Tournament
Topic: Math, Simulation
Difficulty: Easy
Problem:
You are given an integer
• If the current number of teams is even, each team gets paired with another team. A total of
• If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of
Return the number of matches played in the tournament until a winner is decided.
Example 1:
Example 2:
Constraints:
•
1688. Count of Matches in Tournament
Topic: Math, Simulation
Difficulty: Easy
Problem:
You are given an integer
n, the number of teams in a tournament that has strange rules:• If the current number of teams is even, each team gets paired with another team. A total of
n / 2 matches are played, and n / 2 teams advance to the next round.• If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of
(n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.Return the number of matches played in the tournament until a winner is decided.
Example 1:
Input: n = 7
Output: 6
Explanation: Details of the tournament:
- 1st Round: Teams = 7, Matches = 3, and 4 teams advance.
- 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 3 + 2 + 1 = 6.
Example 2:
Input: n = 14
Output: 13
Explanation: Details of the tournament:
- 1st Round: Teams = 14, Matches = 7, and 7 teams advance.
- 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.
- 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 7 + 3 + 2 + 1 = 13.
Constraints:
•
1 <= n <= 200Leetcode Question of Today pinned «End of Maintenance Notice Dear subscribers, I regret to inform you that I have made the decision to discontinue the maintenance of this bot. This means that I will no longer provide updates on LeetCode's "Question of Today". The decision is primarily based…»
2023-12-06
1716. Calculate Money in Leetcode Bank
Topic: Math
Difficulty: Easy
Problem:
Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.
He starts by putting in
Given
Example 1:
Example 2:
Example 3:
Constraints:
•
1716. Calculate Money in Leetcode Bank
Topic: Math
Difficulty: Easy
Problem:
Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.
He starts by putting in
$1 on Monday, the first day. Every day from Tuesday to Sunday, he will put in $1 more than the day before. On every subsequent Monday, he will put in $1 more than the previous Monday. Given
n, return the total amount of money he will have in the Leetcode bank at the end of the n^th day.Example 1:
Input: n = 4
Output: 10
Explanation: After the 4^th day, the total is 1 + 2 + 3 + 4 = 10.
Example 2:
Input: n = 10
Output: 37
Explanation: After the 10^th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2^nd Monday, Hercy only puts in $2.
Example 3:
Input: n = 20
Output: 96
Explanation: After the 20^th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.
Constraints:
•
1 <= n <= 10002023-12-07
1903. Largest Odd Number in String
Topic: Math, String, Greedy
Difficulty: Easy
Problem:
You are given a string
A substring is a contiguous sequence of characters within a string.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1903. Largest Odd Number in String
Topic: Math, String, Greedy
Difficulty: Easy
Problem:
You are given a string
num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.A substring is a contiguous sequence of characters within a string.
Example 1:
Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.
Example 2:
Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".
Example 3:
Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.
Constraints:
•
1 <= num.length <= 10^5•
num only consists of digits and does not contain any leading zeros.2023-12-08
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 <= 10002023-12-09
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?
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 <= 100