2025-11-29
3512. Minimum Operations to Make Array Sum Divisible by K

Topic: Array, Math
Difficulty: Easy

Problem:
You are given an integer array nums and an integer k. You can perform the following operation any number of times:

• Select an index i and replace nums[i] with nums[i] - 1.

Return the minimum number of operations required to make the sum of the array divisible by k.

Example 1:

Input: nums = 3,9,7, k = 5

Output: 4

Explanation:

• Perform 4 operations on nums[1] = 9. Now, nums = [3, 5, 7].
• The sum is 15, which is divisible by 5.

Example 2:

Input: nums = 4,1,3, k = 4

Output: 0

Explanation:

• The sum is 8, which is already divisible by 4. Hence, no operations are needed.

Example 3:

Input: nums = 3,2, k = 6

Output: 5

Explanation:

• Perform 3 operations on nums[0] = 3 and 2 operations on nums[1] = 2. Now, nums = [0, 0].
• The sum is 0, which is divisible by 6.

Constraints:

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

2025-11-30
1590. Make Sum Divisible by P

Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium

Problem:
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= p <= 10^9

2025-12-01
2141. Maximum Running Time of N Computers

Topic: Array, Binary Search, Greedy, Sorting
Difficulty: Hard

Problem:
You have n computers. You are given the integer n and a 0-indexed integer array batteries where the i^th battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the n computers simultaneously.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation: 
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/01/06/example2.png

Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation: 
Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.

Constraints:

• 1 <= n <= batteries.length <= 10^5
• 1 <= batteries[i] <= 10^9

2025-12-02
3623. Count Number of Trapezoids I

Topic: Array, Hash Table, Math, Geometry
Difficulty: Medium

Problem:
You are given a 2D integer array points, where points[i] = [x_i, y_i] represents the coordinates of the i^th point on the Cartesian plane.

A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.

Return the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from points.

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

Example 1:

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

Output: 3

Explanation:

Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-6.png

Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-7.png

Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-8.png

There are three distinct ways to pick four points that form a horizontal trapezoid:

• Using points [1,0], [2,0], [3,2], and [2,2].
• Using points [2,0], [3,0], [3,2], and [2,2].
• Using points [1,0], [3,0], [3,2], and [2,2].

Example 2:

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

Output: 1

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-5.png

There is only one horizontal trapezoid that can be formed.

Constraints:

• 4 <= points.length <= 10^5
• –10^8 <= x_i, y_i <= 10^8
• All points are pairwise distinct.

2025-12-03
3625. Count Number of Trapezoids II

Topic: Array, Hash Table, Math, Geometry
Difficulty: Hard

Problem:
You are given a 2D integer array points where points[i] = [x_i, y_i] represents the coordinates of the i^th point on the Cartesian plane.

Return the number of unique trapezoids that can be formed by choosing any four distinct points from points.

A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.

Example 1:

Input: points = [-3,2,3,0,2,3,3,2,2,-3]

Output: 2

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-4.png

Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-3.png

There are two distinct ways to pick four points that form a trapezoid:

• The points [-3,2], [2,3], [3,2], [2,-3] form one trapezoid.
• The points [2,3], [3,2], [3,0], [2,-3] form another trapezoid.

Example 2:

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

Output: 1

Explanation:

Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-5.png

There is only one trapezoid which can be formed.

Constraints:

• 4 <= points.length <= 500
• –1000 <= x_i, y_i <= 1000
• All points are pairwise distinct.

2025-12-04
2211. Count Collisions on a Road

Topic: String, Stack, Simulation
Difficulty: Medium

Problem:
There are n cars on an infinitely long road. The cars are numbered from 0 to n - 1 from left to right and each car is present at a unique point.

You are given a 0-indexed string directions of length n. directions[i] can be either 'L', 'R', or 'S' denoting whether the i^th car is moving towards the left, towards the right, or staying at its current point respectively. Each moving car has the same speed.

The number of collisions can be calculated as follows:

• When two cars moving in opposite directions collide with each other, the number of collisions increases by 2.
• When a moving car collides with a stationary car, the number of collisions increases by 1.

After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.

Return the total number of collisions that will happen on the road.

Example 1:

Input: directions = "RLRSLL"
Output: 5
Explanation:
The collisions that will happen on the road are:
- Cars 0 and 1 will collide with each other. Since they are moving in opposite directions, the number of collisions becomes 0 + 2 = 2.
- Cars 2 and 3 will collide with each other. Since car 3 is stationary, the number of collisions becomes 2 + 1 = 3.
- Cars 3 and 4 will collide with each other. Since car 3 is stationary, the number of collisions becomes 3 + 1 = 4.
- Cars 4 and 5 will collide with each other. After car 4 collides with car 3, it will stay at the point of collision and get hit by car 5. The number of collisions becomes 4 + 1 = 5.
Thus, the total number of collisions that will happen on the road is 5.

Example 2:

Input: directions = "LLRR"
Output: 0
Explanation:
No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.

Constraints:

• 1 <= directions.length <= 10^5
• directions[i] is either 'L', 'R', or 'S'.

2025-12-05
3432. Count Partitions with Even Sum Difference

Topic: Array, Math, Prefix Sum
Difficulty: Easy

Problem:
You are given an integer array nums of length n.

A partition is defined as an index i where 0 <= i < n - 1, splitting the array into two non-empty subarrays such that:

• Left subarray contains indices [0, i].
• Right subarray contains indices [i + 1, n - 1].

Return the number of partitions where the difference between the sum of the left and right subarrays is even.

Example 1:

Input: nums = 10,10,3,7,6

Output: 4

Explanation:

The 4 partitions are:

• [10], [10, 3, 7, 6] with a sum difference of 10 - 26 = -16, which is even.
• [10, 10], [3, 7, 6] with a sum difference of 20 - 16 = 4, which is even.
• [10, 10, 3], [7, 6] with a sum difference of 23 - 13 = 10, which is even.
• [10, 10, 3, 7], [6] with a sum difference of 30 - 6 = 24, which is even.

Example 2:

Input: nums = 1,2,2

Output: 0

Explanation:

No partition results in an even sum difference.

Example 3:

Input: nums = 2,4,6,8

Output: 3

Explanation:

All partitions result in an even sum difference.

Constraints:

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

2025-12-06
3578. Count Partitions With Max-Min Difference at Most K

Topic: Array, Dynamic Programming, Queue, Sliding Window, Prefix Sum, Monotonic Queue
Difficulty: Medium

Problem:
You are given an integer array nums and an integer k. Your task is to partition nums into one or more non-empty contiguous segments such that in each segment, the difference between its maximum and minimum elements is at most k.

Return the total number of ways to partition nums under this condition.

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

Example 1:

Input: nums = 9,4,1,3,7, k = 4

Output: 6

Explanation:

There are 6 valid partitions where the difference between the maximum and minimum elements in each segment is at most k = 4:

• [[9], [4], [1], [3], [7]]
• [[9], [4], [1], [3, 7]]
• [[9], [4], [1, 3], [7]]
• [[9], [4, 1], [3], [7]]
• [[9], [4, 1], [3, 7]]
• [[9], [4, 1, 3], [7]]

Example 2:

Input: nums = 3,3,4, k = 0

Output: 2

Explanation:

There are 2 valid partitions that satisfy the given conditions:

• [[3], [3], [4]]
• [[3, 3], [4]]

Constraints:

• 2 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

2025-12-07
1523. Count Odd Numbers in an Interval Range

Topic: Math
Difficulty: Easy

Problem:
Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

Constraints:

• 0 <= low <= high <= 10^9

2025-12-08
1925. Count Square Sum Triples

Topic: Math, Enumeration
Difficulty: Easy

Problem:
A square triple (a,b,c) is a triple where a, b, and c are integers and a^2 + b^2 = c^2.

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

Example 1:

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).

Example 2:

Input: n = 10
Output: 4
Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

Constraints:

• 1 <= n <= 250

2025-12-09
3583. Count Special Triplets

Topic: Array, Hash Table, Counting
Difficulty: Medium

Problem:
You are given an integer array nums.

A special triplet is defined as a triplet of indices (i, j, k) such that:

• 0 <= i < j < k < n, where n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

Return the total number of special triplets in the array.

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

Example 1:

Input: nums = 6,3,6

Output: 1

Explanation:

The only special triplet is (i, j, k) = (0, 1, 2), where:

• nums[0] = 6, nums[1] = 3, nums[2] = 6
• nums[0] = nums[1] * 2 = 3 * 2 = 6
• nums[2] = nums[1] * 2 = 3 * 2 = 6

Example 2:

Input: nums = 0,1,0,0

Output: 1

Explanation:

The only special triplet is (i, j, k) = (0, 2, 3), where:

• nums[0] = 0, nums[2] = 0, nums[3] = 0
• nums[0] = nums[2] * 2 = 0 * 2 = 0
• nums[3] = nums[2] * 2 = 0 * 2 = 0

Example 3:

Input: nums = 8,4,2,8,4

Output: 2

Explanation:

There are exactly two special triplets:

• (i, j, k) = (0, 1, 3)
• nums[0] = 8, nums[1] = 4, nums[3] = 8
• nums[0] = nums[1] * 2 = 4 * 2 = 8
• nums[3] = nums[1] * 2 = 4 * 2 = 8
• (i, j, k) = (1, 2, 4)
• nums[1] = 4, nums[2] = 2, nums[4] = 4
• nums[1] = nums[2] * 2 = 2 * 2 = 4
• nums[4] = nums[2] * 2 = 2 * 2 = 4

Constraints:

• 3 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5

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