Length of the Longest Increasing Path solution and explanation
5 more videos on this problem
3288. Length of the Longest Increasing Path (Leetcode Hard)Programming Live with Larry · 27:47 · 422 views
3288. Length of the Longest Increasing Path | Step By Step Solution | Briefly Explained With ExampleCodeNow - By Gopal Gupta · 35:00 · 371 views
Leetcode Biweekly Contest 139 | 3288. Length of the Longest Increasing Path | Binary SearchCodeFod · 15:22 · 228 views
3288. Length of the Longest Increasing Path | Biweekly Contest 139 | LeetcodeAmit Choraria · 20:29 · 177 views
[English] 3288. Length of the Longest Increasing Path Q4 Biweekly 139 [Leetcode Hard]Romain Lhotte · 22:34 · 89 views
LeetCode 3288 - Length of the Longest Increasing Path (Tamanho do Caminho Crescente Mais Longo)Programação Disfuncional · 26:28 · 12 views
The problem
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 + 1andyi < yi + 1for alliwhere1 <= i < m.(xi, yi)is in the given coordinates for alliwhere1 <= 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] <= 109- All elements in
coordinatesare distinct. 0 <= k <= n - 1
Approach overview
Problem 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.
Approach 1: Dynamic Programming with Sorting
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.
def longestIncreasingPath(coordinates, k):
coordinates.sort()
n = len(coordinates)
dp = [1] * n
max_length = 1
for i in range(n):
for j in range(i):
if coordinates[j][0] < coordinates[i][0] and coordinates[j][1] < coordinates[i][1]:
dp[i] = max(dp[i], dp[j] + 1)
if i == k:
max_length = dp[i]
return max_length
coordinates = [[3, 1], [2, 2], [4, 1], [0, 0], [5, 3]]
k = 1
print(longestIncreasingPath(coordinates, k))import java.util.*;
public class LongestIncreasingPath {
public static int longestIncreasingPath(int[][] coords, int k) {
Arrays.sort(coords, (a, b) -> { return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]; });
int n = coords.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int result = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (coords[j][0] < coords[i][0] && coords[j][1] < coords[i][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (i == k) result = dp[i];
}
return result;
}
public static void main(String[] args) {
int[][] coordinates = {{3, 1}, {2, 2}, {4, 1}, {0, 0}, {5, 3}};
int k = 1;
System.out.println(longestIncreasingPath(coordinates, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestIncreasingPath(vector<vector<int>>& coords, int k) {
sort(coords.begin(), coords.end());
int n = coords.size();
vector<int> dp(n, 1);
int result = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (coords[j][0] < coords[i][0] && coords[j][1] < coords[i][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (i == k) result = dp[i];
}
return result;
}
int main() {
vector<vector<int>> coordinates = {{3, 1}, {2, 2}, {4, 1}, {0, 0}, {5, 3}};
int k = 1;
cout << longestIncreasingPath(coordinates, k) << endl;
return 0;
}function longestIncreasingPath(coordinates, k) {
coordinates.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
const n = coordinates.length;
const dp = Array(n).fill(1);
let result = 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (coordinates[j][0] < coordinates[i][0] && coordinates[j][1] < coordinates[i][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (i === k) result = dp[i];
}
return result;
}
const coordinates = [[3, 1], [2, 2], [4, 1], [0, 0], [5, 3]];
const k = 1;
console.log(longestIncreasingPath(coordinates, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
int* p1 = (int*)a;
int* p2 = (int*)b;
if (p1[0] != p2[0])
return p1[0] - p2[0];
return p1[1] - p2[1];
}
int longestIncreasingPath(int** coords, int n, int k) {
qsort(coords, n, sizeof(coords[0]), compare);
int* dp = (int*)calloc(n, sizeof(int));
dp[k] = 1;
int maxLength = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (coords[j][0] < coords[i][0] && coords[j][1] < coords[i][1]) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
if (i == k) maxLength = dp[i];
}
free(dp);
return maxLength;
}
int main() {
int coords[][2] = {{3, 1}, {2, 2}, {4, 1}, {0, 0}, {5, 3}};
int k = 1;
int n = sizeof(coords) / sizeof(coords[0]);
int **pointerCoords = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; ++i) {
pointerCoords[i] = coords[i];
}
int result = longestIncreasingPath(pointerCoords, n, k);
printf("%d\n", result);
free(pointerCoords);
return 0;
}using System;
using System.Linq;
public class Solution {
public static int LongestIncreasingPath(int[][] coords, int k) {
Array.Sort(coords, (a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int n = coords.Length;
int[] dp = Enumerable.Repeat(1, n).ToArray();
int result = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (coords[j][0] < coords[i][0] && coords[j][1] < coords[i][1]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
if (i == k) result = dp[i];
}
return result;
}
public static void Main() {
int[][] coordinates = {
new int[] {3, 1},
new int[] {2, 2},
new int[] {4, 1},
new int[] {0, 0},
new int[] {5, 3}
};
int k = 1;
Console.WriteLine(LongestIncreasingPath(coordinates, k));
}
}This Python solution sorts coordinates and uses a list dp to determine the longest increasing path containing the point at index k. The solution effectively updates path lengths by leveraging sorted order.
The solution has a time complexity of O(n log n) due to sorting. Space complexity is O(n) because of the dp list.
Approach 2: Coordinate Compression with Dynamic Programming
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.
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class BIT {
vector<int> bit;
public:
BIT(int n) : bit(n + 1, 0) {}
void update(int index, int value) {
for (; index < bit.size(); index += index & -index) {
bit[index] = max(bit[index], value);
}
}
int query(int index) {
int maxValue = 0;
for (; index > 0; index -= index & -index) {
maxValue = max(maxValue, bit[index]);
}
return maxValue;
}
};
int longestIncreasingPath(vector<pair<int, int>>& coords, int k) {
int n = coords.size();
vector<int> ys(n);
for (int i = 0; i < n; ++i) ys[i] = coords[i].second;
sort(ys.begin(), ys.end());
unordered_map<int, int> compress;
for (int i = 0; i < n; ++i) {
compress[ys[i]] = i + 1;
}
sort(coords.begin(), coords.end());
BIT bit(n);
int maxLength = 1;
for (int i = 0; i < n; ++i) {
int maxLengthEndingHere = bit.query(compress[coords[i].second] - 1) + 1;
bit.update(compress[coords[i].second], maxLengthEndingHere);
if (i == k) maxLength = maxLengthEndingHere;
}
return maxLength;
}
int main() {
vector<pair<int, int>> coordinates = {{3, 1}, {2, 2}, {4, 1}, {0, 0}, {5, 3}};
int k = 1;
cout << longestIncreasingPath(coordinates, k) << endl;
return 0;
}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.
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.
Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | The solution has a time complexity of |
| Coordinate Compression with Dynamic Programming | This approach has a time complexity of |
Complexity analysis
| 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 |
Frequently asked questions
Is Length of the Longest Increasing Path easy or hard?
Length of the Longest Increasing Path is classified as a Hard problem because it requires recognizing the reduction to a Longest Increasing Subsequence after sorting. Candidates must combine sorting, binary search, and dynamic programming to reach the optimal O(n log n) solution.
Length of the Longest Increasing Path Python/Java solution
Python and Java implementations typically sort the input array and maintain a DP list representing the LIS tails. The built-in binary search utilities such as bisect in Python or Collections.binarySearch in Java help update the structure in logarithmic time.
How to solve Length of the Longest Increasing Path in O(n log n)?
First sort the points by the first coordinate. Then iterate through them while maintaining an array representing the smallest possible tail for increasing subsequences of each length. Use binary search to update the position for each second coordinate value, which keeps the sequence strictly increasing.
What is the best approach for Length of the Longest Increasing Path?
The most efficient solution sorts the points by one coordinate and then computes a Longest Increasing Subsequence (LIS) on the second coordinate. Binary search maintains the LIS structure in O(n log n) time. This approach converts a 2D ordering constraint into a classic LIS problem after sorting.
Is Length of the Longest Increasing Path asked at Google/Amazon/Meta?
Longest increasing sequence variations frequently appear in interviews at companies like Google, Amazon, and Meta. Problems that combine sorting with LIS or dynamic programming are common because they test pattern recognition and algorithm optimization.
What data structure is used in Length of the Longest Increasing Path?
Typical solutions use arrays for dynamic programming along with binary search for LIS updates. Some optimized implementations also use Fenwick Trees or segment trees after coordinate compression to query and update sequence lengths efficiently.
What is the time complexity of Length of the Longest Increasing Path?
The optimal approach runs in O(n log n) time due to sorting and binary search operations during LIS computation. Space complexity is O(n) for the DP structure that tracks the current increasing subsequence.