Longest Increasing Path In a Matrix

The problem

You are given matrix, a grid of numbers with at least one cell. A path starts at any cell and moves one cell at a time: up, down, left or right, never diagonally and never off the grid. Every move must go to a cell with a strictly larger value, so a path cannot step between two equal values. Return the number of cells on the longest such path. A single cell counts as a path of length 1.

What to write

function solve(matrix: number[][]): number

Input
matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output
4

Input
matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output
4

Constraints

The matrix is nonempty; equal-valued moves are not allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every move goes to a strictly larger value. So a path can never return to a cell it has left: that cell holds a smaller value. You do not need to keep track of where the current path has been, and no path can go round in a circle.

2. Hint 2: Ask a smaller question

   In example 1, find by hand the longest path that starts at the 6 in the left column. Then find the longest path that starts at the 2 below it. Did you have to search from the 6 a second time, or could you use what you already knew?

3. Hint 3: Name the pattern

   Many paths run through the same cell, and the longest path from a cell does not depend on how you reached it. So every cell has one fixed answer, built from its larger neighbors' answers. Work each answer out once and keep it in a slot for that cell. A grid of stored answers like this is two-dimensional dynamic programming. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   A filled slot holds the number of cells on the longest increasing path that starts at that cell. The rule: 1 if no neighbor is larger, otherwise 1 plus the largest slot among the larger neighbors. A slot is filled once and never changes.

5. Hint 5: Sketch the pseudocode

   longest(cell): if the cell's slot is filled, return it. Set best = 1. For each of the four neighbors that lies inside the grid and holds a larger value: best = max(best, 1 + longest(neighbor)). Put best in the slot and return it. The answer is the largest longest(cell) over all cells.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Increasing edges cannot form a cycle. Memoize the longest path starting at each cell.

The slow way

From every cell, follow every increasing path to its end and keep the longest. It is correct, but the same stretch of path is walked again for every path that leads into it. On a 10 by 10 grid that holds 1 to 100 row by row, this search is called 705,310 times. With stored answers it is called 280 times.

The insight

A path's first move goes to a larger neighbor, and what follows is a path that starts at that neighbor. So the longest path from a cell is 1 plus the longest path from its best larger neighbor, if it has one. That number does not depend on how you arrived, so it can be worked out once, stored and reused. Storing a function's answers like this is called memoization.

Step by step

1. Keep one slot per cell for the longest path that starts there. A slot holds the number of cells on the longest path that starts at its cell, which is the same whoever asks. A slot holding 0 means not worked out yet: safe, because every real length is at least 1.
2. Asked about a cell, return what its slot holds if it is filled. A filled slot already holds the final answer for that cell. Returning it at once is what keeps any cell from being searched a second time.
3. Otherwise begin with the path that is this cell alone: length 1. The length counts cells, not moves, and a cell by itself is already a path. For a cell with no larger neighbor this 1 is also the final answer.
4. Each larger neighbor gives a path one longer than its own best. A move goes up, down, left or right to a strictly larger value. Stepping to such a neighbor and then following its longest path gives this cell plus that path. The longest of these wins.
5. Fill the slot with the best length found and return it. Every larger neighbor has been tried, so the length is final. Once it is stored, the next question about this cell is answered without any searching.
6. Ask about every cell and return the largest answer. The longest path may start anywhere, and one question only covers paths that start at its own cell. A cell that an earlier question already reached returns its slot at once.

The same numbered steps are the comments in each solution.

function solve(matrix) {
  // 1. Keep one slot per cell for the longest path that starts there
  const memo = matrix.map((row) => row.map(() => 0));
  // 2. Asked about a cell, return what its slot holds if it is filled
  function visit(r, c) {
    if (memo[r][c]) return memo[r][c];
    // 3. Otherwise begin with the path that is this cell alone: length 1
    let best = 1;
    // 4. Each larger neighbor gives a path one longer than its own best
    // A neighbor off the grid reads as undefined and is skipped.
    for (const [a, b] of [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ])
      if (matrix[a]?.[b] !== undefined && matrix[a][b] > matrix[r][c])
        best = Math.max(best, 1 + visit(a, b));
    // 5. Fill the slot with the best length found and return it
    return (memo[r][c] = best);
  }
  // 6. Ask about every cell and return the largest answer
  let best = 0;
  for (let r = 0; r < matrix.length; r++)
    for (let c = 0; c < matrix[0].length; c++)
      best = Math.max(best, visit(r, c));
  return best;
}

function solve(matrix: number[][]): number {
  // 1. Keep one slot per cell for the longest path that starts there
  const memo = matrix.map((row) => row.map(() => 0));
  // 2. Asked about a cell, return what its slot holds if it is filled
  function visit(r: number, c: number): number {
    if (memo[r][c]) return memo[r][c];
    // 3. Otherwise begin with the path that is this cell alone: length 1
    let best = 1;
    // 4. Each larger neighbor gives a path one longer than its own best
    // A neighbor off the grid reads as undefined and is skipped.
    for (const [a, b] of [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ])
      if (matrix[a]?.[b] !== undefined && matrix[a][b] > matrix[r][c])
        best = Math.max(best, 1 + visit(a, b));
    // 5. Fill the slot with the best length found and return it
    return (memo[r][c] = best);
  }
  // 6. Ask about every cell and return the largest answer
  let best = 0;
  for (let r = 0; r < matrix.length; r++)
    for (let c = 0; c < matrix[0].length; c++)
      best = Math.max(best, visit(r, c));
  return best;
}

def solve(matrix):
    # 1. Keep one slot per cell for the longest path that starts there
    rows, cols = len(matrix), len(matrix[0])
    memo = [[0] * cols for _ in range(rows)]

    # 2. Asked about a cell, return what its slot holds if it is filled
    def visit(r, c):
        if memo[r][c]:
            return memo[r][c]
        # 3. Otherwise begin with the path that is this cell alone: length 1
        best = 1
        # 4. Each larger neighbor gives a path one longer than its own best
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            # A negative index would read from the far edge of the grid,
            # so the neighbor is first checked to lie inside it.
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + visit(nr, nc))
        # 5. Fill the slot with the best length found and return it
        memo[r][c] = best
        return best

    # 6. Ask about every cell and return the largest answer
    return max(visit(r, c) for r in range(rows) for c in range(cols))

Example 2, traced

Input
matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output
4

Why it works

A question about a cell only asks about neighbors with larger values. So a chain of questions keeps climbing and can never reach a cell that is still waiting for its own answer. The chain stops at a cell with no larger neighbor, whose answer is 1. Every other slot is then filled from slots that are already final: 1 plus the best of them.

Time and space

Time O(rows · cols), extra space O(rows · cols). Each cell is worked out once. After that its slot answers at once. Working a cell out looks at four neighbors, so the time is O(rows · cols). There is one slot per cell, and unfinished calls can pile up as long as the longest path: O(rows · cols) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• A move needs a strictly larger value. If an equal value is accepted too, the two 9s of example 1 ask about each other before either slot is filled. The calls never end and the program crashes.
• Do not mark cells as visited and refuse to enter them again, as a search for islands does. A cell reached a second time must return its slot. With that marking, example 1 gives 2 instead of 4.
• Count cells, not moves. Starting a cell at 0 instead of 1 makes every answer one too small: example 1 gives 3, and a grid of one cell gives 0.

Pattern

Two-dimensional dynamic programming. Builds on Word Search and Unique Paths.

Keep going