3288. Length of the Longest Increasing Path

Posted on Edited on In

3288. Length of the Longest Increasing Path

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].

Example 1:

1
2
3
Input: coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]], k = 1

Output: 3

Explanation:

(0, 0), (2, 2), (5, 3) is the longest increasing path that contains (2, 2).

Example 2:

1
2
3
Input: coordinates = [[2,1],[7,0],[5,6]], k = 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

Hints/Notes

Solution

Language: C++

Cleaner solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxPathLength(vector<vector<int>>& coordinates, int k) {
        int n = coordinates.size();
        auto cmp = [](vector<int>& lhs, vector<int>& rhs) {
            if (lhs[0] != rhs[0]) {
                return lhs[0] < rhs[0];
            }
            return lhs[1] > rhs[1];
        };
        vector<int> y_coordinates;
        int kx = coordinates[k][0], ky = coordinates[k][1];
        sort(coordinates.begin(), coordinates.end(), cmp);
        for (int i = 0; i < n; i++) {
            int x = coordinates[i][0], y = coordinates[i][1];
            if ((x < kx && y < ky) || (x > kx && y > ky)) {
                auto it = ranges::lower_bound(y_coordinates, y);
                if (it == y_coordinates.end()) {
                    y_coordinates.push_back(y);
                } else {
                    *it = y;
                }
            }
        }
        return y_coordinates.size() + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int maxPathLength(vector<vector<int>>& coordinates, int k) {
        int n = coordinates.size();
        vector<int> nums;
        int xIndex = -1, yIndex = -1;
        for (int i = 0; i < n; i++) {
            coordinates[i] = {coordinates[i][0], coordinates[i][1], i};
        }
        auto cmp = [](vector<int>& lhs, vector<int>& rhs) {
            if (lhs[0] != rhs[0]) {
                return lhs[0] < rhs[0];
            }
            return lhs[1] > rhs[1];
        };
        sort(coordinates.begin(), coordinates.end(), cmp);
        for (int i = 0; i < n; i++) {
            int x = coordinates[i][1], idx = coordinates[i][2];
            int index = binarySearch(nums, x);
            if (index == nums.size()) {
                nums.push_back(x);
            } else {
                nums[index] = x;
            }
            if (idx == k) {
                xIndex = index;
                break;
            }
        }
        nums.clear();
        for (int i = n - 1; i >= 0; i--) {
            int x = -coordinates[i][1], idx = coordinates[i][2];
            int index = binarySearch(nums, x);
            if (index == nums.size()) {
                nums.push_back(x);
            } else {
                nums[index] = x;
            }
            if (idx == k) {
                yIndex = index;
                break;
            }
        }
        return xIndex + yIndex + 1;
    }

    int binarySearch(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] > target) {
                r = mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        return l;
    }
};