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

2025-12-20
944. Delete Columns to Make Sorted

Topic: Array, String
Difficulty: Easy

Problem:
You are given an array of n strings strs, all of the same length.

The strings can be arranged such that there is one on each line, making a grid.

• For example, strs = ["abc", "bce", "cae"] can be arranged as follows:

abc
bce
cae

You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.

Return the number of columns that you will delete.

Example 1:

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Example 2:

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

Constraints:

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] consists of lowercase English letters.

2025-12-21
955. Delete Columns to Make Sorted II

Topic: Array, String, Greedy
Difficulty: Medium

Problem:
You are given an array of n strings strs, all of the same length.

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Return the minimum possible value of answer.length.

Example 1:

Input: strs = ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, strs = ["a", "b", "c"].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

Example 2:

Input: strs = ["xc","yb","za"]
Output: 0
Explanation: 
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.

Constraints:

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.