2025-08-03
2106. Maximum Fruits Harvested After at Most K Steps

Topic: Array, Binary Search, Sliding Window, Prefix Sum
Difficulty: Hard

Problem:
Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [position_i, amount_i] depicts amount_i fruits at the position position_i. fruits is already sorted by position_i in ascending order, and each position_i is unique.

You are also given an integer startPos and an integer k. Initially, you are at the position startPos. From any position, you can either walk to the left or right. It takes one step to move one unit on the x-axis, and you can walk at most k steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position.

Return the maximum total number of fruits you can harvest.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/11/21/1.png

Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation: 
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/11/21/2.png

Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
Output: 14
Explanation: 
You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
The optimal way is to:
- Harvest the 7 fruits at the starting position 5
- Move left to position 4 and harvest 1 fruit
- Move right to position 6 and harvest 2 fruits
- Move right to position 7 and harvest 4 fruits
You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.

Example 3:

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

Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
Output: 0
Explanation:
You can move at most k = 2 steps and cannot reach any position with fruits.

Constraints:

• 1 <= fruits.length <= 10^5
• fruits[i].length == 2
• 0 <= startPos, position_i <= 2 * 10^5
• position_i-1 < position_i for any i > 0 (0-indexed)
• 1 <= amount_i <= 10^4
• 0 <= k <= 2 * 10^5

2025-08-04
904. Fruit Into Baskets

Topic: Array, Hash Table, Sliding Window
Difficulty: Medium

Problem:
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the i^th tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Constraints:

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

2025-08-05
3477. Fruits Into Baskets II

Topic: Array, Binary Search, Segment Tree, Simulation, Ordered Set
Difficulty: Easy

Problem:
You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the i^th type of fruit, and baskets[j] represents the capacity of the j^th basket.

From left to right, place the fruits according to these rules:

• Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
• Each basket can hold only one type of fruit.
• If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

Example 1:

Input: fruits = 4,2,5, baskets = 3,5,4

Output: 1

Explanation:

• fruits[0] = 4 is placed in baskets[1] = 5.
• fruits[1] = 2 is placed in baskets[0] = 3.
• fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = 3,6,1, baskets = 6,4,7

Output: 0

Explanation:

• fruits[0] = 3 is placed in baskets[0] = 6.
• fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
• fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

Constraints:

• n == fruits.length == baskets.length
• 1 <= n <= 100
• 1 <= fruits[i], baskets[i] <= 1000

2025-08-06
3479. Fruits Into Baskets III

Topic: Array, Binary Search, Segment Tree, Ordered Set
Difficulty: Medium

Problem:
You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the i^th type of fruit, and baskets[j] represents the capacity of the j^th basket.

From left to right, place the fruits according to these rules:

• Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
• Each basket can hold only one type of fruit.
• If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

Example 1:

Input: fruits = 4,2,5, baskets = 3,5,4

Output: 1

Explanation:

• fruits[0] = 4 is placed in baskets[1] = 5.
• fruits[1] = 2 is placed in baskets[0] = 3.
• fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = 3,6,1, baskets = 6,4,7

Output: 0

Explanation:

• fruits[0] = 3 is placed in baskets[0] = 6.
• fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
• fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

Constraints:

• n == fruits.length == baskets.length
• 1 <= n <= 10^5
• 1 <= fruits[i], baskets[i] <= 10^9

2025-08-07
3363. Find the Maximum Number of Fruits Collected

Topic: Array, Dynamic Programming, Matrix
Difficulty: Hard

Problem:
There is a game dungeon comprised of n x n rooms arranged in a grid.

You are given a 2D array fruits of size n x n, where fruits[i][j] represents the number of fruits in the room (i, j). Three children will play in the game dungeon, with initial positions at the corner rooms (0, 0), (0, n - 1), and (n - 1, 0).

The children will make exactly n - 1 moves according to the following rules to reach the room (n - 1, n - 1):

• The child starting from (0, 0) must move from their current room (i, j) to one of the rooms (i + 1, j + 1), (i + 1, j), and (i, j + 1) if the target room exists.
• The child starting from (0, n - 1) must move from their current room (i, j) to one of the rooms (i + 1, j - 1), (i + 1, j), and (i + 1, j + 1) if the target room exists.
• The child starting from (n - 1, 0) must move from their current room (i, j) to one of the rooms (i - 1, j + 1), (i, j + 1), and (i + 1, j + 1) if the target room exists.

When a child enters a room, they will collect all the fruits there. If two or more children enter the same room, only one child will collect the fruits, and the room will be emptied after they leave.

Return the maximum number of fruits the children can collect from the dungeon.

Example 1:

Input: fruits = [1,2,3,4,5,6,8,7,9,10,11,12,13,14,15,16]

Output: 100

Explanation:

Image: https://assets.leetcode.com/uploads/2024/10/15/example_1.gif

In this example:

• The 1^st child (green) moves on the path (0,0) -> (1,1) -> (2,2) -> (3, 3).
• The 2^nd child (red) moves on the path (0,3) -> (1,2) -> (2,3) -> (3, 3).
• The 3^rd child (blue) moves on the path (3,0) -> (3,1) -> (3,2) -> (3, 3).

In total they collect 1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100 fruits.

Example 2:

Input: fruits = [1,1,1,1]

Output: 4

Explanation:

In this example:

• The 1^st child moves on the path (0,0) -> (1,1).
• The 2^nd child moves on the path (0,1) -> (1,1).
• The 3^rd child moves on the path (1,0) -> (1,1).

In total they collect 1 + 1 + 1 + 1 = 4 fruits.

Constraints:

• 2 <= n == fruits.length == fruits[i].length <= 1000
• 0 <= fruits[i][j] <= 1000

2025-08-08
808. Soup Servings

Topic: Math, Dynamic Programming, Probability and Statistics
Difficulty: Medium

Problem:
You have two soups, A and B, each starting with n mL. On every turn, one of the following four serving operations is chosen at random, each with probability 0.25 independent of all previous turns:

• pour 100 mL from type A and 0 mL from type B
• pour 75 mL from type A and 25 mL from type B
• pour 50 mL from type A and 50 mL from type B
• pour 25 mL from type A and 75 mL from type B

Note:

• There is no operation that pours 0 mL from A and 100 mL from B.
• The amounts from A and B are poured simultaneously during the turn.
• If an operation asks you to pour more than you have left of a soup, pour all that remains of that soup.

The process stops immediately after any turn in which one of the soups is used up.

Return the probability that A is used up before B, plus half the probability that both soups are used up in the same turn. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: n = 50
Output: 0.62500
Explanation: 
If we perform either of the first two serving operations, soup A will become empty first.
If we perform the third operation, A and B will become empty at the same time.
If we perform the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Example 2:

Input: n = 100
Output: 0.71875
Explanation: 
If we perform the first serving operation, soup A will become empty first.
If we perform the second serving operations, A will become empty on performing operation [1, 2, 3], and both A and B become empty on performing operation 4.
If we perform the third operation, A will become empty on performing operation [1, 2], and both A and B become empty on performing operation 3.
If we perform the fourth operation, A will become empty on performing operation 1, and both A and B become empty on performing operation 2.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.71875.

Constraints:

• 0 <= n <= 10^9

2025-08-09
231. Power of Two

Topic: Math, Bit Manipulation, Recursion
Difficulty: Easy

Problem:
Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2^x.

Example 1:

Input: n = 1
Output: true
Explanation: 2^0 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2^4 = 16

Example 3:

Input: n = 3
Output: false

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

2025-08-10
869. Reordered Power of 2

Topic: Hash Table, Math, Sorting, Counting, Enumeration
Difficulty: Medium

Problem:
You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Example 1:

Input: n = 1
Output: true

Example 2:

Input: n = 10
Output: false

Constraints:

• 1 <= n <= 10^9

2025-08-11
2438. Range Product Queries of Powers

Topic: Array, Bit Manipulation, Prefix Sum
Difficulty: Medium

Problem:
Given a positive integer n, there exists a 0-indexed array called powers, composed of the minimum number of powers of 2 that sum to n. The array is sorted in non-decreasing order, and there is only one way to form the array.

You are also given a 0-indexed 2D integer array queries, where queries[i] = [left_i, right_i]. Each queries[i] represents a query where you have to find the product of all powers[j] with left_i <= j <= right_i.

Return an array answers, equal in length to queries, where answers[i] is the answer to the i^th query. Since the answer to the i^th query may be too large, each answers[i] should be returned modulo 10^9 + 7.

Example 1:

Input: n = 15, queries = [[0,1],[2,2],[0,3]]
Output: [2,4,64]
Explanation:
For n = 15, powers = [1,2,4,8]. It can be shown that powers cannot be a smaller size.
Answer to 1st query: powers[0] * powers[1] = 1 * 2 = 2.
Answer to 2nd query: powers[2] = 4.
Answer to 3rd query: powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64.
Each answer modulo 10^9 + 7 yields the same answer, so [2,4,64] is returned.

Example 2:

Input: n = 2, queries = [[0,0]]
Output: [2]
Explanation:
For n = 2, powers = [2].
The answer to the only query is powers[0] = 2. The answer modulo 10^9 + 7 is the same, so [2] is returned.

Constraints:

• 1 <= n <= 10^9
• 1 <= queries.length <= 10^5
• 0 <= start_i <= end_i < powers.length

2025-08-12
2787. Ways to Express an Integer as Sum of Powers

Topic: Dynamic Programming
Difficulty: Medium

Problem:
Given two positive integers n and x.

Return the number of ways n can be expressed as the sum of the x^th power of unique positive integers, in other words, the number of sets of unique integers [n_1, n_2, ..., n_k] where n = n_1^x + n_2^x + ... + n_k^x.

Since the result can be very large, return it modulo 10^9 + 7.

For example, if n = 160 and x = 3, one way to express n is n = 2^3 + 3^3 + 5^3.

Example 1:

Input: n = 10, x = 2
Output: 1
Explanation: We can express n as the following: n = 3^2 + 1^2 = 10.
It can be shown that it is the only way to express 10 as the sum of the 2^nd power of unique integers.

Example 2:

Input: n = 4, x = 1
Output: 2
Explanation: We can express n in the following ways:
- n = 4^1 = 4.
- n = 3^1 + 1^1 = 4.

Constraints:

• 1 <= n <= 300
• 1 <= x <= 5

2025-08-13
326. Power of Three

Topic: Math, Recursion
Difficulty: Easy

Problem:
Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3^x.

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 3^3

Example 2:

Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.

Example 3:

Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

2025-08-14
2264. Largest 3-Same-Digit Number in String

Topic: String
Difficulty: Easy

Problem:
You are given a string num representing a large integer. An integer is good if it meets the following conditions:

• It is a substring of num with length 3.
• It consists of only one unique digit.

Return the maximum good integer as a string or an empty string "" if no such integer exists.

Note:

• A substring is a contiguous sequence of characters within a string.
• There may be leading zeroes in num or a good integer.

Example 1:

Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".

Example 2:

Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.

Example 3:

Input: num = "42352338"
Output: ""
Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

Constraints:

• 3 <= num.length <= 1000
• num only consists of digits.

2025-08-15
342. Power of Four

Topic: Math, Bit Manipulation, Recursion
Difficulty: Easy

Problem:
Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4^x.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

2025-08-16
1323. Maximum 69 Number

Topic: Math, Greedy
Difficulty: Easy

Problem:
You are given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

• 1 <= num <= 10^4
• num consists of only 6 and 9 digits.

2025-08-17
837. New 21 Game

Topic: Math, Dynamic Programming, Sliding Window, Probability and Statistics
Difficulty: Medium

Problem:
Alice plays the following game, loosely based on the card game "21".

Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets k or more points.

Return the probability that Alice has n or fewer points.

Answers within 10^-5 of the actual answer are considered accepted.

Example 1:

Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.

Example 2:

Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.

Example 3:

Input: n = 21, k = 17, maxPts = 10
Output: 0.73278

Constraints:

• 0 <= k <= n <= 10^4
• 1 <= maxPts <= 10^4

2025-08-18
679. 24 Game

Topic: Array, Math, Backtracking
Difficulty: Hard

Problem:
You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

• The division operator '/' represents real division, not integer division.
• For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
• Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
• For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.
• You cannot concatenate numbers together
• For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.

Return true if you can get such expression that evaluates to 24, and false otherwise.

Example 1:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: cards = [1,2,1,2]
Output: false

Constraints:

• cards.length == 4
• 1 <= cards[i] <= 9

2025-08-19
2348. Number of Zero-Filled Subarrays

Topic: Array, Math
Difficulty: Medium

Problem:
Given an integer array nums, return the number of subarrays filled with 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation: 
There are 4 occurrences of [0] as a subarray.
There are 2 occurrences of [0,0] as a subarray.
There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.

Example 2:

Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation:
There are 5 occurrences of [0] as a subarray.
There are 3 occurrences of [0,0] as a subarray.
There is 1 occurrence of [0,0,0] as a subarray.
There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.

Example 3:

Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.

Constraints:

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

2025-08-20
1277. Count Square Submatrices with All Ones

Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium

Problem:
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

2025-08-21
1504. Count Submatrices With All Ones

Topic: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack
Difficulty: Medium

Problem:
Given an m x n binary matrix mat, return the number of submatrices that have all ones.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/10/27/ones1-grid.jpg

Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
Output: 13
Explanation: 
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/10/27/ones2-grid.jpg

Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
Output: 24
Explanation: 
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Constraints:

• 1 <= m, n <= 150
• mat[i][j] is either 0 or 1.

2025-08-22
3195. Find the Minimum Area to Cover All Ones I

Topic: Array, Matrix
Difficulty: Medium

Problem:
You are given a 2D binary array grid. Find a rectangle with horizontal and vertical sides with the smallest area, such that all the 1's in grid lie inside this rectangle.

Return the minimum possible area of the rectangle.

Example 1:

Input: grid = [0,1,0,1,0,1]

Output: 6

Explanation:

Image: https://assets.leetcode.com/uploads/2024/05/08/examplerect0.png

The smallest rectangle has a height of 2 and a width of 3, so it has an area of 2 * 3 = 6.

Example 2:

Input: grid = [1,0,0,0]

Output: 1

Explanation:

Image: https://assets.leetcode.com/uploads/2024/05/08/examplerect1.png

The smallest rectangle has both height and width 1, so its area is 1 * 1 = 1.

Constraints:

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] is either 0 or 1.
• The input is generated such that there is at least one 1 in grid.