We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Length of the Longest Increasing Path

Number: 3571

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a list of distinct 2D points and an index k, we must find the maximum length of a strictly increasing path (with respect to both x and y coordinates) such that the path contains the point coordinates[k]. In other words, if the path is made up of points (x1,y1), (x2,y2), …, (xm,ym) then for every i we need x[i] < x[i+1] and y[i] < y[i+1] and every point is one of the given coordinates. The goal is to maximize m while ensuring that the k‑th coordinate (in the original input order) appears in the path.

Key Insights

  • Since the condition requires both x and y to be strictly increasing, it forms a partial order that can be exploited by sorting.
  • When the points are sorted by x (and by y as a tiebreaker) any valid increasing path will appear in sorted order.
  • The maximum path containing a given point P can be thought of as a combination of:
    • The longest increasing path ending at P.
    • The longest increasing path starting at P.
  • By computing these two quantities (using techniques related to the Longest Increasing Subsequence in one dimension on the y‑values after sorting) and subtracting 1 (to avoid counting P twice), we obtain the desired result.
  • To achieve an O(n log n) solution we can use data structures such as a Fenwick Tree (Binary Indexed Tree) to answer range maximum queries in the DP recurrences efficiently.

Space and Time Complexity

Time Complexity: O(n log n) – Sorting takes O(n log n) and each DP pass (forward and backward) uses range queries/updates costing O(log n) per element. Space Complexity: O(n) – Additional arrays for DP and the Fenwick tree use linear space.

Solution

We first sort the coordinates by x then y (keeping track of the original index so that we know the sorted position corresponding to coordinates[k]). Then we compute two DP arrays over the sorted order:

  1. For each sorted point i, dpForward[i] is the length of the longest chain ending at that point. This is computed by querying a Fenwick tree keyed by the y‑value (after compressing y’s due to large ranges) for points with smaller y values.
  2. Similarly, dpBackward[i] is computed by iterating from right-to‐left; it gives the longest chain starting at point i (again using a Fenwick tree but in reverse order). Finally, if p is the sorted position of coordinates[k], the answer is dpForward[p] + dpBackward[p] – 1, which “glues” together the best chain ending at P and starting from P, counting P only once.

Key details include:

  • Coordinate compression of y-values to allow efficient Fenwick tree queries/updates.
  • Two passes (forward for dpForward and backward for dpBackward) enabling us to “split” the chain at the required point.

Code Solutions

# Python solution with line-by-line comments
# We use a Fenwick Tree (Binary Indexed Tree) that supports range maximum queries.
class FenwickTree:
    def __init__(self, n):
        self.n = n
        # Tree array to keep max DP value in compressed index ranges
        self.tree = [0]*(n+1)
    
    # Update index i (1-indexed for fenwicks) with value val (keep max)
    def update(self, i, val):
        while i <= self.n:
            self.tree[i] = max(self.tree[i], val)
            i += i & -i  # move to parent index
    
    # Query maximum value in range [1, i]
    def query(self, i):
        res = 0
        while i > 0:
            res = max(res, self.tree[i])
            i -= i & -i  # move to previous index
        return res

def length_of_longest_increasing_path(coordinates, k):
    n = len(coordinates)
    # Create list containing (x, y, original_index)
    points = [(pt[0], pt[1], idx) for idx, pt in enumerate(coordinates)]
    # Sort points by x then by y
    points.sort(key=lambda x: (x[0], x[1]))
    
    # Compress y coordinates to range [1, m]
    ys = sorted(set(pt[1] for pt in points))
    y_to_compressed = {y: i+1 for i, y in enumerate(ys)}
    
    # Create DP array for longest chain ending at each point in sorted order
    dpForward = [0]*n
    fenw = FenwickTree(len(ys))
    
    # Forward DP pass: for each point, get best chain that can extend with current point
    for i, (x, y, orig) in enumerate(points):
        compY = y_to_compressed[y]
        best_prev = fenw.query(compY - 1)
        dpForward[i] = best_prev + 1
        fenw.update(compY, dpForward[i])
    
    # Backward DP: longest chain starting at each point, computed by reversing order
    dpBackward = [0]*n
    fenw_back = FenwickTree(len(ys))
    for i in range(n-1, -1, -1):
        x, y, orig = points[i]
        compY = y_to_compressed[y]
        # For backward, we need to find points with y greater than current y;
        # we reverse the order by querying prefix in reversed tree.
        best_next = fenw_back.query(len(ys) - compY)
        dpBackward[i] = best_next + 1
        # Update at reversed index: convert compY to reversed index
        fenw_back.update(len(ys) - compY + 1, dpBackward[i])
    
    # Find the sorted position of the required coordinate coordinates[k]
    target = coordinates[k]
    pos = None
    for i, (x, y, orig) in enumerate(points):
        if orig == k:
            pos = i
            break

    # Return the sum of longest chain ending at the target and starting at the target minus 1
    return dpForward[pos] + dpBackward[pos] - 1

# Example usage:
if __name__ == "__main__":
    # Example 1
    coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]]
    k = 1
    print(length_of_longest_increasing_path(coordinates, k))  # Expected output: 3
← Back to All Questions