2106. Maximum Fruits Harvested After at Most K Steps LeetCode Solution
In this guide, you will get 2106. Maximum Fruits Harvested After at Most K Steps LeetCode Solution with the best time and space complexity. The solution to Maximum Fruits Harvested After at Most K Steps problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Fruits Harvested After at Most K Steps
Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [positioni, amounti] depicts amounti fruits at the position positioni. fruits is already sorted by positioni in ascending order, and each positioni 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:
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.
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:
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.
2106. Maximum Fruits Harvested After at Most K Steps LeetCode Solution in C++
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
const int maxRight = max(startPos, fruits.back()[0]);
int ans = 0;
vector<int> amounts(1 + maxRight);
vector<int> prefix(2 + maxRight);
for (const vector<int>& f : fruits)
amounts[f[0]] = f[1];
partial_sum(amounts.begin(), amounts.end(), prefix.begin() + 1);
auto getFruits = [&](int leftSteps, int rightSteps) {
const int l = max(0, startPos - leftSteps);
const int r = min(maxRight, startPos + rightSteps);
return prefix[r + 1] - prefix[l];
};
// Go right first.
const int maxRightSteps = min(maxRight - startPos, k);
for (int rightSteps = 0; rightSteps <= maxRightSteps; ++rightSteps) {
const int leftSteps = max(0, k - 2 * rightSteps); // Turn left
ans = max(ans, getFruits(leftSteps, rightSteps));
}
// Go left first.
const int maxLeftSteps = min(startPos, k);
for (int leftSteps = 0; leftSteps <= maxLeftSteps; ++leftSteps) {
const int rightSteps = max(0, k - 2 * leftSteps); // Turn right
ans = max(ans, getFruits(leftSteps, rightSteps));
}
return ans;
}
}; /* code provided by PROGIEZ */
2106. Maximum Fruits Harvested After at Most K Steps LeetCode Solution in Java
class Solution {
public int maxTotalFruits(int[][] fruits, int startPos, int k) {
final int maxRight = Math.max(startPos, fruits[fruits.length - 1][0]);
int ans = 0;
int[] amounts = new int[1 + maxRight];
int[] prefix = new int[2 + maxRight];
for (int[] f : fruits)
amounts[f[0]] = f[1];
for (int i = 0; i + 1 < prefix.length; ++i)
prefix[i + 1] = prefix[i] + amounts[i];
// Go right first.
final int maxRightSteps = Math.min(maxRight - startPos, k);
for (int rightSteps = 0; rightSteps <= maxRightSteps; ++rightSteps) {
final int leftSteps = Math.max(0, k - 2 * rightSteps); // Turn left
ans = Math.max(ans, getFruits(startPos, maxRight, leftSteps, rightSteps, prefix));
}
// Go left first.
final int maxLeftSteps = Math.min(startPos, k);
for (int leftSteps = 0; leftSteps <= maxLeftSteps; ++leftSteps) {
final int rightSteps = Math.max(0, k - 2 * leftSteps); // Turn right
ans = Math.max(ans, getFruits(startPos, maxRight, leftSteps, rightSteps, prefix));
}
return ans;
}
private int getFruits(int startPos, int maxRight, int leftSteps, int rightSteps, int[] prefix) {
final int l = Math.max(0, startPos - leftSteps);
final int r = Math.min(maxRight, startPos + rightSteps);
return prefix[r + 1] - prefix[l];
}
} // code provided by PROGIEZ
2106. Maximum Fruits Harvested After at Most K Steps LeetCode Solution in Python
class Solution:
def maxTotalFruits(
self,
fruits: list[list[int]],
startPos: int,
k: int,
) -> int:
ans = 0
maxRight = max(startPos, fruits[-1][0])
amounts = [0] * (1 + maxRight)
for position, amount in fruits:
amounts[position] = amount
prefix = list(itertools.accumulate(amounts, initial=0))
def getFruits(leftSteps: int, rightSteps: int) -> int:
l = max(0, startPos - leftSteps)
r = min(maxRight, startPos + rightSteps)
return prefix[r + 1] - prefix[l]
# Go right first.
for rightSteps in range(min(maxRight - startPos, k) + 1):
leftSteps = max(0, k - 2 * rightSteps) # Turn left
ans = max(ans, getFruits(leftSteps, rightSteps))
# Go left first.
for leftSteps in range(min(startPos, k) + 1):
rightSteps = max(0, k - 2 * leftSteps) # Turn right
ans = max(ans, getFruits(leftSteps, rightSteps))
return ans # code by PROGIEZ
