3363. Find the Maximum Number of Fruits Collected LeetCode Solution
In this guide, you will get 3363. Find the Maximum Number of Fruits Collected LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Number of Fruits Collected 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 Find the Maximum Number of Fruits Collected
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.
3363. Find the Maximum Number of Fruits Collected LeetCode Solution in C++
class Solution {
public:
int maxCollectedFruits(vector<vector<int>>& fruits) {
return getTopLeft(fruits) + getTopRight(fruits) + getBottomLeft(fruits) -
* fruits.back().back();
}
private:
int getTopLeft(const vector<vector<int>>& fruits) {
const int n = fruits.size();
int res = 0;
for (int i = 0; i < n; ++i)
res += fruits[i][i];
return res;
}
int getTopRight(const vector<vector<int>>& fruits) {
const int n = fruits.size();
// dp[i][j] := the number of fruits collected from (0, n - 1) to (i, j)
vector<vector<int>> dp(n, vector<int>(n));
dp[0][n - 1] = fruits[0][n - 1];
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (x >= y && !(x == n - 1 && y == n - 1))
continue;
for (const auto& [dx, dy] :
vector<pair<int, int>>{{1, -1}, {1, 0}, {1, 1}}) {
const int i = x - dx;
const int j = y - dy;
if (i < 0 || i == n || j < 0 || j == n)
continue;
if (i < j && j < n - 1 - i)
continue;
dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y]);
}
}
}
return dp[n - 1][n - 1];
}
int getBottomLeft(const vector<vector<int>>& fruits) {
const int n = fruits.size();
// dp[i][j] := the number of fruits collected from (n - 1, 0) to (i, j)
vector<vector<int>> dp(n, vector<int>(n));
dp[n - 1][0] = fruits[n - 1][0];
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
if (x <= y && !(x == n - 1 && y == n - 1))
continue;
for (const auto& [dx, dy] :
vector<pair<int, int>>{{-1, 1}, {0, 1}, {1, 1}}) {
const int i = x - dx;
const int j = y - dy;
if (i < 0 || i == n || j < 0 || j == n)
continue;
if (j < i && i < n - 1 - j)
continue;
dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y]);
}
}
}
return dp[n - 1][n - 1];
}
}; /* code provided by PROGIEZ */
3363. Find the Maximum Number of Fruits Collected LeetCode Solution in Java
class Solution {
public int maxCollectedFruits(int[][] fruits) {
final int n = fruits.length;
return getTopLeft(fruits) + getTopRight(fruits) + getBottomLeft(fruits) //
- 2 * fruits[n - 1][n - 1];
}
private int getTopLeft(int[][] fruits) {
final int n = fruits.length;
int res = 0;
for (int i = 0; i < n; ++i)
res += fruits[i][i];
return res;
}
private int getTopRight(int[][] fruits) {
final int n = fruits.length;
// dp[i][j] := the number of fruits collected from (0, n - 1) to (i, j)
int[][] dp = new int[n][n];
dp[0][n - 1] = fruits[0][n - 1];
for (int x = 0; x < n; ++x)
for (int y = 0; y < n; ++y) {
if (x >= y && !(x == n - 1 && y == n - 1))
continue;
for (int[] dir : new int[][] {{1, -1}, {1, 0}, {1, 1}}) {
final int i = x - dir[0];
final int j = y - dir[1];
if (i < 0 || i == n || j < 0 || j == n)
continue;
if (i < j && j < n - 1 - i)
continue;
dp[x][y] = Math.max(dp[x][y], dp[i][j] + fruits[x][y]);
}
}
return dp[n - 1][n - 1];
}
private int getBottomLeft(int[][] fruits) {
final int n = fruits.length;
// dp[i][j] := the number of fruits collected from (n - 1, 0) to (i, j)
int[][] dp = new int[n][n];
dp[n - 1][0] = fruits[n - 1][0];
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x) {
if (x <= y && !(x == n - 1 && y == n - 1))
continue;
for (int[] dir : new int[][] {{-1, 1}, {0, 1}, {1, 1}}) {
final int i = x - dir[0];
final int j = y - dir[1];
if (i < 0 || i == n || j < 0 || j == n)
continue;
if (j < i && i < n - 1 - j)
continue;
dp[x][y] = Math.max(dp[x][y], dp[i][j] + fruits[x][y]);
}
}
return dp[n - 1][n - 1];
}
} // code provided by PROGIEZ
3363. Find the Maximum Number of Fruits Collected LeetCode Solution in Python
class Solution:
def maxCollectedFruits(self, fruits: list[list[int]]) -> int:
n = len(fruits)
def getTopLeft() -> int:
return sum(fruits[i][i] for i in range(n))
def getTopRight() -> int:
# dp[i][j] := the number of fruits collected from (0, n - 1) to (i, j)
dp = [[0] * n for _ in range(n)]
dp[0][-1] = fruits[0][-1]
for x in range(n):
for y in range(n):
if x >= y and (x, y) != (n - 1, n - 1):
continue
for dx, dy in [(1, -1), (1, 0), (1, 1)]:
i = x - dx
j = y - dy
if i < 0 or i == n or j < 0 or j == n:
continue
if i < j < n - 1 - i:
continue
dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y])
return dp[-1][-1]
def getBottomLeft() -> int:
# dp[i][j] := the number of fruits collected from (n - 1, 0) to (i, j)
dp = [[0] * n for _ in range(n)]
dp[-1][0] = fruits[-1][0]
for y in range(n):
for x in range(n):
if x <= y and (x, y) != (n - 1, n - 1):
continue
for dx, dy in [(-1, 1), (0, 1), (1, 1)]:
i = x - dx
j = y - dy
if i < 0 or i == n or j < 0 or j == n:
continue
if j < i < n - 1 - j:
continue
dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y])
return dp[-1][-1]
return getTopLeft() + getTopRight() + getBottomLeft() - 2 * fruits[-1][-1] # code by PROGIEZ
