Hard

Length of the Longest Increasing Path

LAB

Given a matrix, return the length of the longest path moving 4-directionally to strictly larger values.

EXAMPLES

Example 1

Input
{
  "matrix": [
    [
      9,
      9,
      4
    ],
    [
      6,
      6,
      8
    ],
    [
      2,
      1,
      1
    ]
  ]
}

Output
4

FUNCTION SHAPE

matrix: intMatrix→int

SOLUTION NOTE

Split points into before/after k. Find 2D LIS in each part using sort + patience sort on y-values.

Reveal reference solution +

pythonREFERENCE

def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
    n = len(coordinates)
    kx, ky = coordinates[k]

    # Split into before k and after k
    before = [(x, y) for x, y in coordinates if x < kx and y < ky]
    after = [(x, y) for x, y in coordinates if x > kx and y > ky]

    def lis_2d(points):
        if not points:
            return 0
        points.sort(key=lambda p: (p[0], -p[1]))
        from sortedcontainers import SortedList
        sl = SortedList()
        for x, y in points:
            idx = sl.bisect_left(y)
            if idx < len(sl):
                sl.pop(idx)
            sl.add(y)
        return len(sl)

    return 1 + lis_2d(before) + lis_2d(after)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗