Scale Engineer

Length of the Longest Increasing Path

Hard
#2919Time: Exponential, roughly O(N!). For each node, we might branch out to N-1 other nodes, leading to a factorial-like complexity in the worst case.Space: O(N), for the recursion stack depth in the worst case (a single long chain).
Algorithms
Binary SearchSorting
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach models the problem as finding the longest path in a graph. Each coordinate is a node, and a directed edge exists from point A to point B if B can follow A in an increasing path. The length of the longest path passing through a specific point k is the sum of the longest path ending at k and the longest path starting from k, minus one. We can use simple recursion to find these two lengths. For each point, the function explores all possible preceding or succeeding points, leading to an exponential number of calls.

Algorithm

  • Model the problem as finding the longest path in a Directed Acyclic Graph (DAG), where points are nodes and an edge exists from point i to j if x_i < x_j and y_i < y_j.
  • The length of the longest path through coordinates[k] is the length of the longest path ending at k plus the length of the longest path starting from k, minus one (to not double-count k).
  • Define a recursive function, findLongestEndingAt(i), to compute the length of the longest increasing path ending at coordinates[i].
  • Inside findLongestEndingAt(i), initialize maxLength = 1.
  • Iterate through all other points j. If coordinates[j] can precede coordinates[i], update maxLength = max(maxLength, 1 + findLongestEndingAt(j)).
  • Similarly, define findLongestStartingFrom(i) to compute the longest path starting at coordinates[i].
  • The final answer is findLongestEndingAt(k) + findLongestStartingFrom(k) - 1.

Walkthrough

The core idea is to break the problem into two parts: finding the longest path that ends at coordinates[k] and the longest path that starts at coordinates[k].

A recursive function findLongestEndingAt(i) would work as follows:

  1. The base case is a path of length 1 (the point itself).
  2. It then iterates through every other point j in the coordinates array.
  3. If point j can come before point i in an increasing path (i.e., coordinates[j][0] < coordinates[i][0] and coordinates[j][1] < coordinates[i][1]), it makes a recursive call to findLongestEndingAt(j).
  4. It takes the maximum length returned from all such valid predecessors and adds 1 to it.

A similar function findLongestStartingFrom(i) is defined for paths starting from i. This approach repeatedly calculates the same subproblems, leading to its inefficiency.

// This is a conceptual snippet; a full implementation would need a helper// to pass the coordinates array and avoid global state.private int findLongestEndingAt(int i, int[][] coordinates) {    int maxLength = 1;    for (int j = 0; j < coordinates.length; j++) {        if (i == j) continue;        if (coordinates[j][0] < coordinates[i][0] && coordinates[j][1] < coordinates[i][1]) {            maxLength = Math.max(maxLength, 1 + findLongestEndingAt(j, coordinates));        }    }    return maxLength;} private int findLongestStartingFrom(int i, int[][] coordinates) {    int maxLength = 1;    for (int j = 0; j < coordinates.length; j++) {        if (i == j) continue;        if (coordinates[i][0] < coordinates[j][0] && coordinates[i][1] < coordinates[j][1]) {            maxLength = Math.max(maxLength, 1 + findLongestStartingFrom(j, coordinates));        }    }    return maxLength;} public int getLongestPath(int[][] coordinates, int k) {    int ending = findLongestEndingAt(k, coordinates);    int starting = findLongestStartingFrom(k, coordinates);    return ending + starting - 1;}

Complexity

Time

Exponential, roughly O(N!). For each node, we might branch out to N-1 other nodes, leading to a factorial-like complexity in the worst case.

Space

O(N), for the recursion stack depth in the worst case (a single long chain).

Trade-offs

Pros

  • Simple to conceptualize and follows the problem definition directly.

Cons

  • Extremely inefficient due to a massive number of redundant calculations.

  • Will result in a 'Time Limit Exceeded' error for all but the smallest inputs.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem