# Length of the Longest Increasing Path
**Difficulty:** HARD
[External](https://leetcode.com/problems/length-of-the-longest-increasing-path)
Canonical: https://scaleengineer.com/dsa/problems/length-of-the-longest-increasing-path
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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]`.

**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
## Brute-Force Recursion
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.
**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).
**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.
### Explanation
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.

```java
// 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;
}
```
### 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`.

## Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using memoization, a dynamic programming technique. We store the results of subproblems (the longest path lengths for each point) in cache arrays. When the recursive function is called for a point for which the result has already been computed, we simply return the cached value instead of re-exploring its entire sub-tree. This drastically reduces the number of computations from exponential to polynomial time.
**Time:** O(N^2). There are 2*N subproblems (states). Each subproblem takes O(N) time to solve as it iterates through all other points. · **Space:** O(N), for the two memoization arrays and the recursion stack.
**Pros:** Vastly more efficient than the brute-force approach.; Guarantees that each subproblem is solved only once.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 10^5).
### Explanation
We maintain two arrays, `memoEnding` and `memoStarting`, to store the lengths of the longest paths ending at and starting from each point, respectively. The recursive functions are modified to use these arrays.

When `findLongestEndingAt(i)` is called:
1. It checks `memoEnding[i]`. If it's not the initial value, the result is already known, so it's returned immediately.
2. Otherwise, it proceeds with the calculation: it iterates through all other points `j` to find valid predecessors, makes recursive calls, and finds the maximum length.
3. Crucially, before returning, it saves the calculated length in `memoEnding[i]`. 

This ensures that the expensive computation for each point is performed only once. The overall complexity becomes the number of states (N for each of the two DP arrays) multiplied by the work per state (an O(N) loop to find predecessors/successors).

```java
public int getLongestPath(int[][] coordinates, int k) {
    int n = coordinates.length;
    int[] memoEnding = new int[n];
    int[] memoStarting = new int[n];
    int ending = findLongestEndingAt(k, coordinates, memoEnding);
    int starting = findLongestStartingFrom(k, coordinates, memoStarting);
    return ending + starting - 1;
}

private int findLongestEndingAt(int i, int[][] coordinates, int[] memo) {
    if (memo[i] != 0) {
        return memo[i];
    }
    int maxLength = 1;
    for (int j = 0; j < coordinates.length; j++) {
        if (coordinates[j][0] < coordinates[i][0] && coordinates[j][1] < coordinates[i][1]) {
            maxLength = Math.max(maxLength, 1 + findLongestEndingAt(j, coordinates, memo));
        }
    }
    return memo[i] = maxLength;
}

private int findLongestStartingFrom(int i, int[][] coordinates, int[] memo) {
    if (memo[i] != 0) {
        return memo[i];
    }
    int maxLength = 1;
    for (int j = 0; j < coordinates.length; j++) {
        if (coordinates[i][0] < coordinates[j][0] && coordinates[i][1] < coordinates[j][1]) {
            maxLength = Math.max(maxLength, 1 + findLongestStartingFrom(j, coordinates, memo));
        }
    }
    return memo[i] = maxLength;
}
```
### Algorithm
- Use the same recursive structure as the brute-force approach.
- Create two memoization arrays, `memoEnding` and `memoStarting`, of size `n`, initialized to a value indicating 'not computed' (e.g., 0 or -1).
- In the `findLongestEndingAt(i)` function, first check if `memoEnding[i]` has been computed. If so, return the stored value.
- If not, compute the value as in the brute-force approach.
- Before returning the computed length, store it in `memoEnding[i]`.
- Apply the same logic to the `findLongestStartingFrom(i)` function with the `memoStarting` array.
- The final result is `findLongestEndingAt(k) + findLongestStartingFrom(k) - 1`.

## Optimized Dynamic Programming with Fenwick Tree
The O(N^2) DP approach is bottlenecked by the linear scan to find predecessors or successors for each point. We can optimize this search using a combination of sorting and a data structure. By sorting the points by their x-coordinate, we ensure that when we process any point, all its potential predecessors have already been processed. The problem then reduces to efficiently finding the maximum path length among the processed points that also satisfy the y-coordinate condition. This is a 1D range maximum query problem, which can be solved in logarithmic time using a Fenwick Tree or Segment Tree. Since y-coordinates can be large, we first apply coordinate compression. We perform this process twice: once with ascending sort to find paths ending at each point, and once with descending sort to find paths starting from each point.
**Time:** O(N log N). Sorting takes O(N log N). The two passes over the data involve N Fenwick Tree operations, each taking O(log M) where M <= N. The total time is dominated by sorting. · **Space:** O(N), to store the points, DP arrays, coordinate map, and the Fenwick Tree.
**Pros:** Highly efficient, with a time complexity that meets the problem constraints.; It's a general and powerful technique for this class of 2D DP problems.
**Cons:** Significantly more complex to implement correctly compared to simpler DP.; Requires knowledge of advanced data structures like Fenwick Trees and concepts like coordinate compression.
### Explanation
This approach provides an efficient O(N log N) solution.

**1. Data Structures**
- **Point Class**: A simple class or struct to hold `x`, `y`, and the original index of each coordinate.
- **Fenwick Tree**: A data structure that can perform point updates and prefix maximum queries in O(log M) time, where M is the size of the tree.

**2. Calculating `dpEnding` (Longest Paths Ending at Each Point)**
- We sort the points in increasing order of `x`, then `y`. This ensures that for any point `p_i`, any predecessor `p_j` appears before it in the sorted list.
- The DP relation is `dpEnding[i] = 1 + max({0} U {dpEnding[j] | x_j < x_i, y_j < y_i})`.
- After sorting, the `x_j < x_i` condition is implicitly handled for many `j`. The challenge is to efficiently find `max(dpEnding[j])` for `y_j < y_i` among the already processed points.
- We use a Fenwick Tree on the compressed y-coordinates. We iterate through the sorted points. For point `p_i`, we query the tree for `max_len` in the range `[0, y_compressed_i - 1]`. Then we set `dpEnding[i] = 1 + max_len` and update the tree at `y_compressed_i` with this new value.

**3. Calculating `dpStarting` (Longest Paths Starting from Each Point)**
- This is symmetric. We sort points in decreasing order of `x`, then `y`.
- The DP relation is `dpStarting[i] = 1 + max({0} U {dpStarting[j] | x_i < x_j, y_i < y_j})`.
- We need to query for `y_j > y_i`. We can map the compressed y-coordinates `y_comp` to `m - 1 - y_comp` (where `m` is the number of unique y's). A query for `y_j > y_i` becomes a query for `y_j' < y_i'`, which our Fenwick tree can handle.

**4. Implementation Details**
- Points with the same x-coordinate must be processed as a batch. We calculate the DP values for all of them based on the current Fenwick tree state, and only after that, we update the tree with all their new lengths. This prevents points with the same `x` from being predecessors/successors to each other.

```java
class Solution {
    class FenwickTree {
        private int[] tree;
        private int size;
        public FenwickTree(int size) {
            this.size = size;
            this.tree = new int[size + 1];
        }
        public void update(int idx, int val) {
            idx++;
            while (idx <= size) {
                tree[idx] = Math.max(tree[idx], val);
                idx += idx & (-idx);
            }
        }
        public int query(int idx) {
            idx++;
            int maxVal = 0;
            while (idx > 0) {
                maxVal = Math.max(maxVal, tree[idx]);
                idx -= idx & (-idx);
            }
            return maxVal;
        }
    }

    class Point {
        int x, y, index;
        Point(int x, int y, int index) {
            this.x = x;
            this.y = y;
            this.index = index;
        }
    }

    public int longestIncreasingPath(int[][] coordinates, int k) {
        int[] endingAt = calculateLengths(coordinates, false);
        int[] startingFrom = calculateLengths(coordinates, true);
        return endingAt[k] + startingFrom[k] - 1;
    }

    private int[] calculateLengths(int[][] coordinates, boolean isForStartingPath) {
        int n = coordinates.length;
        List<Point> points = new ArrayList<>();
        Set<Integer> ySet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            points.add(new Point(coordinates[i][0], coordinates[i][1], i));
            ySet.add(coordinates[i][1]);
        }

        List<Integer> sortedY = new ArrayList<>(ySet);
        Collections.sort(sortedY);
        Map<Integer, Integer> yMap = new HashMap<>();
        for (int i = 0; i < sortedY.size(); i++) {
            yMap.put(sortedY.get(i), i);
        }
        int m = yMap.size();

        if (isForStartingPath) {
            points.sort((a, b) -> a.x != b.x ? Integer.compare(b.x, a.x) : Integer.compare(b.y, a.y));
        } else {
            points.sort((a, b) -> a.x != b.x ? Integer.compare(a.x, b.x) : Integer.compare(a.y, b.y));
        }

        int[] lengths = new int[n];
        FenwickTree ft = new FenwickTree(m);
        
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && points.get(j).x == points.get(i).x) {
                j++;
            }
            
            List<int[]> batchResults = new ArrayList<>();
            for (int l = i; l < j; l++) {
                Point p = points.get(l);
                int yCompressed = yMap.get(p.y);
                int prevMax;
                if (isForStartingPath) {
                    int yTransformed = m - 1 - yCompressed;
                    prevMax = (yTransformed == 0) ? 0 : ft.query(yTransformed - 1);
                } else {
                    prevMax = (yCompressed == 0) ? 0 : ft.query(yCompressed - 1);
                }
                batchResults.add(new int[]{p.index, yCompressed, 1 + prevMax});
            }

            for (int[] res : batchResults) {
                lengths[res[0]] = res[2];
                int yCompressed = res[1];
                int updateVal = res[2];
                int updateIndex = isForStartingPath ? m - 1 - yCompressed : yCompressed;
                ft.update(updateIndex, updateVal);
            }
            i = j;
        }
        return lengths;
    }
}
```
### Algorithm
- Decompose the problem into two parts: calculating `dpEnding` (longest path ending at each point) and `dpStarting` (longest path starting from each point).
- **To calculate `dpEnding`**:
  1. Sort the points by x-coordinate (primary key) and y-coordinate (secondary key).
  2. The y-coordinates can be large, so perform coordinate compression on them to map them to a smaller range `[0, m-1]`.
  3. Initialize a Fenwick Tree (or Segment Tree) for range maximum queries.
  4. Iterate through the sorted points. For each point `p_i = (x_i, y_i)`, query the Fenwick tree for the maximum path length among points with a compressed y-coordinate less than `p_i`'s. Let this be `max_len`.
  5. The longest path ending at `p_i` is `1 + max_len`. Store this result.
  6. Update the Fenwick tree at `p_i`'s compressed y-coordinate with this new length.
  7. Handle points with the same x-coordinate in a batch to ensure correctness.
- **To calculate `dpStarting`**:
  1. Follow a similar process, but sort the points in descending order of x and y.
  2. When querying the Fenwick tree for a point `p_i`, we need the max length for points with `y > y_i`. This can be achieved by transforming the compressed y-coordinates (e.g., `y_comp' = m - 1 - y_comp`) and performing a standard prefix max query.
- **Final Step**: Combine the results: `answer = dpEnding[k] + dpStarting[k] - 1`.