Coding · Graphs and grids
Longest increasing path in a matrix
- Reported in several places
- Hard
- Senior SWE (3 years, offer) and SDE-1 (entry level)
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Given a grid of integers, find the length of the longest path in which every step moves up, down, left or right to a cell holding a strictly larger value. A path may start in any cell and may not leave the grid, and the answer counts the cells on the path. For [[9,9,4],[6,6,8],[2,1,1]] the answer is 4, from the path 1, 2, 6, 9. The grid can have a few hundred rows and columns. Two candidate reports about a year apart mention it, and one candidate started from plain depth-first search and added memoisation when pushed.
Restated in our own words, not a quote from Myntra or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would check the move rules and the output. Are the moves only up, down, left and right, or also diagonal? Must each step go to a strictly larger value, so that equal neighbours do not count? Can the path start anywhere? Do I return the number of cells on the path or the number of steps? What do I return for an empty grid? And how big can the grid be, because that decides between recursion and an iterative method?
My reading: four directions, strictly larger, any start cell, the answer is the number of cells, 0 for an empty grid, and the grid may be a few hundred cells on a side, so I avoid deep recursion.
Brute force
Say the obvious answer and why it is too slow.
Start a depth-first search from every cell: from a cell, try each of its four neighbours holding a larger value, and return one plus the best result. The path cannot loop because values strictly grow, so no visited set is needed. Take the maximum over all start cells.
This is correct, but it recounts the same paths. A cell can be reached by many different increasing paths, and each time the whole tail above it is explored again. On a grid where values grow to the right and downwards the number of increasing paths is a binomial coefficient, exponential in the grid size, so even a 20 by 20 grid is out of reach. One candidate report describes starting here and adding memoisation when pushed.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- Exponential in the grid size without memoisation
- Time
- O(m * n) for an m by n grid
- Space
- O(m * n)
The pattern is longest path in an implicit DAG, solved in topological order. Draw an edge from every cell to each neighbour with a strictly larger value. Edges only go upwards in value, so there are no cycles, and the longest increasing path is the longest path in this DAG. Nothing needs to be built: the edges are implied by the grid.
There are two standard ways to evaluate it. The first is memoised DFS: longest(cell) = 1 + the maximum of longest(neighbour) over larger neighbours, stored per cell, so each cell is computed once and the time is O(m * n). Its weak point is depth: on a snake-shaped grid the recursion goes as deep as the number of cells, and a 200 by 200 grid is 40,000 frames, which can overflow the JavaScript stack.
The second, which I ship, is Kahn's algorithm in layers. For each cell count its smaller neighbours: that is its in-degree. Cells with in-degree 0 are local minima and form layer 1. Peel a layer: for each cell in it, decrement the count of every larger neighbour, and any neighbour reaching 0 joins the next layer. The number of layers is the answer. A cell lands in layer t exactly when the longest increasing path that ends at it has t cells: it is released when its last smaller neighbour is peeled, which is one layer after the deepest of its smaller neighbours. The last layer therefore holds the ends of the longest paths.
Time is O(m * n), since each cell and each of its four neighbour checks happens a constant number of times, and space is O(m * n) for the counts and the layers. Out loud: "cells point to bigger neighbours, so it is a DAG; peel it layer by layer and count the layers."
Walk it through
A dry run on the example, step by step.
| Layer | Cells peeled | Cells released |
|---|---|---|
| 1 | 4@(0,2) 1@(2,1) 1@(2,2) | 6@(1,1) 2@(2,0) |
| 2 | 6@(1,1) 2@(2,0) | 9@(0,1) 8@(1,2) 6@(1,0) |
| 3 | 9@(0,1) 8@(1,2) 6@(1,0) | 9@(0,0) |
| 4 | 9@(0,0) | none |
Take [[9,9,4],[6,6,8],[2,1,1]] and count smaller neighbours first. The cells with none are the 4 in the top right and the two 1s in the bottom row, which form layer 1. Peeling them releases the 6 in the middle and the 2 at the bottom left, because their only smaller neighbour was a 1. The 8 and the top middle 9 still wait on other cells, so layer 2 is the 6 and the 2.
Peeling layer 2 releases the 9 at the top middle (its smaller neighbours 4 and 6 are both done), the 8 (its smaller neighbours 4, 6 and 1 are done), and the 6 on the left (the 2 is done), so layer 3 has those three. Peeling layer 3 releases the 9 in the top left corner, which waited on the left 6. That corner is layer 4, and peeling it releases nothing, so there are 4 layers and the answer is 4, matching the path 1, 2, 6, 9.
The code
Runnable JavaScript, checked against test cases.
function longestIncreasingPath(matrix) {
const rows = matrix.length;
if (rows === 0) return 0;
const cols = matrix[0].length;
const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const smaller = new Array(rows * cols).fill(0);
let layer = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
for (const [dr, dc] of moves) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] < matrix[r][c]) smaller[r * cols + c]++;
}
if (smaller[r * cols + c] === 0) layer.push(r * cols + c);
}
}
let length = 0;
while (layer.length > 0) {
length++;
const next = [];
for (const cell of layer) {
const r = Math.floor(cell / cols);
const c = cell % cols;
for (const [dr, dc] of moves) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] <= matrix[r][c]) continue;
smaller[nr * cols + nc]--;
if (smaller[nr * cols + nc] === 0) next.push(nr * cols + nc);
}
}
layer = next;
}
return length;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty grid, or a grid whose rows are empty, has no cells, so the answer is 0 and the loop never starts. A one-cell grid gives 1. A grid with all values equal gives 1, because no step is strictly larger.
- Plateaus: equal neighbours add no edge and no in-degree, so a flat region with no smaller neighbours sits entirely in layer 1.
- Single row or column: works the same way; a decreasing column gives its full length by walking from the bottom up.
- Negative values: only comparisons are used.
- Non-square grids: a cell index is row times column count plus column, so rows and columns are never mixed up.
- Snake grids: the layer count equals the cell count, and nothing recurses.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the path itself, not only its length?
- How would you count how many longest paths there are?
- What breaks if equal neighbours are allowed as steps, and what would you do?
- How would you handle diagonal moves, or a weight on each step?
- Memoised DFS is shorter to write, so when would you still choose the layered version, and can you make the DFS safe from stack overflow?
Where candidates slip
The mistakes this problem punishes.
The most frequent slip is allowing equal neighbours (using at-least rather than strictly larger), which creates cycles and an infinite loop or wrong lengths. Next is a visited set shared across start cells, which blocks paths that legitimately pass through a cell from a different start; with memoisation no visited set is needed because the order is acyclic.
Others: clearing the memo for each start cell, which brings back the exponential cost; returning the number of steps instead of the number of cells; starting only from corners or from the smallest value; mixing up rows and columns on a non-square grid; and writing the recursive version without considering depth on a large snake grid.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.