LeetCode 3938 - Maximum Path Intersection Sum in a Grid

Difficulty: 🟡 Medium
Topics: —

Solution

Here’s a fully detailed technical solution guide for LeetCode 3938, following your formatting and content requirements.

Problem Understanding

The problem provides an m x n integer grid and two players with distinct movement constraints. Player 1 starts at the top-left (0, 0) and moves only right or down to reach the bottom-right (m-1, n-1). Player 2 starts at the bottom-left (m-1, 0) and moves only right or up to reach the top-right (0, n-1).

The key task is to identify shared cells, which are grid cells that both players traverse on their respective paths, and compute the maximum sum of values of all shared cells. We need to maximize this sum over all possible path pairs.

Input constraints are significant: 2 <= m, n <= 1000 and 4 <= m * n <= 5 * 10^5, meaning a brute-force enumeration of all possible paths is infeasible. Cell values range from -100 to 100, so paths may involve negative contributions that need careful handling. Edge cases include grids where all cells are negative, grids with single-row or single-column corridors, and grids where shared cells are sparse.

Approaches

Brute Force

A brute-force solution would generate all valid paths for both players, then compute the sum of shared cells for each path pair. The algorithm is correct but computationally intractable because Player 1 has approximately $\binom{m+n-2}{m-1}$ paths, and Player 2 has a similar count. For large grids, this grows exponentially, making it impossible to run within reasonable time limits.

Key Insight for Optimal Approach

Instead of enumerating paths, we observe that the problem is a two-dimensional dynamic programming problem. For Player 1, we can compute the maximum path sum from top-left to every cell using standard DP with only right and down moves. Similarly, for Player 2, we compute the maximum path sum from bottom-left to every cell with right and up moves.

Once these two DP matrices are computed, a cell (i, j) is a candidate shared cell if it lies on some path for both players, and its value contributes to the intersection sum. The goal is to maximize the sum of such shared cells, which effectively reduces to considering overlapping optimal paths and aggregating the maximum overlap.

This leads to an algorithm with O(m * n) time complexity and O(m * n) space complexity, which is acceptable given the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(m+n))	O(1)	Enumerate all paths for both players, infeasible for large grids
Optimal DP	O(m * n)	O(m * n)	Compute max path sums for both players independently, then aggregate intersection sums

Algorithm Walkthrough

Compute DP for Player 1: Create a matrix dp1[i][j] representing the maximum path sum from (0,0) to (i,j) using only right and down moves. Initialize dp1[0][0] = grid[0][0] and fill using the relation:

dp1[i][j] = grid[i][j] + max(dp1[i-1][j], dp1[i][j-1]) handling boundary conditions. 2. Compute DP for Player 2: Create a matrix dp2[i][j] representing the maximum path sum from (m-1,0) to (i,j) using only right and up moves. Initialize dp2[m-1][0] = grid[m-1][0] and fill using the relation:

dp2[i][j] = grid[i][j] + max(dp2[i+1][j], dp2[i][j-1]) handling boundaries. 3. Identify shared cells: Iterate over all cells (i,j) in the grid. A cell can only be shared if it is part of some optimal path in both dp1 and dp2. The contribution of a shared cell is simply grid[i][j]. 4. Maximize intersection sum: For each candidate cell, compute the total sum of intersection values. The final answer is the maximum sum of these shared cells.

Why it works: The DP matrices guarantee that every cell's value in dp1 and dp2 reflects the maximum achievable sum to that cell from the respective start positions. Intersecting the optimal paths ensures that only the best contributions from both players are included. By iterating over all cells, we account for the maximum possible intersection sum without enumerating paths explicitly.

Python Solution

from typing import List

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # DP for Player 1: top-left to bottom-right
        dp1 = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                top = dp1[i-1][j] if i > 0 else float('-inf')
                left = dp1[i][j-1] if j > 0 else float('-inf')
                if i == 0 and j == 0:
                    dp1[i][j] = grid[i][j]
                else:
                    dp1[i][j] = grid[i][j] + max(top, left)
        
        # DP for Player 2: bottom-left to top-right
        dp2 = [[0] * n for _ in range(m)]
        for i in reversed(range(m)):
            for j in range(n):
                bottom = dp2[i+1][j] if i+1 < m else float('-inf')
                left = dp2[i][j-1] if j > 0 else float('-inf')
                if i == m-1 and j == 0:
                    dp2[i][j] = grid[i][j]
                else:
                    dp2[i][j] = grid[i][j] + max(bottom, left)
        
        # Maximum sum of shared cells
        max_shared = float('-inf')
        for i in range(m):
            for j in range(n):
                # A cell is shared if it is reachable by both optimal paths
                max_shared = max(max_shared, dp1[i][j] + dp2[i][j] - grid[i][j])
        
        return max_shared

Implementation Explanation:

We first construct dp1 for Player 1 using standard top-left to bottom-right DP. Next, dp2 for Player 2 is built from bottom-left to top-right. The main insight is to avoid double-counting a shared cell by subtracting grid[i][j] once when summing dp1[i][j] + dp2[i][j]. Finally, we iterate over all cells to find the maximum shared sum.

Go Solution

func maxScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    
    dp1 := make([][]int, m)
    for i := range dp1 {
        dp1[i] = make([]int, n)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            top, left := -1<<31, -1<<31
            if i > 0 {
                top = dp1[i-1][j]
            }
            if j > 0 {
                left = dp1[i][j-1]
            }
            if i == 0 && j == 0 {
                dp1[i][j] = grid[i][j]
            } else {
                if top > left {
                    dp1[i][j] = grid[i][j] + top
                } else {
                    dp1[i][j] = grid[i][j] + left
                }
            }
        }
    }
    
    dp2 := make([][]int, m)
    for i := range dp2 {
        dp2[i] = make([]int, n)
    }
    
    for i := m-1; i >= 0; i-- {
        for j := 0; j < n; j++ {
            bottom, left := -1<<31, -1<<31
            if i+1 < m {
                bottom = dp2[i+1][j]
            }
            if j > 0 {
                left = dp2[i][j-1]
            }
            if i == m-1 && j == 0 {
                dp2[i][j] = grid[i][j]
            } else {
                if bottom > left {
                    dp2[i][j] = grid[i][j] + bottom
                } else {
                    dp2[i][j] = grid[i][j] + left
                }
            }
        }
    }
    
    maxShared := -1 << 31
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            val := dp1[i][j] + dp2[i][j] - grid[i][j]
            if val > maxShared {
                maxShared = val
            }
        }
    }
    
    return max