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