LeetCode 3288 - Length of the Longest Increasing Path

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sorting

Solution

Problem Understanding

We are given a collection of distinct points on a 2D plane. Each point is represented as (x, y).

An increasing path is a sequence of points where both coordinates strictly increase from one point to the next. If we move from point A = (x1, y1) to point B = (x2, y2), then we must satisfy:

x1 < x2
y1 < y2

The problem asks for the maximum possible length of such a path that must include one specific point, coordinates[k].

This is important because we are not simply looking for the global longest increasing path. The path is constrained to pass through one designated point.

For example, if the target point is (2, 2), then every valid path we consider must contain that point somewhere in the sequence.

The input size is large:

Up to 10^5 points
Coordinates can be as large as 10^9

These constraints immediately rule out quadratic dynamic programming solutions such as checking every pair of points. Any O(n^2) solution would be far too slow for 10^5 elements.

The fact that all coordinates are distinct is very helpful. We never need to worry about duplicate points.

A few important observations emerge immediately:

A valid predecessor of (x, y) must satisfy both smaller x and smaller y.
A valid successor must satisfy both larger x and larger y.
The designated point splits the problem naturally into:
the best increasing chain ending at that point
the best increasing chain starting from that point

The final answer is:

(left chain length) + (right chain length) - 1

We subtract one because the target point gets counted twice.

Important edge cases include:

Only one point exists
No point can precede the target
No point can follow the target
All points form a single chain
Points are ordered in a way that creates many invalid transitions despite increasing x

The strict inequality on both coordinates is especially important. Equal x or equal y values cannot be chained together.

Approaches

Brute Force Approach

A brute force solution would treat the problem as a graph problem.

For every pair of points (i, j), we could create a directed edge from i to j if:

xi < xj AND yi < yj

This creates a directed acyclic graph because coordinates strictly increase along edges.

We could then perform dynamic programming or DFS memoization to compute:

longest path ending at each node
longest path starting from each node

Finally, we combine the two values for coordinates[k].

This works because every valid increasing path corresponds to a path in the DAG.

Unfortunately, constructing the graph itself requires checking all pairs of points:

O(n^2)

With n = 100000, this is completely infeasible.

Key Insight

The problem is actually a variation of the Longest Increasing Subsequence problem in two dimensions.

If we sort points by:

increasing x
decreasing y when x ties

then finding a valid increasing path becomes equivalent to finding a LIS on the y values.

The classic LIS algorithm using binary search runs in:

O(n log n)

The designated point divides the solution into two independent LIS computations:

Longest increasing subsequence ending at the target point
Longest increasing subsequence starting from the target point

We can compute:

the forward LIS among points smaller than the target
the reverse LIS among points larger than the target

The final answer combines both lengths.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n²) or O(n)	Builds all valid transitions explicitly
Optimal	O(n log n)	O(n)	Uses LIS with binary search

Algorithm Walkthrough

Step 1: Extract the Target Point

We first store:

target_x, target_y = coordinates[k]

Every point in the final path must relate correctly to this point.

Step 2: Partition the Points

We divide all points into three categories:

points strictly smaller than the target in both coordinates
the target point itself
points strictly larger than the target in both coordinates

Points that fail one of the inequalities can never appear in the same increasing path as the target.

For example:

(1, 10) cannot connect to (5, 5)

because the y coordinate decreases.

Step 3: Compute the Best Left Chain

We gather all points satisfying:

x < target_x AND y < target_y

These are the only points that can appear before the target.

We sort them by:

increasing x
decreasing y

The decreasing y tie breaker is the standard trick used in 2D LIS problems. It prevents invalid subsequences from forming when x values are equal.

We then run the classic LIS algorithm on the y values.

The LIS length gives the maximum number of points that can appear before the target.

Including the target itself:

left_length = LIS + 1

Step 4: Compute the Best Right Chain

Now we find all points satisfying:

x > target_x AND y > target_y

These are the only points that can appear after the target.

We again sort by:

increasing x
decreasing y

Then we compute LIS on the y values.

This gives the maximum number of points that can appear after the target.

Including the target:

right_length = LIS + 1

Step 5: Combine the Results

The target point belongs to both chains, so:

answer = left_length + right_length - 1

Why it works

Sorting by increasing x ensures any subsequence automatically satisfies the x ordering requirement.

The decreasing y tie breaker prevents points with equal x from incorrectly appearing together in the LIS.

After sorting, any increasing subsequence on y corresponds exactly to a valid increasing path in two dimensions.

Since every valid path containing the target decomposes into:

a valid increasing chain before the target
the target itself
a valid increasing chain after the target

combining the two optimal LIS computations produces the globally optimal answer.

Python Solution

from bisect import bisect_left
from typing import List

class Solution:
    def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
        target_x, target_y = coordinates[k]

        left_points = []
        right_points = []

        for x, y in coordinates:
            if x < target_x and y < target_y:
                left_points.append((x, y))
            elif x > target_x and y > target_y:
                right_points.append((x, y))

        def lis_length(points: List[tuple]) -> int:
            points.sort(key=lambda p: (p[0], -p[1]))

            lis = []

            for _, y in points:
                pos = bisect_left(lis, y)

                if pos == len(lis):
                    lis.append(y)
                else:
                    lis[pos] = y

            return len(lis)

        left_len = lis_length(left_points)
        right_len = lis_length(right_points)

        return left_len + right_len + 1

The implementation begins by extracting the target point.

We then separate points into two groups:

points that can appear before the target
points that can appear after the target

Any point failing the strict inequalities is ignored immediately because it can never participate in a valid path containing the target.

The helper function lis_length performs the standard O(n log n) LIS algorithm.

The points are sorted using:

(key=lambda p: (p[0], -p[1]))

This ordering is critical for correctness in 2D LIS problems.

The lis array stores the smallest possible ending value for increasing subsequences of each length. Binary search allows us to update this efficiently.

Finally, we combine:

left_len + right_len + 1

The +1 accounts for the target point itself.

Go Solution

package main

import (
	"sort"
)

func maxPathLength(coordinates [][]int, k int) int {
	targetX := coordinates[k][0]
	targetY := coordinates[k][1]

	leftPoints := make([][]int, 0)
	rightPoints := make([][]int, 0)

	for _, point := range coordinates {
		x := point[0]
		y := point[1]

		if x < targetX && y < targetY {
			leftPoints = append(leftPoints, []int{x, y})
		} else if x > targetX && y > targetY {
			rightPoints = append(rightPoints, []int{x, y})
		}
	}

	lisLength := func(points [][]int) int {
		sort.Slice(points, func(i, j int) bool {
			if points[i][0] == points[j][0] {
				return points[i][1] > points[j][1]
			}
			return points[i][0] < points[j][0]
		})

		lis := make([]int, 0)

		for _, point := range points {
			y := point[1]

			pos := sort.SearchInts(lis, y)

			if pos == len(lis) {
				lis = append(lis, y)
			} else {
				lis[pos] = y
			}
		}

		return len(lis)
	}

	leftLen := lisLength(leftPoints)
	rightLen := lisLength(rightPoints)

	return leftLen + rightLen + 1
}

The Go implementation follows the exact same algorithmic structure as the Python solution.

A few Go-specific details are worth noting:

sort.Slice is used for custom sorting.
sort.SearchInts performs binary search for the LIS update step.
Slices dynamically grow as needed.
Integer overflow is not a concern because the maximum path length is at most 10^5.

Worked Examples

Example 1

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

Target point:

(2, 2)

Step 1: Partition Points

Point	Relation
(3,1)	Invalid
(2,2)	Target
(4,1)	Invalid
(0,0)	Left
(5,3)	Right

So:

left_points = [(0,0)]
right_points = [(5,3)]

Step 2: Left LIS

Sorted:

x	y
0	0

LIS states:

y	lis
0	[0]

Result:

left_len = 1

Step 3: Right LIS

Sorted:

x	y
5	3

LIS states:

y	lis
3	[3]

Result:

right_len = 1

Step 4: Final Answer

1 + 1 + 1 = 3

The path is:

(0,0) -> (2,2) -> (5,3)

Example 2

coordinates = [[2,1],[7,0],[5,6]]
k = 2

Target:

(5,6)

Step 1: Partition

Point	Relation
(2,1)	Left
(7,0)	Invalid
(5,6)	Target

So:

left_points = [(2,1)]
right_points = []

Step 2: Left LIS

y	lis
1	[1]

Result:

left_len = 1

Step 3: Right LIS

No points exist.

right_len = 0

Step 4: Final Answer

1 + 0 + 1 = 2

Valid path:

(2,1) -> (5,6)

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting and LIS binary searches dominate
Space	O(n)	Arrays used for partitioning and LIS

The algorithm scans the input once to partition points.

Each partition is sorted independently. Across all points, total sorting work remains O(n log n).

The LIS computation processes each point once and performs a binary search for each update, giving another O(n log n) factor.

The auxiliary space comes from storing partitions and the LIS tracking array.

Test Cases

from typing import List

class Solution:
    def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
        from bisect import bisect_left

        target_x, target_y = coordinates[k]

        left_points = []
        right_points = []

        for x, y in coordinates:
            if x < target_x and y < target_y:
                left_points.append((x, y))
            elif x > target_x and y > target_y:
                right_points.append((x, y))

        def lis_length(points):
            points.sort(key=lambda p: (p[0], -p[1]))

            lis = []

            for _, y in points:
                pos = bisect_left(lis, y)

                if pos == len(lis):
                    lis.append(y)
                else:
                    lis[pos] = y

            return len(lis)

        return lis_length(left_points) + lis_length(right_points) + 1

sol = Solution()

assert sol.maxPathLength([[3,1],[2,2],[4,1],[0,0],[5,3]], 1) == 3
# basic example with both left and right chains

assert sol.maxPathLength([[2,1],[7,0],[5,6]], 2) == 2
# example with only left contribution

assert sol.maxPathLength([[1,1]], 0) == 1
# single point

assert sol.maxPathLength([[1,1],[2,2],[3,3],[4,4]], 2) == 4
# full increasing chain

assert sol.maxPathLength([[4,4],[3,3],[2,2],[1,1]], 1) == 4
# unordered input

assert sol.maxPathLength([[1,5],[2,4],[3,3],[4,2],[5,1]], 2) == 1
# no valid increasing neighbors

assert sol.maxPathLength([[1,1],[1,2],[2,3]], 2) == 2
# equal x values should not chain

assert sol.maxPathLength([[1,1],[2,2],[2,3],[3,4]], 1) == 3
# tie handling in sorting

assert sol.maxPathLength([[0,0],[1000000000,1000000000]], 0) == 2
# large coordinate values

assert sol.maxPathLength([[5,5],[1,1],[2,2],[10,10],[6,6]], 0) == 5
# target in the middle of optimal path

Test Summary

Test	Why
Basic sample	Verifies normal operation
Only left chain	Verifies empty right side
Single point	Smallest valid input
Fully increasing chain	Verifies maximum chaining
Unordered input	Confirms sorting correctness
No valid neighbors	Verifies answer can be 1
Equal x values	Tests strict inequality handling
Sorting tie case	Verifies decreasing y tie breaker
Large coordinates	Confirms coordinate magnitude is irrelevant
Target in middle	Verifies combining left and right LIS

Edge Cases

Single Point Input

If the input contains only one point, the answer must be 1.

This can easily break implementations that assume at least one predecessor or successor exists. In this solution, both partitions become empty, both LIS computations return 0, and the final answer becomes:

0 + 0 + 1 = 1

which is correct.

Equal X Coordinates

Points with the same x value cannot belong to the same increasing path because the problem requires strict inequality.

A naive LIS implementation that sorts by increasing x and increasing y may accidentally allow invalid chains among equal x values.

The solution prevents this by sorting ties using decreasing y:

(x ascending, y descending)

This is the standard and correct handling for 2D LIS problems.

Target Cannot Connect to Any Point

Sometimes the target has no valid predecessor and no valid successor.

Example:

[(1,5), (2,4), (3,3)]

Every candidate violates the strict y increase condition.

In this case, both partitions are empty and the answer correctly becomes 1.

This is important because some implementations incorrectly assume the target can always extend a chain.