Length of the Longest Increasing Path

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

Examples

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 <= 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

Solution

Method 1 – Dynamic Programming with Coordinate Sorting

Intuition

We want the longest path of points where both x and y strictly increase, and the path must include coordinates[k]. This is a 2D variant of the Longest Increasing Subsequence (LIS) problem. We can sort the points, use DP to track the longest path ending at each point, and ensure the path includes the required point.

Approach

1. Sort the coordinates by x, then by y.
2. For each point, use DP to find the longest increasing path ending at that point:
   • For each previous point with both x and y less, update the current DP value.
3. Track the maximum path length for all paths that include coordinates[k].
4. Return the maximum such length.

Code

C++

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& coordinates, int k) {
        int n = coordinates.size();
        vector<pair<int,int>> pts;
        for (auto& p : coordinates) pts.emplace_back(p[0], p[1]);
        sort(pts.begin(), pts.end());
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (pts[j].first < pts[i].first && pts[j].second < pts[i].second)
                    dp[i] = max(dp[i], dp[j]+1);
            }
        }
        // Find all indices matching coordinates[k]
        for (int i = 0; i < n; ++i) {
            if (pts[i].first == coordinates[k][0] && pts[i].second == coordinates[k][1])
                ans = max(ans, dp[i]);
        }
        return ans;
    }
};

Go

func longestIncreasingPath(coordinates [][]int, k int) int {
    n := len(coordinates)
    pts := make([][2]int, n)
    for i, p := range coordinates {
        pts[i] = [2]int{p[0], p[1]}
    }
    sort.Slice(pts, func(i, j int) bool {
        if pts[i][0] == pts[j][0] { return pts[i][1] < pts[j][1] }
        return pts[i][0] < pts[j][0]
    })
    dp := make([]int, n)
    for i := range dp { dp[i] = 1 }
    ans := 1
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if pts[j][0] < pts[i][0] && pts[j][1] < pts[i][1] {
                if dp[j]+1 > dp[i] { dp[i] = dp[j]+1 }
            }
        }
    }
    for i := 0; i < n; i++ {
        if pts[i][0] == coordinates[k][0] && pts[i][1] == coordinates[k][1] {
            if dp[i] > ans { ans = dp[i] }
        }
    }
    return ans
}

Java

class Solution {
    public int longestIncreasingPath(int[][] coordinates, int k) {
        int n = coordinates.length;
        int[][] pts = new int[n][2];
        for (int i = 0; i < n; i++) pts[i] = coordinates[i];
        Arrays.sort(pts, (a, b) -> a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pts[j][0] < pts[i][0] && pts[j][1] < pts[i][1])
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        for (int i = 0; i < n; i++) {
            if (pts[i][0] == coordinates[k][0] && pts[i][1] == coordinates[k][1])
                ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun longestIncreasingPath(coordinates: Array<IntArray>, k: Int): Int {
        val n = coordinates.size
        val pts = coordinates.map { it.copyOf() }.sortedWith(compareBy({it[0]}, {it[1]}))
        val dp = IntArray(n) { 1 }
        var ans = 1
        for (i in 0 until n) {
            for (j in 0 until i) {
                if (pts[j][0] < pts[i][0] && pts[j][1] < pts[i][1])
                    dp[i] = maxOf(dp[i], dp[j]+1)
            }
        }
        for (i in 0 until n) {
            if (pts[i][0] == coordinates[k][0] && pts[i][1] == coordinates[k][1])
                ans = maxOf(ans, dp[i])
        }
        return ans
    }
}

Python

class Solution:
    def longestIncreasingPath(self, coordinates: list[list[int]], k: int) -> int:
        n = len(coordinates)
        pts = sorted(coordinates)
        dp = [1]*n
        for i in range(n):
            for j in range(i):
                if pts[j][0] < pts[i][0] and pts[j][1] < pts[i][1]:
                    dp[i] = max(dp[i], dp[j]+1)
        ans = 1
        for i in range(n):
            if pts[i][0] == coordinates[k][0] and pts[i][1] == coordinates[k][1]:
                ans = max(ans, dp[i])
        return ans

Rust

impl Solution {
    pub fn longest_increasing_path(coordinates: Vec<Vec<i32>>, k: usize) -> i32 {
        let n = coordinates.len();
        let mut pts: Vec<(i32,i32)> = coordinates.iter().map(|p| (p[0], p[1])).collect();
        pts.sort();
        let mut dp = vec![1; n];
        for i in 0..n {
            for j in 0..i {
                if pts[j].0 < pts[i].0 && pts[j].1 < pts[i].1 {
                    dp[i] = dp[i].max(dp[j]+1);
                }
            }
        }
        let mut ans = 1;
        for i in 0..n {
            if pts[i].0 == coordinates[k][0] && pts[i].1 == coordinates[k][1] {
                ans = ans.max(dp[i]);
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    longestIncreasingPath(coordinates: number[][], k: number): number {
        const n = coordinates.length;
        const pts = [...coordinates].sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        const dp = new Array(n).fill(1);
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < i; j++) {
                if (pts[j][0] < pts[i][0] && pts[j][1] < pts[i][1])
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        let ans = 1;
        for (let i = 0; i < n; i++) {
            if (pts[i][0] === coordinates[k][0] && pts[i][1] === coordinates[k][1])
                ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2), where n is the number of points (for each point, we may check all previous points).
• 🧺 Space complexity: O(n), for the dp array.