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.

2025-09-18
3408. Design Task Manager

Topic: Hash Table, Design, Heap (Priority Queue), Ordered Set
Difficulty: Medium

Problem:
There is a task management system that allows users to manage their tasks, each associated with a priority. The system should efficiently handle adding, modifying, executing, and removing tasks.

Implement the TaskManager class:

• TaskManager(vector<vector<int>>& tasks) initializes the task manager with a list of user-task-priority triples. Each element in the input list is of the form [userId, taskId, priority], which adds a task to the specified user with the given priority.
• void add(int userId, int taskId, int priority) adds a task with the specified taskId and priority to the user with userId. It is guaranteed that taskId does not exist in the system.
• void edit(int taskId, int newPriority) updates the priority of the existing taskId to newPriority. It is guaranteed that taskId exists in the system.
• void rmv(int taskId) removes the task identified by taskId from the system. It is guaranteed that taskId exists in the system.
• int execTop() executes the task with the highest priority across all users. If there are multiple tasks with the same highest priority, execute the one with the highest taskId. After executing, the taskId is removed from the system. Return the userId associated with the executed task. If no tasks are available, return -1.

Note that a user may be assigned multiple tasks.

Example 1:

Input:

"TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"

[[[1, 101, 10, 2, 102, 20, 3, 103, 15]], 4, 104, 5, 102, 8, , 101, 5, 105, 15, ]

Output:

null, null, null, 3, null, null, 5

Explanation

TaskManager taskManager = new TaskManager([1, 101, 10, 2, 102, 20, 3, 103, 15]); // Initializes with three tasks for Users 1, 2, and 3.

taskManager.add(4, 104, 5); // Adds task 104 with priority 5 for User 4.

taskManager.edit(102, 8); // Updates priority of task 102 to 8.

taskManager.execTop(); // return 3. Executes task 103 for User 3.

taskManager.rmv(101); // Removes task 101 from the system.

taskManager.add(5, 105, 15); // Adds task 105 with priority 15 for User 5.

taskManager.execTop(); // return 5. Executes task 105 for User 5.

Constraints:

• 1 <= tasks.length <= 10^5
• 0 <= userId <= 10^5
• 0 <= taskId <= 10^5
• 0 <= priority <= 10^9
• 0 <= newPriority <= 10^9
• At most 2 * 10^5 calls will be made in total to add, edit, rmv, and execTop methods.
• The input is generated such that taskId will be valid.

2025-09-19
3484. Design Spreadsheet

Topic: Array, Hash Table, String, Design, Matrix
Difficulty: Medium

Problem:
A spreadsheet is a grid with 26 columns (labeled from 'A' to 'Z') and a given number of rows. Each cell in the spreadsheet can hold an integer value between 0 and 10^5.

Implement the Spreadsheet class:

• Spreadsheet(int rows) Initializes a spreadsheet with 26 columns (labeled 'A' to 'Z') and the specified number of rows. All cells are initially set to 0.
• void setCell(String cell, int value) Sets the value of the specified cell. The cell reference is provided in the format "AX" (e.g., "A1", "B10"), where the letter represents the column (from 'A' to 'Z') and the number represents a 1-indexed row.
• void resetCell(String cell) Resets the specified cell to 0.
• int getValue(String formula) Evaluates a formula of the form "=X+Y", where X and Y are either cell references or non-negative integers, and returns the computed sum.

Note: If getValue references a cell that has not been explicitly set using setCell, its value is considered 0.

Example 1:

Input:

"Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"

[3, "=5+7", "A1", 10, "=A1+6", "B2", 15, "=A1+B2", "A1", "=A1+B2"]

Output:

null, 12, null, 16, null, 25, null, 15

Explanation

Spreadsheet spreadsheet = new Spreadsheet(3); // Initializes a spreadsheet with 3 rows and 26 columns

spreadsheet.getValue("=5+7"); // returns 12 (5+7)

spreadsheet.setCell("A1", 10); // sets A1 to 10

spreadsheet.getValue("=A1+6"); // returns 16 (10+6)

spreadsheet.setCell("B2", 15); // sets B2 to 15

spreadsheet.getValue("=A1+B2"); // returns 25 (10+15)

spreadsheet.resetCell("A1"); // resets A1 to 0

spreadsheet.getValue("=A1+B2"); // returns 15 (0+15)

Constraints:

• 1 <= rows <= 10^3
• 0 <= value <= 10^5
• The formula is always in the format "=X+Y", where X and Y are either valid cell references or non-negative integers with values less than or equal to 10^5.
• Each cell reference consists of a capital letter from 'A' to 'Z' followed by a row number between 1 and rows.
• At most 10^4 calls will be made in total to setCell, resetCell, and getValue.

2025-09-20
3508. Implement Router

Topic: Array, Hash Table, Binary Search, Design, Queue, Ordered Set
Difficulty: Medium

Problem:
Design a data structure that can efficiently manage data packets in a network router. Each data packet consists of the following attributes:

• source: A unique identifier for the machine that generated the packet.
• destination: A unique identifier for the target machine.
• timestamp: The time at which the packet arrived at the router.

Implement the Router class:

Router(int memoryLimit): Initializes the Router object with a fixed memory limit.

• memoryLimit is the maximum number of packets the router can store at any given time.
• If adding a new packet would exceed this limit, the oldest packet must be removed to free up space.

bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router.

• A packet is considered a duplicate if another packet with the same source, destination, and timestamp already exists in the router.
• Return true if the packet is successfully added (i.e., it is not a duplicate); otherwise return false.

int[] forwardPacket(): Forwards the next packet in FIFO (First In First Out) order.

• Remove the packet from storage.
• Return the packet as an array [source, destination, timestamp].
• If there are no packets to forward, return an empty array.

int getCount(int destination, int startTime, int endTime):

• Returns the number of packets currently stored in the router (i.e., not yet forwarded) that have the specified destination and have timestamps in the inclusive range [startTime, endTime].

Note that queries for addPacket will be made in increasing order of timestamp.

Example 1:

Input:

"Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"

[3, 1, 4, 90, 2, 5, 90, 1, 4, 90, 3, 5, 95, 4, 5, 105, , 5, 2, 110, 5, 100, 110]

Output:

null, true, true, false, true, true, [2, 5, 90, true, 1]

Explanation

Router router = new Router(3); // Initialize Router with memoryLimit of 3.

router.addPacket(1, 4, 90); // Packet is added. Return True.

router.addPacket(2, 5, 90); // Packet is added. Return True.

router.addPacket(1, 4, 90); // This is a duplicate packet. Return False.

router.addPacket(3, 5, 95); // Packet is added. Return True

router.addPacket(4, 5, 105); // Packet is added, [1, 4, 90] is removed as number of packets exceeds memoryLimit. Return True.

router.forwardPacket(); // Return [2, 5, 90] and remove it from router.

router.addPacket(5, 2, 110); // Packet is added. Return True.

router.getCount(5, 100, 110); // The only packet with destination 5 and timestamp in the inclusive range [100, 110] is [4, 5, 105]. Return 1.
Example 2:

Input:

"Router", "addPacket", "forwardPacket", "forwardPacket"

[2, 7, 4, 90, , ]

Output:

null, true, [7, 4, 90, ]

Explanation

Router router = new Router(2); // Initialize Router with memoryLimit of 2.

router.addPacket(7, 4, 90); // Return True.

router.forwardPacket(); // Return [7, 4, 90].

router.forwardPacket(); // There are no packets left, return [].

Constraints:

• 2 <= memoryLimit <= 10^5
• 1 <= source, destination <= 2 * 10^5
• 1 <= timestamp <= 10^9
• 1 <= startTime <= endTime <= 10^9
• At most 10^5 calls will be made to addPacket, forwardPacket, and getCount methods altogether.
• queries for addPacket will be made in increasing order of timestamp.

2025-09-21
1912. Design Movie Rental System

Topic: Array, Hash Table, Design, Heap (Priority Queue), Ordered Set
Difficulty: Hard

Problem:
You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.

Each movie is given as a 2D integer array entries where entries[i] = [shop_i, movie_i, price_i] indicates that there is a copy of movie movie_i at shop shop_i with a rental price of price_i. Each shop carries at most one copy of a movie movie_i.

The system should support the following functions:

• Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_i should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.
• Rent: Rents an unrented copy of a given movie from a given shop.
• Drop: Drops off a previously rented copy of a given movie at a given shop.
• Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list res where res[j] = [shop_j, movie_j] describes that the j^th cheapest rented movie movie_j was rented from the shop shop_j. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_j should appear first, and if there is still tie, the one with the smaller movie_j should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.

Implement the MovieRentingSystem class:

• MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.
• List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.
• void rent(int shop, int movie) Rents the given movie from the given shop.
• void drop(int shop, int movie) Drops off a previously rented movie at the given shop.
• List<List<Integer>> report() Returns a list of cheapest rented movies as described above.

Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.

Example 1:

Input
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
Output
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

Explanation
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.
movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].
movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].
movieRentingSystem.report();   // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.
movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].
movieRentingSystem.search(2);  // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.

Constraints:

• 1 <= n <= 3 * 10^5
• 1 <= entries.length <= 10^5
• 0 <= shop_i < n
• 1 <= movie_i, price_i <= 10^4
• Each shop carries at most one copy of a movie movie_i.
• At most 10^5 calls in total will be made to search, rent, drop and report.

2025-09-22
3005. Count Elements With Maximum Frequency

Topic: Array, Hash Table, Counting
Difficulty: Easy

Problem:
You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

2025-09-23
165. Compare Version Numbers

Topic: Two Pointers, String
Difficulty: Medium

Problem:
Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros.

To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0.

Return the following:

• If version1 < version2, return -1.
• If version1 > version2, return 1.
• Otherwise, return 0.

Example 1:

Input: version1 = "1.2", version2 = "1.10"

Output: -1

Explanation:

version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

Example 2:

Input: version1 = "1.01", version2 = "1.001"

Output: 0

Explanation:

Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 3:

Input: version1 = "1.0", version2 = "1.0.0.0"

Output: 0

Explanation:

version1 has less revisions, which means every missing revision are treated as "0".

Constraints:

• 1 <= version1.length, version2.length <= 500
• version1 and version2 only contain digits and '.'.
• version1 and version2 are valid version numbers.
• All the given revisions in version1 and version2 can be stored in a 32-bit integer.

2025-09-24
166. Fraction to Recurring Decimal

Topic: Hash Table, Math, String
Difficulty: Medium

Problem:
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Constraints:

• -2^31 <= numerator, denominator <= 2^31 - 1
• denominator != 0

2025-09-25
120. Triangle

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?