3288. Length of the Longest Increasing Path LeetCode Solution

In this guide, you will get 3288. Length of the Longest Increasing Path LeetCode Solution with the best time and space complexity. The solution to Length of the Longest Increasing Path problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Length of the Longest Increasing Path solution in C++
4. Length of the Longest Increasing Path solution in Java
5. Length of the Longest Increasing Path solution in Python
6. Additional Resources

Problem Statement of Length of the Longest Increasing Path

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:

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:

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 <= 105
coordinates[i].length == 2
0 <= coordinates[i][0], coordinates[i][1] <= 109
All elements in coordinates are distinct.
0 <= k <= n – 1

Complexity Analysis

• Time Complexity: O(n\log n)
• Space Complexity: O(n)

3288. Length of the Longest Increasing Path LeetCode Solution in C++

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) {
      return pair<int, int>{coordinate.first, -coordinate.second};
    });
    // 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();
  }
};
/* code provided by PROGIEZ */

3288. Length of the Longest Increasing Path LeetCode Solution in Java

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(
        (a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));
    // 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;
  }
}
// code provided by PROGIEZ

3288. Length of the Longest Increasing Path LeetCode Solution in Python

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)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.