Maximum Falling Path Sum in a Rectangle
Updated
Problem statement
Given a rectangular integer matrix grid, find the maximum sum of a path that starts at any cell in the first row and ends in the last row. From row r, column c, move to row r+1 and column c-1, c, or c+1, whenever that column is inside the matrix.
For this exercise, assume the matrix is nonempty and may contain negative values. Every path includes exactly one cell from each row. Return the maximum path sum.
Function
maximumFallingPath(grid: int[][]) → intExamples
Example 1
grid = [[1,2,3],[9,8,7],[4,5,6]]return = 17A path can take 3, then 8, then 6 for a total of 17.
Example 2
grid = [[-5,-2],[-3,-4]]return = -5Choose -2 followed diagonally by -3. A path cannot stop early or take an empty sum.
Constraints
- For this exercise, assume
1 <= rows, columns <= 100. - Every row has the same number of columns.
-1000000 <= grid[r][c] <= 1000000.
More PeopleStrong Onsite Interview questions
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
- LRU Cache OperationsONSITE INTERVIEW · Seen Mar 2026
- Sliding Window MaximumONSITE INTERVIEW · Seen Mar 2026
- Find the Entry of a Linked List CycleONSITE INTERVIEW · Seen Sep 2025
- Integer to English Words: Up to 20 DigitsONSITE INTERVIEW · Seen Sep 2025
- Word Ladder II: All Shortest TransformationsONSITE INTERVIEW · Seen Sep 2025
- Detect a Cycle in a Linked ListONSITE INTERVIEW · Seen May 2025
- First Nonrepeating CharacterONSITE INTERVIEW · Seen May 2025
- Longest Subarray with a Target SumONSITE INTERVIEW · Seen May 2025
Similar questions at other companies
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Minimum Obstacle Removals on a Shortest Grid PathAmazon · ONSITE INTERVIEW
- Longest Matrix Walk with Two-Step ComparisonsGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum All-Ones Square Side LengthOmnissa · ONSITE INTERVIEWOmnissa interview questions
- Enumerate Right-and-Down Matrix PathsOracle · ONSITE INTERVIEWOracle interview questions
- Maximal Square AreaUber · ONSITE INTERVIEWUber interview questions
- Minimum Path SumMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Maximum Grid Path ScoreDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
- Minimum Path SumBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Bomb Enemy Best CoordinatesSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions