2025-12-10
3577. Count the Number of Computer Unlocking Permutations

Topic: Array, Math, Brainteaser, Combinatorics
Difficulty: Medium

Problem:
You are given an array complexity of length n.

There are n locked computers in a room with labels from 0 to n - 1, each with its own unique password. The password of the computer i has a complexity complexity[i].

The password for the computer labeled 0 is already decrypted and serves as the root. All other computers must be unlocked using it or another previously unlocked computer, following this information:

• You can decrypt the password for the computer i using the password for computer j, where j is any integer less than i with a lower complexity. (i.e. j < i and complexity[j] < complexity[i])
• To decrypt the password for computer i, you must have already unlocked a computer j such that j < i and complexity[j] < complexity[i].

Find the number of permutations of [0, 1, 2, ..., (n - 1)] that represent a valid order in which the computers can be unlocked, starting from computer 0 as the only initially unlocked one.

Since the answer may be large, return it modulo 10^9 + 7.

Note that the password for the computer with label 0 is decrypted, and not the computer with the first position in the permutation.

Example 1:

Input: complexity = 1,2,3

Output: 2

Explanation:

The valid permutations are:

• 0, 1, 2
• Unlock computer 0 first with root password.
• Unlock computer 1 with password of computer 0 since complexity[0] < complexity[1].
• Unlock computer 2 with password of computer 1 since complexity[1] < complexity[2].
• 0, 2, 1
• Unlock computer 0 first with root password.
• Unlock computer 2 with password of computer 0 since complexity[0] < complexity[2].
• Unlock computer 1 with password of computer 0 since complexity[0] < complexity[1].

Example 2:

Input: complexity = 3,3,3,4,4,4

Output: 0

Explanation:

There are no possible permutations which can unlock all computers.

Constraints:

• 2 <= complexity.length <= 10^5
• 1 <= complexity[i] <= 10^9

2025-12-11
3531. Count Covered Buildings

Topic: Array, Hash Table, Sorting
Difficulty: Medium

Problem:
You are given a positive integer n, representing an n x n city. You are also given a 2D grid buildings, where buildings[i] = [x, y] denotes a unique building located at coordinates [x, y].

A building is covered if there is at least one building in all four directions: left, right, above, and below.

Return the number of covered buildings.

Example 1:

Image: https://assets.leetcode.com/uploads/2025/03/04/telegram-cloud-photo-size-5-6212982906394101085-m.jpg

Input: n = 3, buildings = [1,2,2,2,3,2,2,1,2,3]

Output: 1

Explanation:

• Only building [2,2] is covered as it has at least one building:
• above ([1,2])
• below ([3,2])
• left ([2,1])
• right ([2,3])
• Thus, the count of covered buildings is 1.

Example 2:

Image: https://assets.leetcode.com/uploads/2025/03/04/telegram-cloud-photo-size-5-6212982906394101086-m.jpg

Input: n = 3, buildings = [1,1,1,2,2,1,2,2]

Output: 0

Explanation:

• No building has at least one building in all four directions.

Example 3:

Image: https://assets.leetcode.com/uploads/2025/03/16/telegram-cloud-photo-size-5-6248862251436067566-x.jpg

Input: n = 5, buildings = [1,3,3,2,3,3,3,5,5,3]

Output: 1

Explanation:

• Only building [3,3] is covered as it has at least one building:
• above ([1,3])
• below ([5,3])
• left ([3,2])
• right ([3,5])
• Thus, the count of covered buildings is 1.

Constraints:

• 2 <= n <= 10^5
• 1 <= buildings.length <= 10^5
• buildings[i] = [x, y]
• 1 <= x, y <= n
• All coordinates of buildings are unique.

2025-12-12
3433. Count Mentions Per User

Topic: Array, Math, Sorting, Simulation
Difficulty: Medium

Problem:
You are given an integer numberOfUsers representing the total number of users and an array events of size n x 3.

Each events[i] can be either of the following two types:

1. Message Event: ["MESSAGE", "timestamp_i", "mentions_string_i"]
• This event indicates that a set of users was mentioned in a message at timestamp_i.
• The mentions_string_i string can contain one of the following tokens:
• id<number>: where <number> is an integer in range [0,numberOfUsers - 1]. There can be multiple ids separated by a single whitespace and may contain duplicates. This can mention even the offline users.
• ALL: mentions all users.
• HERE: mentions all online users.
2. Offline Event: ["OFFLINE", "timestamp_i", "id_i"]
• This event indicates that the user id_i had become offline at timestamp_i for 60 time units. The user will automatically be online again at time timestamp_i + 60.

Return an array mentions where mentions[i] represents the number of mentions the user with id i has across all MESSAGE events.

All users are initially online, and if a user goes offline or comes back online, their status change is processed before handling any message event that occurs at the same timestamp.

Note that a user can be mentioned multiple times in a single message event, and each mention should be counted separately.

Example 1:

Input: numberOfUsers = 2, events = ["MESSAGE","10","id1 id0","OFFLINE","11","0","MESSAGE","71","HERE"]

Output: 2,2

Explanation:

Initially, all users are online.

At timestamp 10, id1 and id0 are mentioned. mentions = [1,1]

At timestamp 11, id0 goes offline.

At timestamp 71, id0 comes back online and "HERE" is mentioned. mentions = [2,2]

Example 2:

Input: numberOfUsers = 2, events = ["MESSAGE","10","id1 id0","OFFLINE","11","0","MESSAGE","12","ALL"]

Output: 2,2

Explanation:

Initially, all users are online.

At timestamp 10, id1 and id0 are mentioned. mentions = [1,1]

At timestamp 11, id0 goes offline.

At timestamp 12, "ALL" is mentioned. This includes offline users, so both id0 and id1 are mentioned. mentions = [2,2]

Example 3:

Input: numberOfUsers = 2, events = ["OFFLINE","10","0","MESSAGE","12","HERE"]

Output: 0,1

Explanation:

Initially, all users are online.

At timestamp 10, id0 goes offline.

At timestamp 12, "HERE" is mentioned. Because id0 is still offline, they will not be mentioned. mentions = [0,1]

Constraints:

• 1 <= numberOfUsers <= 100
• 1 <= events.length <= 100
• events[i].length == 3
• events[i][0] will be one of MESSAGE or OFFLINE.
• 1 <= int(events[i][1]) <= 10^5
• The number of id<number> mentions in any "MESSAGE" event is between 1 and 100.
• 0 <= <number> <= numberOfUsers - 1
• It is guaranteed that the user id referenced in the OFFLINE event is online at the time the event occurs.

2025-12-13
3606. Coupon Code Validator

Topic: Array, Hash Table, String, Sorting
Difficulty: Easy

Problem:
You are given three arrays of length n that describe the properties of n coupons: code, businessLine, and isActive. The i^th coupon has:

• code[i]: a string representing the coupon identifier.
• businessLine[i]: a string denoting the business category of the coupon.
• isActive[i]: a boolean indicating whether the coupon is currently active.

A coupon is considered valid if all of the following conditions hold:

1. code[i] is non-empty and consists only of alphanumeric characters (a-z, A-Z, 0-9) and underscores (_).
2. businessLine[i] is one of the following four categories: "electronics", "grocery", "pharmacy", "restaurant".
3. isActive[i] is true.

Return an array of the codes of all valid coupons, sorted first by their businessLine in the order: "electronics", "grocery", "pharmacy", "restaurant", and then by code in lexicographical (ascending) order within each category.

Example 1:

Input: code = "SAVE20","","PHARMA5","SAVE@20", businessLine = "restaurant","grocery","pharmacy","restaurant", isActive = true,true,true,true

Output: "PHARMA5","SAVE20"

Explanation:

• First coupon is valid.
• Second coupon has empty code (invalid).
• Third coupon is valid.
• Fourth coupon has special character @ (invalid).

Example 2:

Input: code = "GROCERY15","ELECTRONICS\_50","DISCOUNT10", businessLine = "grocery","electronics","invalid", isActive = false,true,true

Output: "ELECTRONICS\_50"

Explanation:

• First coupon is inactive (invalid).
• Second coupon is valid.
• Third coupon has invalid business line (invalid).

Constraints:

• n == code.length == businessLine.length == isActive.length
• 1 <= n <= 100
• 0 <= code[i].length, businessLine[i].length <= 100
• code[i] and businessLine[i] consist of printable ASCII characters.
• isActive[i] is either true or false.

2025-12-14
2147. Number of Ways to Divide a Long Corridor

Topic: Math, String, Dynamic Programming
Difficulty: Hard

Problem:
Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant.

One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n - 1), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10^9 + 7. If there is no way, return 0.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/12/04/1.png

Input: corridor = "SSPPSPS"
Output: 3
Explanation: There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, each section has exactly two seats.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/12/04/2.png

Input: corridor = "PPSPSP"
Output: 1
Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.

Example 3:

Image: https://assets.leetcode.com/uploads/2021/12/12/3.png

Input: corridor = "S"
Output: 0
Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

Constraints:

• n == corridor.length
• 1 <= n <= 10^5
• corridor[i] is either 'S' or 'P'.

2025-12-15
2110. Number of Smooth Descent Periods of a Stock

Topic: Array, Math, Dynamic Programming
Difficulty: Medium

Problem:
You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the i^th day.

A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.

Return the number of smooth descent periods.

Example 1:

Input: prices = [3,2,1,4]
Output: 7
Explanation: There are 7 smooth descent periods:
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Note that a period with one day is a smooth descent period by the definition.

Example 2:

Input: prices = [8,6,7,7]
Output: 4
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3:

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Constraints:

• 1 <= prices.length <= 10^5
• 1 <= prices[i] <= 10^5

2025-12-16
3562. Maximum Profit from Trading Stocks with Discounts

Topic: Array, Dynamic Programming, Tree, Depth-First Search
Difficulty: Hard

Problem:
You are given an integer n, representing the number of employees in a company. Each employee is assigned a unique ID from 1 to n, and employee 1 is the CEO. You are given two 1-based integer arrays, present and future, each of length n, where:

• present[i] represents the current price at which the i^th employee can buy a stock today.
• future[i] represents the expected price at which the i^th employee can sell the stock tomorrow.

The company's hierarchy is represented by a 2D integer array hierarchy, where hierarchy[i] = [u_i, v_i] means that employee u_i is the direct boss of employee v_i.

Additionally, you have an integer budget representing the total funds available for investment.

However, the company has a discount policy: if an employee's direct boss purchases their own stock, then the employee can buy their stock at half the original price (floor(present[v] / 2)).

Return the maximum profit that can be achieved without exceeding the given budget.

Note:

• You may buy each stock at most once.
• You cannot use any profit earned from future stock prices to fund additional investments and must buy only from budget.

Example 1:

Input: n = 2, present = 1,2, future = 4,3, hierarchy = [1,2], budget = 3

Output: 5

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-053641.png

• Employee 1 buys the stock at price 1 and earns a profit of 4 - 1 = 3.
• Since Employee 1 is the direct boss of Employee 2, Employee 2 gets a discounted price of floor(2 / 2) = 1.
• Employee 2 buys the stock at price 1 and earns a profit of 3 - 1 = 2.
• The total buying cost is 1 + 1 = 2 <= budget. Thus, the maximum total profit achieved is 3 + 2 = 5.

Example 2:

Input: n = 2, present = 3,4, future = 5,8, hierarchy = [1,2], budget = 4

Output: 4

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-053641.png

• Employee 2 buys the stock at price 4 and earns a profit of 8 - 4 = 4.
• Since both employees cannot buy together, the maximum profit is 4.

Example 3:

Input: n = 3, present = 4,6,8, future = 7,9,11, hierarchy = [1,2,1,3], budget = 10

Output: 10

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/09/image.png

• Employee 1 buys the stock at price 4 and earns a profit of 7 - 4 = 3.
• Employee 3 would get a discounted price of floor(8 / 2) = 4 and earns a profit of 11 - 4 = 7.
• Employee 1 and Employee 3 buy their stocks at a total cost of 4 + 4 = 8 <= budget. Thus, the maximum total profit achieved is 3 + 7 = 10.

Example 4:

Input: n = 3, present = 5,2,3, future = 8,5,6, hierarchy = [1,2,2,3], budget = 7

Output: 12

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-054114.png

• Employee 1 buys the stock at price 5 and earns a profit of 8 - 5 = 3.
• Employee 2 would get a discounted price of floor(2 / 2) = 1 and earns a profit of 5 - 1 = 4.
• Employee 3 would get a discounted price of floor(3 / 2) = 1 and earns a profit of 6 - 1 = 5.
• The total cost becomes 5 + 1 + 1 = 7 <= budget. Thus, the maximum total profit achieved is 3 + 4 + 5 = 12.

Constraints:

• 1 <= n <= 160
• present.length, future.length == n
• 1 <= present[i], future[i] <= 50
• hierarchy.length == n - 1
• hierarchy[i] == [u_i, v_i]
• 1 <= u_i, v_i <= n
• u_i != v_i
• 1 <= budget <= 160
• There are no duplicate edges.
• Employee 1 is the direct or indirect boss of every employee.
• The input graph hierarchy is guaranteed to have no cycles.

2025-12-17
3573. Best Time to Buy and Sell Stock V

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
You are given an integer array prices where prices[i] is the price of a stock in dollars on the i^th day, and an integer k.

You are allowed to make at most k transactions, where each transaction can be either of the following:

• Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].
• Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most k transactions.

Example 1:

Input: prices = 1,7,9,8,2, k = 2

Output: 14

Explanation:

We can make $14 of profit through 2 transactions:

• A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
• A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

Example 2:

Input: prices = 12,16,19,19,8,1,19,13,9, k = 3

Output: 36

Explanation:

We can make $36 of profit through 3 transactions:

• A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
• A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
• A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

Constraints:

• 2 <= prices.length <= 10^3
• 1 <= prices[i] <= 10^9
• 1 <= k <= prices.length / 2

2025-12-18
3652. Best Time to Buy and Sell Stock using Strategy

Topic: Array, Sliding Window, Prefix Sum
Difficulty: Medium

Problem:
You are given two integer arrays prices and strategy, where:

• prices[i] is the price of a given stock on the i^th day.
• strategy[i] represents a trading action on the i^th day, where:
• -1 indicates buying one unit of the stock.
• 0 indicates holding the stock.
• 1 indicates selling one unit of the stock.

You are also given an even integer k, and may perform at most one modification to strategy. A modification consists of:

• Selecting exactly k consecutive elements in strategy.
• Set the first k / 2 elements to 0 (hold).
• Set the last k / 2 elements to 1 (sell).

The profit is defined as the sum of strategy[i] * prices[i] across all days.

Return the maximum possible profit you can achieve.

Note: There are no constraints on budget or stock ownership, so all buy and sell operations are feasible regardless of past actions.

Example 1:

Input: prices = 4,2,8, strategy = -1,0,1, k = 2

Output: 10

Explanation:

ModificationStrategyProfit CalculationProfitOriginal-1, 0, 1 + (0 × 2) + (1 × 8) = -4 + 0 + 84Modify 0, 10, 1, 1 + (1 × 2) + (1 × 8) = 0 + 2 + 810Modify 1, 2-1, 0, 1 + (0 × 2) + (1 × 8) = -4 + 0 + 84
Thus, the maximum possible profit is 10, which is achieved by modifying the subarray [0, 1]​​​​​​​.

Example 2:

Input: prices = 5,4,3, strategy = 1,1,0, k = 2

Output: 9

Explanation:

ModificationStrategyProfit CalculationProfitOriginal1, 1, 0 + (1 × 4) + (0 × 3) = 5 + 4 + 09Modify 0, 10, 1, 0 + (1 × 4) + (0 × 3) = 0 + 4 + 04Modify 1, 21, 0, 1 + (0 × 4) + (1 × 3) = 5 + 0 + 38
Thus, the maximum possible profit is 9, which is achieved without any modification.

Constraints:

• 2 <= prices.length == strategy.length <= 10^5
• 1 <= prices[i] <= 10^5
• -1 <= strategy[i] <= 1
• 2 <= k <= prices.length
• k is even

2025-12-19
2092. Find All People With Secret

Topic: Depth-First Search, Breadth-First Search, Union Find, Graph, Sorting
Difficulty: Hard

Problem:
You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person x_i has the secret at time_i, then they will share the secret with person y_i, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

Example 1:

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.​​​​
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Constraints:

• 2 <= n <= 10^5
• 1 <= meetings.length <= 10^5
• meetings[i].length == 3
• 0 <= x_i, y_i <= n - 1
• x_i != y_i
• 1 <= time_i <= 10^5
• 1 <= firstPerson <= n - 1