FastPrepLongest Matrix Walk with Two-Step Comparisons
Problems/Longest Matrix Walk with Two-Step Comparisons

Longest Matrix Walk with Two-Step Comparisons

Google logoGoogle● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report calls this a 'matrix dump' exercise. It gives the rule of moving to a value smaller than the current or previous one, plus an optimization from DFS to DP. The name may be a typo, and we do not assume a known problem. Our version is about 50% the same as the reported question. The report leaves out several things, so we chose them: maximize the walk length, move only up, down, left, or right, any cell can be the start, the rule for the first move, whether revisits are allowed, a single number as the output, and the input limits.

Given a nonempty rectangular integer matrix grid, find the maximum number of cell visits in a walk under the following rules. The starting cell and every later visit each contribute 1 to the length.

For this exercise, assume you may start at any cell and may stop at any time. Each move goes to one cell immediately above, below, left, or right, within the matrix. You may revisit a cell, including the cell just left, whenever the value rule permits it. The matrix is never modified.

The first move must go to a value strictly smaller than the starting value. For each later move, let previous be the value at the cell visited immediately before the current cell, let current be the current value, and let next be the destination value. The move is legal exactly when next < current OR next < previous. The comparisons are strict, and either one is enough. This rule may allow an increase relative to the current cell.

Return only the largest possible length as an integer, counting all visits, including revisits. A walk containing just its starting cell has length 1. No path or tie-breaking order is returned. Every valid input has a finite answer under these rules.

Function

longestTwoStepMatrixWalk(grid: int[][]) → int

Examples

Example 1

grid = [[3,1,2]]return = 4
grid
0120312

The walk visits columns 0, 1, 2, 1, with values 3 → 1 → 2 → 1. The move from 1 to 2 is legal because 2 is smaller than the previous value 3. The last visit repeats column 1. No length-5 walk is legal.

Example 2

grid = [[7,7],[7,7]]return = 1
grid
01077177

Every possible move goes to an equal value, so no first move is legal. Starting and stopping at any one cell gives length 1.

Example 3

grid = [[5,1],[2,0]]return = 5
grid
01051120

A maximum walk has values 5 → 2 → 0 → 1 → 0. It revisits the zero-valued cell; the move from 0 to 1 is permitted by the previous value 2. The maximum is 5.

Constraints

  • 1 <= grid.length <= 12.
  • 1 <= grid[r].length <= 12 for every row.
  • All rows have the same length.
  • The total number of cells is at most 12.
  • -1000 <= grid[r][c] <= 1000.

More Google Onsite Interview questions

  • Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
  • Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
  • Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions
  • Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
  • Mouse and Cheese ReachabilityMeta · ONSITE INTERVIEWMeta interview questions
  • Number of IslandsTripjack · ONSITE INTERVIEWTripjack interview questions
  • Number of IslandsTekion · ONSITE INTERVIEWTekion interview questions
  • Grid Pathfinding with Obstacles (DFS)Roblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
  • Number of IslandsGoldman Sachs · OA · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
  • Number of IslandsBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Number of IslandsCrowdstrike · ONSITE INTERVIEWCrowdstrike interview questions

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
  • Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int longestTwoStepMatrixWalk(int[][] grid) {
        // Write your code here.
    }
}
Checking account…