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 <= 105coordinates[i].length == 20 <= coordinates[i][0], coordinates[i][1] <= 109coordinates are distinct.0 <= k <= n - 1Problem Overview: You are given a set of points stored in an array. A valid path requires coordinates to strictly increase as you move forward. The goal is to compute the maximum length of such an increasing path while respecting the ordering constraints between points.
Approach 1: Dynamic Programming with Sorting (O(n log n) time, O(n) space)
Start by sorting the points by their first coordinate. If two points share the same first coordinate, order them carefully so they do not incorrectly extend an increasing sequence. After sorting, the problem reduces to finding a longest increasing sequence based on the second coordinate. Maintain a DP structure similar to the classic Longest Increasing Subsequence. For each point, use binary search to find the position where its second coordinate fits in the current sequence and update the DP array. Sorting enforces the first coordinate constraint, while the LIS step ensures the second coordinate strictly increases. This approach relies heavily on sorting and binary search to achieve an efficient solution.
Approach 2: Coordinate Compression with Dynamic Programming (O(n log n) time, O(n) space)
When coordinates are large or sparse, compress them into a smaller index range before applying dynamic programming. Map each coordinate value to a compressed rank so comparisons remain consistent but memory usage stays small. After compression, process points in sorted order and compute the longest valid sequence ending at each point. A Fenwick Tree or segment tree can query the best previous length for smaller coordinates, then update the current coordinate with the new DP value. Compression avoids large arrays while keeping operations logarithmic. This technique combines array processing with indexed data structures to efficiently track optimal subproblems.
Recommended for interviews: The sorting + LIS style dynamic programming approach is what most interviewers expect. It shows you can recognize when a 2D ordering problem reduces to a 1D LIS after sorting. The coordinate compression variant demonstrates deeper optimization skills when coordinate ranges are large or when using Fenwick/segment tree style DP.
In this approach, we first sort the given points to have them in a potential order to identify increasing paths. We then employ dynamic programming (DP) to determine the longest path that includes a specific point by storing the maximum path length terminating at each point. This is done by iteratively updating the path lengths based on previously computed DP values for eligible preceding points.
This C solution sorts the coordinates array based on x and y values and uses a dynamic programming array dp to store the longest increasing path up to each point. We then determine the maximum at point k.
The time complexity is dominated by the sorting step, O(n log n). Space complexity is O(n) due to the dynamic programming array.
Instead of directly comparing each pair of coordinates, this approach uses coordinate compression to map each coordinate to a potentially reduced range. This helps optimize the process of updating the longest paths using a sweep line technique and binary indexed tree (BIT) for efficiently querying and updating the longest increasing sequences.
In this C++ solution, coordinate compression maps y-values to a new domain to manage their size in a binary indexed tree (BIT). Subsequently, the BIT is used to efficiently maintain and query the longest increasing sequences up to each compressed y-value.
C++
This approach has a time complexity of O(n log n) due to sorting and BIT updates. Space complexity is O(n) because of BIT and map storage.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | The time complexity is dominated by the sorting step, |
| Coordinate Compression with Dynamic Programming | This approach has a time complexity of |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Sorting (LIS style) | O(n log n) | O(n) | General case where points can be sorted and LIS can be applied on one dimension |
| Coordinate Compression + DP (Fenwick/Segment Tree) | O(n log n) | O(n) | When coordinate values are large and require efficient indexed queries |
3288. Length of the Longest Increasing Path (Leetcode Hard) • Programming Live with Larry • 421 views views
Watch 5 more video solutions →Practice Length of the Longest Increasing Path with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor