Longest Matrix Walk with Two-Step Comparisons
Updated
Problem statement
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[][]) → intExamples
Example 1
grid = [[3,1,2]]return = 4The 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 = 1Every 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 = 5A 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 <= 12for 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