Skip to content

Practice Length of the Longest Increasing Path

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3288
LeetCode Problem

Length of the Longest Increasing Path

Problem Statement

Choose a sequence of the supplied coordinates that includes coordinates[k]. Every step must increase both x and y strictly; equality in either coordinate is forbidden. Points can be visited in a different order from the input. Return the largest possible number of points in such a sequence. Approach: Split eligible points around the required pivot into those smaller in both coordinates and those larger in both. Solve each side independently: sort by increasing x, breaking equal-x ties by decreasing y, then find a strictly increasing subsequence of y using binary search. The answer is the two subsequence lengths plus one for the pivot. The tie ordering prevents equal-x points from entering the same path. Time: O(n log n); auxiliary space: O(n). Worked example: For the first input below, (0,0), (2,2), (3,3), (4,4) gives length 4. The point (1,3) cannot appear before the required pivot because its y coordinate is too large.

Source: Length of the Longest Increasing Path on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
coordinates = [[0,0],[1,3],[2,2],[4,4],[3,3],[2,1]], k = 2
Output
4

# Example 2

Input
coordinates = [[1,1],[1,2],[2,1]], k = 0
Output
1

Constraints

There are 1 to 100,000 distinct coordinate pairs.
Each pair contains exactly two integers, both from 0 through 1,000,000,000.
k is a valid zero-based index into coordinates.

How to solve Length of the Longest Increasing Path

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Because the pivot must be on the path, everything before it is strictly smaller in both coordinates and everything after it strictly larger, so the problem splits into two independent two-dimensional longest strictly increasing chain problems, each solved by sorting on x and running the binary-search LIS on y.

Why brute force is not enough

The quadratic longest increasing subsequence dynamic program compares every pair of points, about 10^10 operations for 100,000 coordinates.

Approach

  1. Partition: keep points with both coordinates strictly below the pivot in a lower set and points with both strictly above in an upper set; discard the rest, since no path through the pivot can use them.
  2. Sort each set by x ascending and, for equal x, by y descending. The tie-break ensures two points sharing an x value can never both be chosen, because their y values appear in decreasing order and the chain on y is strict.
  3. Run the O(n log n) strictly increasing subsequence on the y values: keep a sorted array where position i is the smallest possible last y of a chain of length i + 1, and insert each y by replacing the first entry greater than or equal to it or appending. Sortedness is the invariant that makes binary search valid.
  4. The array length after a set is that side's longest chain; it is automatically strictly increasing in x as well because of the tie-break.
  5. Return lower length plus upper length plus one for the pivot.

Walkthrough of Example 1

coordinates = [[0,0],[1,3],[2,2],[4,4],[3,3],[2,1]], k = 2 → 4

  1. coordinates are [[0,0],[1,3],[2,2],[4,4],[3,3],[2,1]] and k is 2, so the pivot is (2,2).
  2. Lower set: only (0,0). The point (1,3) fails on y and (2,1) fails because its x equals 2.
  3. Upper set: (4,4) and (3,3). Sorted by x: (3,3), (4,4), with y values 3, 4.
  4. The chain on [0] has length 1; the chain on [3,4] has length 2.
  5. Answer is 1 + 2 + 1 = 4, realized by (0,0), (2,2), (3,3), (4,4), the expected output.

Time and space

Time O(n log n) · Space O(n). With n points, partitioning is linear, sorting each side is O(n log n), each insertion is O(log n), and the partitioned copies and tails array are linear.

Interview pitfalls

  • Sorting equal-x points by ascending y, which lets two points with the same x enter the chain.
  • Using a non-strict search so equal y values chain together; y must strictly increase.
  • Running LIS on all points and ignoring that the pivot must be included; the true answer can be much smaller.
  • Filtering with non-strict comparisons, letting points sharing a coordinate with the pivot leak into a side.
  • Forgetting the plus one for the pivot, or adding it twice.

Follow-up questions interviewers ask

  • How would you reconstruct one longest path rather than its length?
  • If the path need not contain any particular point, how does the answer relate to this computation?
  • Can you answer the question for many different pivots without recomputing from scratch each time?

Further reading on the technique: Longest increasing subsequence

Related LeetCode Problems

Practice more problems similar to Length of the Longest Increasing Path.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.