FastPrepMaximum Falling Path Sum in a Rectangle
Problems/Maximum Falling Path Sum in a Rectangle

Maximum Falling Path Sum in a Rectangle

PeopleStrong logoPeopleStrong● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a PeopleStrong onsite interview. The technical-round task asks for the largest falling sum in a rectangular matrix, moving down or diagonally. We chose that values can be negative, the limits, and the function interface. Our version is about 95% the same as the reported question.

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[][]) → int

Examples

Example 1

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

A path can take 3, then 8, then 6 for a total of 17.

Example 2

grid = [[-5,-2],[-3,-4]]return = -5
grid
010-5-21-3-4

Choose -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

Interview reports that mention this question

  • PeopleStrong SDE OA and Interview Questions: 12 Experiences
All PeopleStrong interview questionsSee PeopleStrong hiring insights
Saved
class Solution {
    public int maximumFallingPath(int[][] grid) {
        // Write your solution here.
    }
}
Checking account…