Longest Increasing Path in a Matrix
Updated
Problem statement
You are given an n x m grid of integers matrix.
A path is a sequence of cells in which each next cell shares a side with the current one (up, down, left or right, never diagonally) and holds a strictly larger value than the current one. A path can start and end at any cell. Because the values keep growing, a path never visits a cell twice.
The length of a path is the number of cells on it, so a single cell is a path of length 1.
Return the length of the longest path in the grid.
Function
longestIncreasingPath(matrix: int[][]) → intExamples
Example 1
matrix = [[3,4,5],[2,9,6],[1,8,7]]return = 9Start at 1 in the bottom-left corner and go up to 2 and 3, right to 4 and 5, down to 6 and 7, left to 8, and up to 9 in the center.
Every step goes to a side neighbor with a larger value, and the path uses all 9 cells, so the answer is 9.
Example 2
matrix = [[5,5],[5,5]]return = 1Every cell holds 5. A step must go to a strictly larger value, so no step is possible. Each path is a single cell, and the answer is 1.
Example 3
matrix = [[1,2,3,1000000000],[6,5,4,2]]return = 6The longest path is 1 -> 2 -> 3 along the top row, then down to 4, and left to 5 and 6. It has 6 cells.
Stepping from 3 to 1000000000 looks tempting, but no neighbor of that cell is larger, so that path stops there with only 4 cells.
Constraints
n == matrix.lengthm == matrix[i].length1 <= n, m <= 2001 <= matrix[i][j] <= 10^9
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Minimum Cost Path with TeleportationsAmazon · OA
- Shipping Starts and Terminal DestinationsIntuit · OAIntuit interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
- Longest Increasing Path in a MatrixVisa · ONSITE INTERVIEWVisa interview questions
- Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions
- Analyze Underpaid Managers in a Salary TreeGoogle · PHONE SCREENGoogle interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Safest Shortest Path Through a GridSnowflake · OASnowflake interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions