Skip to content

3288. Length of the Longest Increasing Path 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int maxPathLength(vector<vector<int>>& coordinates, int k) {
    const int xk = coordinates[k][0];
    const int yk = coordinates[k][1];
    vector<pair<int, int>> leftCoordinates;
    vector<pair<int, int>> rightCoordinates;

    for (const vector<int>& coordinate : coordinates) {
      const int x = coordinate[0];
      const int y = coordinate[1];
      if (x < xk && y < yk)
        leftCoordinates.emplace_back(x, y);
      else if (x > xk && y > yk)
        rightCoordinates.emplace_back(x, y);
    }

    return 1 + lengthOfLIS(leftCoordinates) + lengthOfLIS(rightCoordinates);
  }

 private:
  // Similar to 300. Longest Increasing Subsequence
  int lengthOfLIS(vector<pair<int, int>>& coordinates) {
    ranges::sort(coordinates, ranges::less{},
                 [](const pair<int, int>& coordinate) {
      const auto& [x, y] = coordinate;
      return pair<int, int>{x, -y};
    });
    // tails[i] := the minimum tail of all the increasing subsequences having
    // length i + 1
    vector<int> tails;
    for (const auto& [_, y] : coordinates)
      if (tails.empty() || y > tails.back())
        tails.push_back(y);
      else
        tails[firstGreaterEqual(tails, y)] = y;
    return tails.size();
  }

  int firstGreaterEqual(const vector<int>& arr, int target) {
    return ranges::lower_bound(arr, target) - arr.begin();
  }
};

 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
class Solution {
  public int maxPathLength(int[][] coordinates, int k) {
    final int xk = coordinates[k][0];
    final int yk = coordinates[k][1];
    List<int[]> leftCoordinates = new ArrayList<>();
    List<int[]> rightCoordinates = new ArrayList<>();

    for (int[] coordinate : coordinates) {
      final int x = coordinate[0];
      final int y = coordinate[1];
      if (x < xk && y < yk)
        leftCoordinates.add(new int[] {x, y});
      else if (x > xk && y > yk)
        rightCoordinates.add(new int[] {x, y});
    }

    return 1 + lengthOfLIS(leftCoordinates) + lengthOfLIS(rightCoordinates);
  }

  // Similar to 300. Longest Increasing Subsequence
  private int lengthOfLIS(List<int[]> coordinates) {
    coordinates.sort(Comparator.comparingInt((int[] coordinate) -> coordinate[0])
                         .thenComparingInt((int[] coordinate) -> - coordinate[1]));
    // tails[i] := the minimum tail of all the increasing subsequences having
    // length i + 1
    List<Integer> tails = new ArrayList<>();
    for (int[] coordinate : coordinates) {
      final int y = coordinate[1];
      if (tails.isEmpty() || y > tails.get(tails.size() - 1))
        tails.add(y);
      else
        tails.set(firstGreaterEqual(tails, y), y);
    }
    return tails.size();
  }

  private int firstGreaterEqual(List<Integer> arr, int target) {
    final int i = Collections.binarySearch(arr, target);
    return i < 0 ? -i - 1 : i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def maxPathLength(self, coordinates: list[list[int]], k: int) -> int:
    xk, yk = coordinates[k]
    leftCoordinates = [(x, y) for x, y in coordinates if x < xk and y < yk]
    rightCoordinates = [(x, y) for x, y in coordinates if x > xk and y > yk]
    return (1 +
            self._lengthOfLIS(leftCoordinates) +
            self._lengthOfLIS(rightCoordinates))

  # Similar to 300. Longest Increasing Subsequence
  def _lengthOfLIS(self, coordinates: list[tuple[int, int]]) -> int:
    coordinates.sort(key=lambda x: (x[0], -x[1]))
    # tail[i] := the minimum tail of all the increasing subsequences having
    # length i + 1
    tail = []
    for _, y in coordinates:
      if not tail or y > tail[-1]:
        tail.append(y)
      else:
        tail[bisect.bisect_left(tail, y)] = y
    return len(tail)