3288. Length of the Longest Increasing Path Hard

1/**
2 * [3288] Length of the Longest Increasing Path
3 *
4 * You are given a 2D array of integers coordinates of length n and an integer k, where 0 <= k < n.
5 * coordinates[i] = [xi, yi] indicates the point (xi, yi) in a 2D plane.
6 * An increasing path of length m is defined as a list of points (x1, y1), (x2, y2), (x3, y3), ..., (xm, ym) such that:
7 * 
8 * 	xi < xi + 1 and yi < yi + 1 for all i where 1 <= i < m.
9 * 	(xi, yi) is in the given coordinates for all i where 1 <= i <= m.
10 * 
11 * Return the maximum length of an increasing path that contains coordinates[k].
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]], k = 1</span>
16 * Output: <span class="example-io">3</span>
17 * Explanation:
18 * (0, 0), (2, 2), (5, 3)<!-- notionvc: 082cee9e-4ce5-4ede-a09d-57001a72141d --> is the longest increasing path that contains (2, 2).
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">coordinates = [[2,1],[7,0],[5,6]], k = 2</span>
23 * Output: <span class="example-io">2</span>
24 * Explanation:
25 * (2, 1), (5, 6) is the longest increasing path that contains (5, 6).
26 * </div>
27 *  
28 * Constraints:
29 * 
30 * 	1 <= n == coordinates.length <= 10^5
31 * 	coordinates[i].length == 2
32 * 	0 <= coordinates[i][0], coordinates[i][1] <= 10^9
33 * 	All elements in coordinates are distinct.<!-- notionvc: 6e412fc2-f9dd-4ba2-b796-5e802a2b305a --><!-- notionvc: c2cf5618-fe99-4909-9b4c-e6b068be22a6 -->
34 * 	0 <= k <= n - 1
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/length-of-the-longest-increasing-path/
40// discuss: https://leetcode.com/problems/length-of-the-longest-increasing-path/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn max_path_length(coordinates: Vec<Vec<i32>>, k: i32) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_3288() {
58    }
59}
60