#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