Length of the Longest Increasing Path

• 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.

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.

1// This is a conceptual snippet; a full implementation would need a helper2// to pass the coordinates array and avoid global state.3private int findLongestEndingAt(int i, int[][] coordinates) {4    int maxLength = 1;5    for (int j = 0; j < coordinates.length; j++) {6        if (i == j) continue;7        if (coordinates[j][0] < coordinates[i][0] && coordinates[j][1] < coordinates[i][1]) {8            maxLength = Math.max(maxLength, 1 + findLongestEndingAt(j, coordinates));9        }10    }11    return maxLength;12}13 14private int findLongestStartingFrom(int i, int[][] coordinates) {15    int maxLength = 1;16    for (int j = 0; j < coordinates.length; j++) {17        if (i == j) continue;18        if (coordinates[i][0] < coordinates[j][0] && coordinates[i][1] < coordinates[j][1]) {19            maxLength = Math.max(maxLength, 1 + findLongestStartingFrom(j, coordinates));20        }21    }22    return maxLength;23}24 25public int getLongestPath(int[][] coordinates, int k) {26    int ending = findLongestEndingAt(k, coordinates);27    int starting = findLongestStartingFrom(k, coordinates);28    return ending + starting - 1;29}

• 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.

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).

1public int getLongestPath(int[][] coordinates, int k) {2    int n = coordinates.length;3    int[] memoEnding = new int[n];4    int[] memoStarting = new int[n];5    int ending = findLongestEndingAt(k, coordinates, memoEnding);6    int starting = findLongestStartingFrom(k, coordinates, memoStarting);7    return ending + starting - 1;8}9 10private int findLongestEndingAt(int i, int[][] coordinates, int[] memo) {11    if (memo[i] != 0) {12        return memo[i];13    }14    int maxLength = 1;15    for (int j = 0; j < coordinates.length; j++) {16        if (coordinates[j][0] < coordinates[i][0] && coordinates[j][1] < coordinates[i][1]) {17            maxLength = Math.max(maxLength, 1 + findLongestEndingAt(j, coordinates, memo));18        }19    }20    return memo[i] = maxLength;21}22 23private int findLongestStartingFrom(int i, int[][] coordinates, int[] memo) {24    if (memo[i] != 0) {25        return memo[i];26    }27    int maxLength = 1;28    for (int j = 0; j < coordinates.length; j++) {29        if (coordinates[i][0] < coordinates[j][0] && coordinates[i][1] < coordinates[j][1]) {30            maxLength = Math.max(maxLength, 1 + findLongestStartingFrom(j, coordinates, memo));31        }32    }33    return memo[i] = maxLength;34}

• 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.

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.

1class Solution {2    class FenwickTree {3        private int[] tree;4        private int size;5        public FenwickTree(int size) {6            this.size = size;7            this.tree = new int[size + 1];8        }9        public void update(int idx, int val) {10            idx++;11            while (idx <= size) {12                tree[idx] = Math.max(tree[idx], val);13                idx += idx & (-idx);14            }15        }16        public int query(int idx) {17            idx++;18            int maxVal = 0;19            while (idx > 0) {20                maxVal = Math.max(maxVal, tree[idx]);21                idx -= idx & (-idx);22            }23            return maxVal;24        }25    }26 27    class Point {28        int x, y, index;29        Point(int x, int y, int index) {30            this.x = x;31            this.y = y;32            this.index = index;33        }34    }35 36    public int longestIncreasingPath(int[][] coordinates, int k) {37        int[] endingAt = calculateLengths(coordinates, false);38        int[] startingFrom = calculateLengths(coordinates, true);39        return endingAt[k] + startingFrom[k] - 1;40    }41 42    private int[] calculateLengths(int[][] coordinates, boolean isForStartingPath) {43        int n = coordinates.length;44        List<Point> points = new ArrayList<>();45        Set<Integer> ySet = new HashSet<>();46        for (int i = 0; i < n; i++) {47            points.add(new Point(coordinates[i][0], coordinates[i][1], i));48            ySet.add(coordinates[i][1]);49        }50 51        List<Integer> sortedY = new ArrayList<>(ySet);52        Collections.sort(sortedY);53        Map<Integer, Integer> yMap = new HashMap<>();54        for (int i = 0; i < sortedY.size(); i++) {55            yMap.put(sortedY.get(i), i);56        }57        int m = yMap.size();58 59        if (isForStartingPath) {60            points.sort((a, b) -> a.x != b.x ? Integer.compare(b.x, a.x) : Integer.compare(b.y, a.y));61        } else {62            points.sort((a, b) -> a.x != b.x ? Integer.compare(a.x, b.x) : Integer.compare(a.y, b.y));63        }64 65        int[] lengths = new int[n];66        FenwickTree ft = new FenwickTree(m);67        68        for (int i = 0; i < n; ) {69            int j = i;70            while (j < n && points.get(j).x == points.get(i).x) {71                j++;72            }73            74            List<int[]> batchResults = new ArrayList<>();75            for (int l = i; l < j; l++) {76                Point p = points.get(l);77                int yCompressed = yMap.get(p.y);78                int prevMax;79                if (isForStartingPath) {80                    int yTransformed = m - 1 - yCompressed;81                    prevMax = (yTransformed == 0) ? 0 : ft.query(yTransformed - 1);82                } else {83                    prevMax = (yCompressed == 0) ? 0 : ft.query(yCompressed - 1);84                }85                batchResults.add(new int[]{p.index, yCompressed, 1 + prevMax});86            }87 88            for (int[] res : batchResults) {89                lengths[res[0]] = res[2];90                int yCompressed = res[1];91                int updateVal = res[2];92                int updateIndex = isForStartingPath ? m - 1 - yCompressed : yCompressed;93                ft.update(updateIndex, updateVal);94            }95            i = j;96        }97        return lengths;98    }99}