FastPrepLongest Increasing Path in a Matrix
Problems/Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix

Nutanix logoNutanix● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The second task in a 2021 Nutanix online coding round for MTS interns asked for the longest path through a grid of numbers. Each move goes to a side neighbor with a bigger number. Any cell can be the first or the last one.

The report gives no grid size, no input format and no example. Here the grid has 1 to 200 rows and 1 to 200 columns. Values stay between 1 and 10^9 as in the report. A path's length counts its cells, so one cell alone has length 1. You get the grid as a 2D array and return the length.

Our version is about 90% the same as the reported question.

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

Examples

Example 1

matrix = [[3,4,5],[2,9,6],[1,8,7]]return = 9
matrix
012034512962187

Start 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 = 1
matrix
01055155

Every 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 = 6

The 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.length
  • m == matrix[i].length
  • 1 <= n, m <= 200
  • 1 <= 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

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        // Write your code here.
    }
}
Checking account…