2023-11-30
1611. Minimum One Bit Operations to Make Integers Zero

Topic: Dynamic Programming, Bit Manipulation, Memoization
Difficulty: Hard

Problem:
Given an integer n, you must transform it into 0 using the following operations any number of times:

• Change the rightmost (0^th) bit in the binary representation of n.
• Change the i^th bit in the binary representation of n if the (i-1)^th bit is set to 1 and the (i-2)^th through 0^th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2^nd operation since the 0^th bit is 1.
"01" -> "00" with the 1^st operation.

Example 2:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2^nd operation since the 1^st bit is 1 and 0^th through 0^th bits are 0.
"010" -> "011" with the 1^st operation.
"011" -> "001" with the 2^nd operation since the 0^th bit is 1.
"001" -> "000" with the 1^st operation.

Constraints:

• 0 <= n <= 10^9

2023-12-01
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 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 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] <= 1000

2023-12-04
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 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 <= 200

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 $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 <= 1000

2023-12-07
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 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 <= 1000

2023-12-09
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 <= 100

Follow 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 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^9

2023-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:

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^5

2023-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 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^3

2023-12-13
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 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_j

Return 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 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 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 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 (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^4