Machine Learning, AI and Programming

LeetCode : Cherry Pickup

Problem Statement

Solution :

This problem is probably one of the most difficult path traversal problem, I have seen on LeetCode and I will let you know the reason why. The most faulty assumption to begin with is that, this can be solved using a greedy approach, i.e. find the maximum possible cherries during the forward traversal (0,0) to (N-1, N-1) and then find the maximum possible cherries during the backward traversal (N-1, N-1) to (0,0). This approach fails for the following example.


Because with a greedy approach, he will choose 13 cherries during forward traversal and 1 during backward for a total of 14 cherries, but if he traverses the following path :

(0,0) -> (0,3) -> (2,3) -> (2,6) -> (6,6) -> (3,3) -> (3,0) -> (0,0)

Then he can collect 15 cherries. So greedy approach would not work.

If we follow the brute force approach of going through every possible round trips, then the time complexity would be exponential. So instead we would need to use Dynamic Programming (memoization) to cache the repeated path calculations and re-use them. But the next question comes, is what should we memoize.


Like in most path traversal problems, we can easily memoize the maximum cherries from any point (i, j) to (N-1, N-1), F[i][j], during the forward journey or from the point (N-1, N-1) to (p, q), B[p][q], during the backward journey but when we need to consider both the journeys in a single traversal and with the constraint that any point visited during the forward journey should not be counted again (cherry already picked up) during the backward journey (if he passes through that same point again), this separate or independent memoization scheme will not work because the backward journey value will depend on the path during the forward journey and memoization will break that.

So instead, we would be memoizing on two points simultaneously, i.e. H[i][j][p][q], maximum cherries collected by traversing from point (i, j) to (N-1, N-1) and then to (p, q).

Observe that, we can compute the maximum cherries collected starting from (0,0) using the following recursive definition:

Max cherries from (0,0) = max {

Max cherries collected by going forward through (0,1) and coming back through (0,1),

Max cherries collected by going forward through (1,0) and coming back through (1,0),

Max cherries collected by going forward through (0,1) and coming back through (1,0),

Max cherries collected by going forward through (1,0) and coming back through (0,1),

} + Number of cherries at (0,0)

Max cherries from (0,0) = max {H[0][1][0][1], H[1][0][1][0], H[0][1][1][0], H[1][0][0][1]} + G[0][0]

where G[i][j] is the value of point (i,j) in the grid, i.e. the number of cherries at (i,j)

Similarly, by the definition of the problem and the path :

H[i][j][p][q] = max{H[i+1][j][p+1][q], H[i+1][j][p][q+1], H[i][j+1][p+1][q], H[i][j+1][p][q+1]} + G[i][j] + G[p][q]

Note that, when (i, j) and (p,q) are the same points, maximum cherries collected by going forward through (i,j+1) and coming back through (p+1,q) is same as maximum cherries collected by going forward through (i+1,j) and coming back through (p,q+1) due to symmetry. Thus,

H[i][j][i][j] = max{H[i+1][j][i+1][j], H[i+1][j][i][j+1], H[i][j+1][i][j+1]} + G[i][j]

Also due to symmetry of the problem, coming back from (N-1, N-1) to (p,q) during backward journey is same as going forward from (p,q) to (N-1, N-1) and thus we will only consider forward journeys from two points at a time, which is same as one forward journey and one backward journey.

Following is the python code for solving the above problem :

import collections

class Solution(object):
    def get_max_path_one(self, grid, p1, p2, cached):

        x = p1[0] < len(grid) and p1[1] < len(grid) and grid[p1[0]][p1[1]] != -1
        y = p2[0] < len(grid) and p2[1] < len(grid) and grid[p2[0]][p2[1]] != -1

        if x and y:
            if (p1, p2) in cached:
                w = cached[(p1, p2)]
                w = self.get_max_path(grid, p1, p2, cached)

            w = -float("Inf")

        return w

    def get_max_path(self, grid, point_1, point_2, cached):

        if point_1 == point_2 == (len(grid) - 1, len(grid) - 1):
            cached[(point_1, point_2)] = grid[len(grid) - 1][len(grid) - 1]

            p1, q1 = (point_1[0] + 1, point_1[1]), (point_1[0], point_1[1] + 1)
            p2, q2 = (point_2[0] + 1, point_2[1]), (point_2[0], point_2[1] + 1)

            a = self.get_max_path_one(grid, p1, p2, cached)
            b = self.get_max_path_one(grid, q1, q2, cached)
            c = self.get_max_path_one(grid, p1, q2, cached)

            if point_1 == point_2:
                x = grid[point_1[0]][point_1[1]]
                cached[(point_1, point_2)] = x + max(a, b, c)

                x = grid[point_1[0]][point_1[1]] + grid[point_2[0]][point_2[1]]
                d = self.get_max_path_one(grid, q1, p2, cached)

                cached[(point_1, point_2)] = x + max(a, b, c, d)

        return cached[(point_1, point_2)]

    def cherryPickup(self, grid):
        cached = collections.defaultdict(int)
        out = self.get_max_path(grid, (0,0), (0,0), cached)

        if out == -float("Inf"):
            return 0

        return out

The runtime complexity of the above code is O(N^3).

Each point in the matrix will traverse a path of maximum length 2N-1, from (0,0) to (N-1, N-1) because he can traverse either in right or down direction. Thus there will be maximum of N points to be selected between (0,0) to (N-1, N-1) and thus O(N^2) pairs of points. Thus total run-time is O(N^2*N)=O(N^3).


Tags: , , , ,