3648. Find The Maximum Number Of Fruits Collected¶

Difficulty: Hard

3648. Find the Maximum Number of Fruits Collected

Hard

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:

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

Solution¶

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static class Pair {
        int row, col;
        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
        @Override
        public String toString() {
            return "(" + row + " " + col + ")";
        }
    }
    public int maxCollectedFruits(int[][] arr) {
        int n = arr.length;
        int res = 0;
        for (int i = 0; i < n; i++)
            res += arr[i][i];
        res += solveTopRight(arr) + solveBottomLeft(arr) - 2 * arr[n - 1][n - 1];
        return res;
    }
    private int solveTopRight(int arr[][]) {
        int n = arr.length;
        int dp[][] = new int[n + 1][n + 1];
        for (int current[] : dp)
            Arrays.fill(current, (int)(-1e9));
        dp[0][n - 1] = arr[0][n - 1];
        int dir[][] = {{1, -1}, {1, 0}, {1, 1}};
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(0, n - 1));
        while (q.size() > 0) {
            int currRow = q.peek().row, currCol = q.peek().col;
            q.poll();
            for (int dire[] : dir) {
                int newRow = currRow + dire[0], newCol = currCol + dire[1];
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                    if (newRow == newCol && newRow != n - 1 && newCol != n - 1)
                        continue;
                    if (dp[newRow][newCol] < dp[currRow][currCol] + arr[newRow][newCol]) {
                        dp[newRow][newCol] = dp[currRow][currCol] + arr[newRow][newCol];
                        q.offer(new Pair(newRow, newCol));
                    }
                }
            }
        }
        return dp[n - 1][n - 1];
    }
    private int solveBottomLeft(int arr[][]) {
        int n = arr.length;
        int dp[][] = new int[n + 1][n + 1];
        for (int current[] : dp)
            Arrays.fill(current, (int)(-1e9));
        dp[n - 1][0] = arr[n - 1][0];
        int dir[][] = {{-1, 1}, {0, 1}, {1, 1}};
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(n - 1, 0));
        while (q.size() > 0) {
            int currRow = q.peek().row, currCol = q.peek().col;
            q.poll();
            for (int dire[] : dir) {
                int newRow = currRow + dire[0], newCol = currCol + dire[1];
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                    if (newRow == newCol && newRow != n - 1 && newCol != n - 1)
                        continue;
                    if (dp[newRow][newCol] < dp[currRow][currCol] + arr[newRow][newCol]) {
                        dp[newRow][newCol] = dp[currRow][currCol] + arr[newRow][newCol];
                        q.offer(new Pair(newRow, newCol));
                    }
                }
            }
        }
        return dp[n - 1][n - 1];
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here