#3288
Length of the Longest Increasing Path
hard · 19.2% accepted · 102 likes · top 1%
array · binary search · sorting
Description
You are given a 2D array of integers coordinates of length n and an integer k, where 0 <= k < n.coordinates[i] = [xi, yi] indicates the point (xi, yi) in a 2D plane.
An increasing path of length m is defined as a list of points (x1, y1), (x2, y2), (x3, y3), ..., (xm, ym) such that:
- xi < xi + 1 and yi < yi + 1 for all i where 1 <= i < m.
- (xi, yi) is in the given coordinates for all i where 1 <= i <= m.
Return the maximum length of an increasing path that contains coordinates[k].
Solution