2025-08-29
3021. Alice and Bob Playing Flower Game

Topic: Math
Difficulty: Medium

Problem:
Alice and Bob are playing a turn-based game on a field, with two lanes of flowers between them. There are x flowers in the first lane between Alice and Bob, and y flowers in the second lane between them.

Image: https://assets.leetcode.com/uploads/2025/08/27/3021.png

The game proceeds as follows:

1. Alice takes the first turn.
2. In each turn, a player must choose either one of the lane and pick one flower from that side.
3. At the end of the turn, if there are no flowers left at all, the current player captures their opponent and wins the game.

Given two integers, n and m, the task is to compute the number of possible pairs (x, y) that satisfy the conditions:

• Alice must win the game according to the described rules.
• The number of flowers x in the first lane must be in the range [1,n].
• The number of flowers y in the second lane must be in the range [1,m].

Return the number of possible pairs (x, y) that satisfy the conditions mentioned in the statement.

Example 1:

Input: n = 3, m = 2
Output: 3
Explanation: The following pairs satisfy conditions described in the statement: (1,2), (3,2), (2,1).

Example 2:

Input: n = 1, m = 1
Output: 0
Explanation: No pairs satisfy the conditions described in the statement.

Constraints:

• 1 <= n, m <= 10^5

2025-08-30
36. Valid Sudoku

Topic: Array, Hash Table, Matrix
Difficulty: Medium

Problem:
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Image: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

2025-08-31
37. Sudoku Solver

Topic: Array, Hash Table, Backtracking, Matrix
Difficulty: Hard

Problem:
Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Image: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Image: [https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png](https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png)

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

2025-09-01
1792. Maximum Average Pass Ratio

Topic: Array, Greedy, Heap (Priority Queue)
Difficulty: Medium

Problem:
There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [pass_i, total_i]. You know beforehand that in the i^th class, there are total_i total students, but only pass_i number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints:

• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= pass_i <= total_i <= 10^5
• 1 <= extraStudents <= 10^5

2025-09-02
3025. Find the Number of Ways to Place People I

Topic: Array, Math, Geometry, Sorting, Enumeration
Difficulty: Medium

Problem:
You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D plane, where points[i] = [x_i, y_i].

Count the number of pairs of points (A, B), where

• A is on the upper left side of B, and
• there are no other points in the rectangle (or line) they make (including the border).

Return the count.

Example 1:

Input: points = [1,1,2,2,3,3]

Output: 0

Explanation:

Image: https://assets.leetcode.com/uploads/2024/01/04/example1alicebob.png

There is no way to choose A and B so A is on the upper left side of B.

Example 2:

Input: points = [6,2,4,4,2,6]

Output: 2

Explanation:

Image: https://assets.leetcode.com/uploads/2024/06/25/t2.jpg

• The left one is the pair (points[1], points[0]), where points[1] is on the upper left side of points[0] and the rectangle is empty.
• The middle one is the pair (points[2], points[1]), same as the left one it is a valid pair.
• The right one is the pair (points[2], points[0]), where points[2] is on the upper left side of points[0], but points[1] is inside the rectangle so it's not a valid pair.

Example 3:

Input: points = [3,1,1,3,1,1]

Output: 2

Explanation:

Image: https://assets.leetcode.com/uploads/2024/06/25/t3.jpg

• The left one is the pair (points[2], points[0]), where points[2] is on the upper left side of points[0] and there are no other points on the line they form. Note that it is a valid state when the two points form a line.
• The middle one is the pair (points[1], points[2]), it is a valid pair same as the left one.
• The right one is the pair (points[1], points[0]), it is not a valid pair as points[2] is on the border of the rectangle.

Constraints:

• 2 <= n <= 50
• points[i].length == 2
• 0 <= points[i][0], points[i][1] <= 50
• All points[i] are distinct.

2025-09-03
3027. Find the Number of Ways to Place People II

Topic: Array, Math, Geometry, Sorting, Enumeration
Difficulty: Hard

Problem:
You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D-plane, where points[i] = [x_i, y_i].

We define the right direction as positive x-axis (increasing x-coordinate) and the left direction as negative x-axis (decreasing x-coordinate). Similarly, we define the up direction as positive y-axis (increasing y-coordinate) and the down direction as negative y-axis (decreasing y-coordinate)

You have to place n people, including Alice and Bob, at these points such that there is exactly one person at every point. Alice wants to be alone with Bob, so Alice will build a rectangular fence with Alice's position as the upper left corner and Bob's position as the lower right corner of the fence (Note that the fence might not enclose any area, i.e. it can be a line). If any person other than Alice and Bob is either inside the fence or on the fence, Alice will be sad.

Return the number of pairs of points where you can place Alice and Bob, such that Alice does not become sad on building the fence.

Note that Alice can only build a fence with Alice's position as the upper left corner, and Bob's position as the lower right corner. For example, Alice cannot build either of the fences in the picture below with four corners (1, 1), (1, 3), (3, 1), and (3, 3), because:

• With Alice at (3, 3) and Bob at (1, 1), Alice's position is not the upper left corner and Bob's position is not the lower right corner of the fence.
• With Alice at (1, 3) and Bob at (1, 1), Bob's position is not the lower right corner of the fence.

Image: https://assets.leetcode.com/uploads/2024/01/04/example0alicebob-1.png

Example 1:

Image: https://assets.leetcode.com/uploads/2024/01/04/example1alicebob.png

Input: points = [[1,1],[2,2],[3,3]]
Output: 0
Explanation: There is no way to place Alice and Bob such that Alice can build a fence with Alice's position as the upper left corner and Bob's position as the lower right corner. Hence we return 0.

Example 2:

Image: https://assets.leetcode.com/uploads/2024/02/04/example2alicebob.png

Input: points = [[6,2],[4,4],[2,6]]
Output: 2
Explanation: There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (4, 4) and Bob at (6, 2).
- Place Alice at (2, 6) and Bob at (4, 4).
You cannot place Alice at (2, 6) and Bob at (6, 2) because the person at (4, 4) will be inside the fence.

Example 3:

Image: https://assets.leetcode.com/uploads/2024/02/04/example4alicebob.png

Input: points = [[3,1],[1,3],[1,1]]
Output: 2
Explanation: There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (1, 1) and Bob at (3, 1).
- Place Alice at (1, 3) and Bob at (1, 1).
You cannot place Alice at (1, 3) and Bob at (3, 1) because the person at (1, 1) will be on the fence.
Note that it does not matter if the fence encloses any area, the first and second fences in the image are valid.

Constraints:

• 2 <= n <= 1000
• points[i].length == 2
• -10^9 <= points[i][0], points[i][1] <= 10^9
• All points[i] are distinct.

2025-09-04
3516. Find Closest Person

Topic: Math
Difficulty: Easy

Problem:
You are given three integers x, y, and z, representing the positions of three people on a number line:

• x is the position of Person 1.
• y is the position of Person 2.
• z is the position of Person 3, who does not move.

Both Person 1 and Person 2 move toward Person 3 at the same speed.

Determine which person reaches Person 3 first:

• Return 1 if Person 1 arrives first.
• Return 2 if Person 2 arrives first.
• Return 0 if both arrive at the same time.

Return the result accordingly.

Example 1:

Input: x = 2, y = 7, z = 4

Output: 1

Explanation:

• Person 1 is at position 2 and can reach Person 3 (at position 4) in 2 steps.
• Person 2 is at position 7 and can reach Person 3 in 3 steps.

Since Person 1 reaches Person 3 first, the output is 1.

Example 2:

Input: x = 2, y = 5, z = 6

Output: 2

Explanation:

• Person 1 is at position 2 and can reach Person 3 (at position 6) in 4 steps.
• Person 2 is at position 5 and can reach Person 3 in 1 step.

Since Person 2 reaches Person 3 first, the output is 2.

Example 3:

Input: x = 1, y = 5, z = 3

Output: 0

Explanation:

• Person 1 is at position 1 and can reach Person 3 (at position 3) in 2 steps.
• Person 2 is at position 5 and can reach Person 3 in 2 steps.

Since both Person 1 and Person 2 reach Person 3 at the same time, the output is 0.

Constraints:

• 1 <= x, y, z <= 100

2025-09-05
2749. Minimum Operations to Make the Integer Zero

Topic: Bit Manipulation, Brainteaser, Enumeration
Difficulty: Medium

Problem:
You are given two integers num1 and num2.

In one operation, you can choose integer i in the range [0, 60] and subtract 2^i + num2 from num1.

Return the integer denoting the minimum number of operations needed to make num1 equal to 0.

If it is impossible to make num1 equal to 0, return -1.

Example 1:

Input: num1 = 3, num2 = -2
Output: 3
Explanation: We can make 3 equal to 0 with the following operations:
- We choose i = 2 and subtract 2^2 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and subtract 2^2 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and subtract 2^0 + (-2) from -1, (-1) - (1 + (-2)) = 0.
It can be proven, that 3 is the minimum number of operations that we need to perform.

Example 2:

Input: num1 = 5, num2 = 7
Output: -1
Explanation: It can be proven, that it is impossible to make 5 equal to 0 with the given operation.

Constraints:

• 1 <= num1 <= 10^9
• -10^9 <= num2 <= 10^9

2025-09-06
3495. Minimum Operations to Make Array Elements Zero

Topic: Array, Math, Bit Manipulation
Difficulty: Hard

Problem:
You are given a 2D array queries, where queries[i] is of the form [l, r]. Each queries[i] defines an array of integers nums consisting of elements ranging from l to r, both inclusive.

In one operation, you can:

• Select two integers a and b from the array.
• Replace them with floor(a / 4) and floor(b / 4).

Your task is to determine the minimum number of operations required to reduce all elements of the array to zero for each query. Return the sum of the results for all queries.

Example 1:

Input: queries = [1,2,2,4]

Output: 3

Explanation:

For queries[0]:

• The initial array is nums = [1, 2].
• In the first operation, select nums[0] and nums[1]. The array becomes [0, 0].
• The minimum number of operations required is 1.

For queries[1]:

• The initial array is nums = [2, 3, 4].
• In the first operation, select nums[0] and nums[2]. The array becomes [0, 3, 1].
• In the second operation, select nums[1] and nums[2]. The array becomes [0, 0, 0].
• The minimum number of operations required is 2.

The output is 1 + 2 = 3.

Example 2:

Input: queries = [2,6]

Output: 4

Explanation:

For queries[0]:

• The initial array is nums = [2, 3, 4, 5, 6].
• In the first operation, select nums[0] and nums[3]. The array becomes [0, 3, 4, 1, 6].
• In the second operation, select nums[2] and nums[4]. The array becomes [0, 3, 1, 1, 1].
• In the third operation, select nums[1] and nums[2]. The array becomes [0, 0, 0, 1, 1].
• In the fourth operation, select nums[3] and nums[4]. The array becomes [0, 0, 0, 0, 0].
• The minimum number of operations required is 4.

The output is 4.

Constraints:

• 1 <= queries.length <= 10^5
• queries[i].length == 2
• queries[i] == [l, r]
• 1 <= l < r <= 10^9

2025-09-07
1304. Find N Unique Integers Sum up to Zero

Topic: Array, Math
Difficulty: Easy

Problem:
Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]

Example 3:

Input: n = 1
Output: [0]

Constraints:

• 1 <= n <= 1000

2025-09-08
1317. Convert Integer to the Sum of Two No-Zero Integers

Topic: Math
Difficulty: Easy

Problem:
No-Zero integer is a positive integer that does not contain any 0 in its decimal representation.

Given an integer n, return a list of two integers [a, b] where:

• a and b are No-Zero integers.
• a + b = n

The test cases are generated so that there is at least one valid solution. If there are many valid solutions, you can return any of them.

Example 1:

Input: n = 2
Output: [1,1]
Explanation: Let a = 1 and b = 1.
Both a and b are no-zero integers, and a + b = 2 = n.

Example 2:

Input: n = 11
Output: [2,9]
Explanation: Let a = 2 and b = 9.
Both a and b are no-zero integers, and a + b = 11 = n.
Note that there are other valid answers as [8, 3] that can be accepted.

Constraints:

• 2 <= n <= 10^4

2025-09-09
2327. Number of People Aware of a Secret

Topic: Dynamic Programming, Queue, Simulation
Difficulty: Medium

Problem:
On day 1, one person discovers a secret.

You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards.

Given an integer n, return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: n = 6, delay = 2, forget = 4
Output: 5
Explanation:
Day 1: Suppose the first person is named A. (1 person)
Day 2: A is the only person who knows the secret. (1 person)
Day 3: A shares the secret with a new person, B. (2 people)
Day 4: A shares the secret with a new person, C. (3 people)
Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people)
Day 6: B shares the secret with E, and C shares the secret with F. (5 people)

Example 2:

Input: n = 4, delay = 1, forget = 3
Output: 6
Explanation:
Day 1: The first person is named A. (1 person)
Day 2: A shares the secret with B. (2 people)
Day 3: A and B share the secret with 2 new people, C and D. (4 people)
Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)

Constraints:

• 2 <= n <= 1000
• 1 <= delay < forget <= n

2025-09-10
1733. Minimum Number of People to Teach

Topic: Array, Hash Table, Greedy
Difficulty: Medium

Problem:
On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

• There are n languages numbered 1 through n,
• languages[i] is the set of languages the i^​​​​​​th​​​​ user knows, and
• friendships[i] = [u_​​​​​​i​​​, v_​​​​​​i] denotes a friendship between the users u^​​​​​_​​​​​​i​​​​​ and v_i.

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.

Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn't guarantee that x is a friend of z.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
Output: 2
Explanation: Teach the third language to users 1 and 3, yielding two users to teach.

Constraints:

• 2 <= n <= 500
• languages.length == m
• 1 <= m <= 500
• 1 <= languages[i].length <= n
• 1 <= languages[i][j] <= n
• 1 <= u_​​​​​​i < v_​​​​​​i <= languages.length
• 1 <= friendships.length <= 500
• All tuples (u_​​​​​i, v_​​​​​​i) are unique
• languages[i] contains only unique values

2025-09-11
2785. Sort Vowels in a String

Topic: String, Sorting
Difficulty: Medium

Problem:
Given a 0-indexed string s, permute s to get a new string t such that:

• All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
• The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

Return the resulting string.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

Example 1:

Input: s = "lEetcOde"
Output: "lEOtcede"
Explanation: 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

Example 2:

Input: s = "lYmpH"
Output: "lYmpH"
Explanation: There are no vowels in s (all characters in s are consonants), so we return "lYmpH".

Constraints:

• 1 <= s.length <= 10^5
• s consists only of letters of the English alphabet in uppercase and lowercase.

2025-09-12
3227. Vowels Game in a String

Topic: Math, String, Brainteaser, Game Theory
Difficulty: Medium

Problem:
Alice and Bob are playing a game on a string.

You are given a string s, Alice and Bob will take turns playing the following game where Alice starts first:

• On Alice's turn, she has to remove any non-empty substring from s that contains an odd number of vowels.
• On Bob's turn, he has to remove any non-empty substring from s that contains an even number of vowels.

The first player who cannot make a move on their turn loses the game. We assume that both Alice and Bob play optimally.

Return true if Alice wins the game, and false otherwise.

The English vowels are: a, e, i, o, and u.

Example 1:

Input: s = "leetcoder"

Output: true

Explanation:

Alice can win the game as follows:

• Alice plays first, she can delete the underlined substring in s = "leetcoder" which contains 3 vowels. The resulting string is s = "der".
• Bob plays second, he can delete the underlined substring in s = "der" which contains 0 vowels. The resulting string is s = "er".
• Alice plays third, she can delete the whole string s = "er" which contains 1 vowel.
• Bob plays fourth, since the string is empty, there is no valid play for Bob. So Alice wins the game.

Example 2:

Input: s = "bbcd"

Output: false

Explanation:

There is no valid play for Alice in her first turn, so Alice loses the game.

Constraints:

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters.

2025-09-13
3541. Find Most Frequent Vowel and Consonant

Topic: Hash Table, String, Counting
Difficulty: Easy

Problem:
You are given a string s consisting of lowercase English letters ('a' to 'z').

Your task is to:

• Find the vowel (one of 'a', 'e', 'i', 'o', or 'u') with the maximum frequency.
• Find the consonant (all other letters excluding vowels) with the maximum frequency.

Return the sum of the two frequencies.

Note: If multiple vowels or consonants have the same maximum frequency, you may choose any one of them. If there are no vowels or no consonants in the string, consider their frequency as 0.

The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: s = "successes"

Output: 6

Explanation:

• The vowels are: 'u' (frequency 1), 'e' (frequency 2). The maximum frequency is 2.
• The consonants are: 's' (frequency 4), 'c' (frequency 2). The maximum frequency is 4.
• The output is 2 + 4 = 6.

Example 2:

Input: s = "aeiaeia"

Output: 3

Explanation:

• The vowels are: 'a' (frequency 3), 'e' ( frequency 2), 'i' (frequency 2). The maximum frequency is 3.
• There are no consonants in s. Hence, maximum consonant frequency = 0.
• The output is 3 + 0 = 3.

Constraints:

• 1 <= s.length <= 100
• s consists of lowercase English letters only.

2025-09-14
966. Vowel Spellchecker

Topic: Array, Hash Table, String
Difficulty: Medium

Problem:
Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

• Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
• Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
• Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
• Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
• Vowel Errors: If after replacing the vowels ('a', 'e', 'i', 'o', 'u') of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
• Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
• Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
• Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

• When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
• When the query matches a word up to capitlization, you should return the first such match in the wordlist.
• When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
• If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Example 2:

Input: wordlist = ["yellow"], queries = ["YellOw"]
Output: ["yellow"]

Constraints:

• 1 <= wordlist.length, queries.length <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] and queries[i] consist only of only English letters.

2025-09-15
1935. Maximum Number of Words You Can Type

Topic: Hash Table, String
Difficulty: Easy

Problem:
There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: We cannot type "world" because the 'd' key is broken.

Example 2:

Input: text = "leet code", brokenLetters = "lt"
Output: 1
Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3:

Input: text = "leet code", brokenLetters = "e"
Output: 0
Explanation: We cannot type either word because the 'e' key is broken.

Constraints:

• 1 <= text.length <= 10^4
• 0 <= brokenLetters.length <= 26
• text consists of words separated by a single space without any leading or trailing spaces.
• Each word only consists of lowercase English letters.
• brokenLetters consists of distinct lowercase English letters.

2025-09-16
2197. Replace Non-Coprime Numbers in Array

Topic: Array, Math, Stack, Number Theory
Difficulty: Hard

Problem:
You are given an array of integers nums. Perform the following steps:

1. Find any two adjacent numbers in nums that are non-coprime.
2. If no such numbers are found, stop the process.
3. Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
4. Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 10^8.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation: 
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• The test cases are generated such that the values in the final array are less than or equal to 10^8.

2025-09-17
2353. Design a Food Rating System

Topic: Array, Hash Table, String, 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.