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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Length of the Longest Increasing Path

Difficulty: Hard

Problem Description

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, and (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].

Key Insights

  • The problem requires finding the longest strictly increasing sequence of points based on their coordinates.
  • We need to ensure that both x and y coordinates are strictly increasing.
  • The search must include the specific point coordinates[k].
  • Sorting the points based on their coordinates can facilitate finding increasing sequences.
  • A dynamic programming or a binary search approach can optimize the search for the longest increasing subsequence.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the coordinates and then a linear scan for the increasing path. Space Complexity: O(n) - for storing the sorted result and any additional data structures used.

Solution

To solve the problem, we first sort the given coordinates based on x and then y values. This ensures that we only need to find the longest increasing subsequence based on the y-coordinates. We can utilize a dynamic programming approach combined with binary search to efficiently find the longest increasing subsequence that includes the point corresponding to coordinates[k].

The algorithm involves:

  1. Sorting the coordinates.
  2. Using a list to track the longest increasing subsequence of y-coordinates.
  3. Applying binary search to insert each y-coordinate into this list, ensuring that we maintain the increasing order.

Code Solutions

def lengthOfLongestIncreasingPath(coordinates, k):
    from bisect import bisect_left
    
    # Sort the coordinates based on (x, y)
    coordinates.sort()
    
    # Extract the y-coordinate of the k-th point
    target_y = coordinates[k][1]
    
    # List to store the longest increasing subsequence of y-coordinates
    lis = []
    
    # Variable to track the maximum length of the path including coordinates[k]
    max_length = 1
    
    for x, y in coordinates:
        # Use binary search to find the position to replace or extend the lis
        pos = bisect_left(lis, y)
        
        # If pos equals the length of the lis, it means we can extend it
        if pos == len(lis):
            lis.append(y)
        else:
            lis[pos] = y
        
        # Check if the current y is the target_y
        if y == target_y:
            # The length of the increasing sequence until this point
            max_length = max(max_length, pos + 1)
    
    return max_length
← Back to All Questions