Frontend School

Maximal L-shaped Path Sum in a Matrix

DSA
hard

Maximal L-shaped Path Sum in a Matrix

Hard
Matrix
Dynamic Programming
Prefix Sum

Overview

In various grid-based computational tasks, such as optimal sensor placement, network routing, or resource collection in a simulated environment, identifying specific geometric patterns with maximal value can be critical. This problem challenges you to find an 'L'-shaped path within a matrix that yields the highest possible sum of cell values. This pattern recognition is a fundamental skill in optimizing resource utilization and pathfinding in constrained environments.

What you need to do / Task

Your task is to implement the maximalLPathSum function:

  1. The function will take a 2D integer matrix grid as input.
  2. You must identify an 'L'-shaped path within the grid such that the sum of its constituent cell values is maximized.
  3. An 'L'-shaped path is defined by a central "corner" cell (r, c) and two segments: one purely vertical and one purely horizontal. Both segments must originate from the corner cell and extend outwards in a cardinal direction (up/down for vertical, left/right for horizontal).
  4. Crucially, each segment must have a "length" of at least 1. This means each segment must include at least one cell other than the corner cell itself. For example, a vertical segment consisting of cells (r, c) and (r-1, c) has a length of 1.
  5. The corner cell (r, c) is counted only once in the total sum.
  6. Return the maximum possible L-shaped path sum. If no valid L-shaped path can be formed (e.g., the matrix is too small), return Number.MIN_SAFE_INTEGER.

Input & output

  • grid: A number[][] representing the matrix. Each cell grid[r][c] contains an integer value.
  • Returns: A number representing the maximal L-shaped path sum. If no valid L-shaped path exists (e.g., matrix dimensions are R < 2 or C < 2), return Number.MIN_SAFE_INTEGER.

Clarifications

  • The grid can contain negative integer values. This means an optimal path might include negative values if they lead to a larger overall sum compared to not including them, or if all possible sums are negative, you should return the largest (least negative) sum.
  • An 'L'-shaped path has 8 possible orientations based on the direction of its vertical and horizontal segments from the corner (e.g., Up-Left, Up-Right, Down-Left, Down-Right, and longer extensions of these basic forms).
  • The length of a segment is the number of cells excluding the corner cell. So, a path like (r, c-1), (r, c), (r+1, c) has a horizontal segment of length 1 and a vertical segment of length 1.

Examples

1

Example 1

Input:

grid = [[1,2,3],[4,5,6],[7,8,9]]

Output:

33

Note:

Consider the L-shape with corner at (2,2) (value 9). The vertical segment goes upwards to (0,2) (values 3,6,9, sum 18). The horizontal segment goes leftwards to (2,0) (values 7,8,9, sum 24). The total sum is 18 + 24 - 9 (corner counted once) = 33. This is the maximal sum.

2

Example 2

Input:

grid = [[-1,-2,-3],[-4,-5,-6],[-7,-8,-9]]

Output:

-11

Note:

All values are negative. The maximal sum will be the least negative. Consider an L-shape with corner at (1,1) (value -5). The vertical segment goes upwards, choosing (-2,-5) with sum -7. The horizontal segment goes leftwards, choosing (-4,-5) with sum -9. Total sum is -7 + (-9) - (-5) = -11. This is the maximal sum.

3

Example 3

Input:

grid = [[10]]

Output:

-2147483648

Note:

The grid is 1x1. It is too small to form any L-shaped path with segments of length at least 1. Thus, Number.MIN_SAFE_INTEGER is returned.

Constraints

Constraints & assumptions

  • 1 <= grid.length <= 500 (R, number of rows)
  • 1 <= grid[0].length <= 500 (C, number of columns)
  • -1000 <= grid[r][c] <= 1000
  • The grid is guaranteed to be non-empty and rectangular.

What interviewers evaluate

  • Correctness: The solution must correctly identify the maximal L-shaped path sum for all valid inputs, including edge cases and scenarios with negative values, adhering strictly to the 'length at least 1' segment constraint.
  • Efficiency: The solution should achieve optimal time complexity, ideally O(R*C), by utilizing dynamic programming or similar techniques. Space complexity should also be considered.
  • Code Quality: Clarity, readability, modularity, and adherence to best practices in variable naming, function structure, and comments.
  • Problem Understanding & Edge Cases: Ability to handle inputs where no valid L-shape can be formed (e.g., matrices smaller than 2x2) and correctly interpret the segment length constraint.

Loading editor...