2 Output: 2 Explanation: `(2, 1)`, `(5, 6)` is the longest increasing path that contains `(5, 6)`.

Constraints

1 <= n == coordinates.length <= 10^5
coordinates[i].length == 2
0 <= coordinates[i][0], coordinates[i][1] <= 10^9
All elements in coordinates are distinct.
0 <= k <= n - 1

Solution

Method 1 – Dynamic Programming with Coordinate Sorting

Intuition

We want the longest path of points where both x and y strictly increase, and the path must include coordinates[k]. This is a 2D variant of the Longest Increasing Subsequence (LIS) problem. We can sort the points, use DP to track the longest path ending at each point, and ensure the path includes the required point.

Approach

Sort the coordinates by x, then by y.
For each point, use DP to find the longest increasing path ending at that point:
- For each previous point with both x and y less, update the current DP value.
Track the maximum path length for all paths that include coordinates[k].
Return the maximum such length.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int longestIncreasingPath(vector<vector<int>>& coordinates, int k) {\n        int n = coordinates.size();\n        vector<pair<int,int>> pts;\n        for (auto& p : coordinates) pts.emplace_back(p[0], p[1]);\n        sort(pts.begin(), pts.end());\n

Related Tags