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?

2025-09-26
611. Valid Triangle Number

Topic: Array, Two Pointers, Binary Search, Greedy, Sorting
Difficulty: Medium

Problem:
Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

2025-09-27
812. Largest Triangle Area

Topic: Array, Math, Geometry
Difficulty: Easy

Problem:
Given an array of points on the X-Y plane points where points[i] = [x_i, y_i], return the area of the largest triangle that can be formed by any three different points. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/04/1027.png

Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000
Explanation: The five points are shown in the above figure. The red triangle is the largest.

Example 2:

Input: points = [[1,0],[0,0],[0,1]]
Output: 0.50000

Constraints:

• 3 <= points.length <= 50
• -50 <= x_i, y_i <= 50
• All the given points are unique.

2025-09-28
976. Largest Perimeter Triangle

Topic: Array, Math, Greedy, Sorting
Difficulty: Easy

Problem:
Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints:

• 3 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^6

2025-09-29
1039. Minimum Score Triangulation of Polygon

Topic: Array, Dynamic Programming
Difficulty: Medium

Problem:
You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the i^th vertex in clockwise order.

Polygon triangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles.

You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles.

Return the minimum possible score that you can achieve with some triangulation of the polygon.

Example 1:

Image: http://127.0.0.1:49174/shape1.jpg

Input: values = 1,2,3

Output: 6

Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

Image: http://127.0.0.1:49174/shape2.jpg

Input: values = 3,7,4,5

Output: 144

Explanation: There are two triangulations, with possible scores: 375 + 457 = 245, or 345 + 347 = 144.

The minimum score is 144.

Example 3:

Image: http://127.0.0.1:49174/shape3.jpg

Input: values = 1,3,1,4,1,5

Output: 13

Explanation: The minimum score triangulation is 113 + 114 + 115 + 111 = 13.

Constraints:

• n == values.length
• 3 <= n <= 50
• 1 <= values[i] <= 100

2025-09-30
2221. Find Triangular Sum of an Array

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

Problem:
You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the value of the only element present in nums after the following process terminates:

1. Let nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
2. For each index i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
3. Replace the array nums with newNums.
4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/02/22/ex1drawio.png

Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2:

Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

2025-10-01
1518. Water Bottles

Topic: Math, Simulation
Difficulty: Easy

Problem:
There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

Example 1:

Image: https://assets.leetcode.com/uploads/2020/07/01/sample_1_1875.png

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Image: https://assets.leetcode.com/uploads/2020/07/01/sample_2_1875.png

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Constraints:

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

2025-10-02
3100. Water Bottles II

Topic: Math, Simulation
Difficulty: Medium

Problem:
You are given two integers numBottles and numExchange.

numBottles represents the number of full water bottles that you initially have. In one operation, you can perform one of the following operations:

• Drink any number of full water bottles turning them into empty bottles.
• Exchange numExchange empty bottles with one full water bottle. Then, increase numExchange by one.

Note that you cannot exchange multiple batches of empty bottles for the same value of numExchange. For example, if numBottles == 3 and numExchange == 1, you cannot exchange 3 empty water bottles for 3 full bottles.

Return the maximum number of water bottles you can drink.

Example 1:

Image: https://assets.leetcode.com/uploads/2024/01/28/exampleone1.png

Input: numBottles = 13, numExchange = 6
Output: 15
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Example 2:

Image: https://assets.leetcode.com/uploads/2024/01/28/example231.png

Input: numBottles = 10, numExchange = 3
Output: 13
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Constraints:

• 1 <= numBottles <= 100
• 1 <= numExchange <= 100

2025-10-03
407. Trapping Rain Water II

Topic: Array, Breadth-First Search, Heap (Priority Queue), Matrix
Difficulty: Hard

Problem:
Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/04/08/trap1-3d.jpg

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/04/08/trap2-3d.jpg

Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10

Constraints:

• m == heightMap.length
• n == heightMap[i].length
• 1 <= m, n <= 200
• 0 <= heightMap[i][j] <= 2 * 10^4

2025-10-04
11. Container With Most Water

Topic: Array, Two Pointers, Greedy
Difficulty: Medium

Problem:
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

2025-10-05
417. Pacific Atlantic Water Flow

Topic: Array, Depth-First Search, Breadth-First Search, Matrix
Difficulty: Medium

Problem:
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [r_i, c_i] denotes that rain water can flow from cell (r_i, c_i) to both the Pacific and Atlantic oceans.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 10^5

2025-10-06
778. Swim in Rising Water

Topic: Array, Binary Search, Depth-First Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix
Difficulty: Hard

Problem:
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

It starts raining, and water gradually rises over time. At time t, the water level is t, meaning any cell with elevation less than equal to t is submerged or reachable.

You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the minimum time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Example 1:

Image: https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg

Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• Each value grid[i][j] is unique.

2025-10-07
1488. Avoid Flood in The City

Topic: Array, Hash Table, Binary Search, Greedy, Heap (Priority Queue)
Difficulty: Medium

Problem:
Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake that is full of water, there will be a flood. Your goal is to avoid floods in any lake.

Given an integer array rains where:

• rains[i] > 0 means there will be rains over the rains[i] lake.
• rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

• ans.length == rains.length
• ans[i] == -1 if rains[i] > 0.
• ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes.

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Constraints:

• 1 <= rains.length <= 10^5
• 0 <= rains[i] <= 10^9

2025-10-08
2300. Successful Pairs of Spells and Potions

Topic: Array, Two Pointers, Binary Search, Sorting
Difficulty: Medium

Problem:
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i^th spell and potions[j] represents the strength of the j^th potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the i^th spell.

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0^th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1^st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2^nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0^th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1^st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2^nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 10^5
• 1 <= success <= 10^10

2025-10-09
3494. Find the Minimum Amount of Time to Brew Potions

Topic: Array, Simulation, Prefix Sum
Difficulty: Medium

Problem:
You are given two integer arrays, skill and mana, of length n and m, respectively.

In a laboratory, n wizards must brew m potions in order. Each potion has a mana capacity mana[j] and must pass through all the wizards sequentially to be brewed properly. The time taken by the i^th wizard on the j^th potion is time_ij = skill[i] * mana[j].

Since the brewing process is delicate, a potion must be passed to the next wizard immediately after the current wizard completes their work. This means the timing must be synchronized so that each wizard begins working on a potion exactly when it arrives. ​

Return the minimum amount of time required for the potions to be brewed properly.

Example 1:

Input: skill = 1,5,2,4, mana = 5,1,4,2

Output: 110

Explanation:

Potion NumberStart timeWizard 0 done byWizard 1 done byWizard 2 done byWizard 3 done by005304060152535860642545878861023868898102110
As an example for why wizard 0 cannot start working on the 1^st potion before time t = 52, consider the case where the wizards started preparing the 1^st potion at time t = 50. At time t = 58, wizard 2 is done with the 1^st potion, but wizard 3 will still be working on the 0^th potion till time t = 60.

Example 2:

Input: skill = 1,1,1, mana = 1,1,1

Output: 5

Explanation:

1. Preparation of the 0^th potion begins at time t = 0, and is completed by time t = 3.
2. Preparation of the 1^st potion begins at time t = 1, and is completed by time t = 4.
3. Preparation of the 2^nd potion begins at time t = 2, and is completed by time t = 5.

Example 3:

Input: skill = 1,2,3,4, mana = 1,2

Output: 21

Constraints:

• n == skill.length
• m == mana.length
• 1 <= n, m <= 5000
• 1 <= mana[i], skill[i] <= 5000

2025-10-10
3147. Taking Maximum Energy From the Mystic Dungeon

Topic: Array, Prefix Sum
Difficulty: Medium

Problem:
In a mystic dungeon, n magicians are standing in a line. Each magician has an attribute that gives you energy. Some magicians can give you negative energy, which means taking energy from you.

You have been cursed in such a way that after absorbing energy from magician i, you will be instantly transported to magician (i + k). This process will be repeated until you reach the magician where (i + k) does not exist.

In other words, you will choose a starting point and then teleport with k jumps until you reach the end of the magicians' sequence, absorbing all the energy during the journey.

You are given an array energy and an integer k. Return the maximum possible energy you can gain.

Note that when you are reach a magician, you must take energy from them, whether it is negative or positive energy.

Example 1:

Input: energy = 5,2,-10,-5,1, k = 3

Output: 3

Explanation: We can gain a total energy of 3 by starting from magician 1 absorbing 2 + 1 = 3.

Example 2:

Input: energy = -2,-3,-1, k = 2

Output: -1

Explanation: We can gain a total energy of -1 by starting from magician 2.

Constraints:

• 1 <= energy.length <= 10^5
• -1000 <= energy[i] <= 1000
• 1 <= k <= energy.length - 1

​​​​​​