Skip to main content
Talentd

Length of the Longest Increasing Path - Solution & Explanation

HardArrayBinary SearchSorting10 min read
Practice this problem

Problem Statement

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

 

Example 1:

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

Output: 3

Explanation:

(0, 0), (2, 2), (5, 3) is the longest increasing path that contains (2, 2).

Example 2:

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

Output: 2

Explanation:

(2, 1), (5, 6) is the longest increasing path that contains (5, 6).

 

Constraints:

  • 1 <= n == coordinates.length <= 105
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0], coordinates[i][1] <= 109
  • All elements in coordinates are distinct.
  • 0 <= k <= n - 1

Approach Overview

Problem Overview: You are given a set of points stored in an array. A valid path requires coordinates to strictly increase as you move forward. The goal is to compute the maximum length of such an increasing path while respecting the ordering constraints between points.

Approach 1: Dynamic Programming with Sorting (O(n log n) time, O(n) space)

Start by sorting the points by their first coordinate. If two points share the same first coordinate, order them carefully so they do not incorrectly extend an increasing sequence. After sorting, the problem reduces to finding a longest increasing sequence based on the second coordinate. Maintain a DP structure similar to the classic Longest Increasing Subsequence. For each point, use binary search to find the position where its second coordinate fits in the current sequence and update the DP array. Sorting enforces the first coordinate constraint, while the LIS step ensures the second coordinate strictly increases. This approach relies heavily on sorting and binary search to achieve an efficient solution.

Approach 2: Coordinate Compression with Dynamic Programming (O(n log n) time, O(n) space)

When coordinates are large or sparse, compress them into a smaller index range before applying dynamic programming. Map each coordinate value to a compressed rank so comparisons remain consistent but memory usage stays small. After compression, process points in sorted order and compute the longest valid sequence ending at each point. A Fenwick Tree or segment tree can query the best previous length for smaller coordinates, then update the current coordinate with the new DP value. Compression avoids large arrays while keeping operations logarithmic. This technique combines array processing with indexed data structures to efficiently track optimal subproblems.

Recommended for interviews: The sorting + LIS style dynamic programming approach is what most interviewers expect. It shows you can recognize when a 2D ordering problem reduces to a 1D LIS after sorting. The coordinate compression variant demonstrates deeper optimization skills when coordinate ranges are large or when using Fenwick/segment tree style DP.

Approach 1: Dynamic Programming with Sorting

In this approach, we first sort the given points to have them in a potential order to identify increasing paths. We then employ dynamic programming (DP) to determine the longest path that includes a specific point by storing the maximum path length terminating at each point. This is done by iteratively updating the path lengths based on previously computed DP values for eligible preceding points.

This C solution sorts the coordinates array based on x and y values and uses a dynamic programming array dp to store the longest increasing path up to each point. We then determine the maximum at point k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is dominated by the sorting step, O(n log n). Space complexity is O(n) due to the dynamic programming array.

Try this approach in the editor →

Approach 2: Coordinate Compression with Dynamic Programming

Instead of directly comparing each pair of coordinates, this approach uses coordinate compression to map each coordinate to a potentially reduced range. This helps optimize the process of updating the longest paths using a sweep line technique and binary indexed tree (BIT) for efficiently querying and updating the longest increasing sequences.

In this C++ solution, coordinate compression maps y-values to a new domain to manage their size in a binary indexed tree (BIT). Subsequently, the BIT is used to efficiently maintain and query the longest increasing sequences up to each compressed y-value.

Code

C++

C++

Complexity

This approach has a time complexity of O(n log n) due to sorting and BIT updates. Space complexity is O(n) because of BIT and map storage.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Sorting

The time complexity is dominated by the sorting step, O(n log n). Space complexity is O(n) due to the dynamic programming array.

Coordinate Compression with Dynamic Programming

This approach has a time complexity of O(n log n) due to sorting and BIT updates. Space complexity is O(n) because of BIT and map storage.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Sorting (LIS style)O(n log n)O(n)General case where points can be sorted and LIS can be applied on one dimension
Coordinate Compression + DP (Fenwick/Segment Tree)O(n log n)O(n)When coordinate values are large and require efficient indexed queries

Video Solution

3288. Length of the Longest Increasing Path (Leetcode Hard) • Programming Live with Larry • 422 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Length of the Longest Increasing Path easy or hard?
Length of the Longest Increasing Path is classified as a Hard problem because it requires recognizing the reduction to a Longest Increasing Subsequence after sorting. Candidates must combine sorting, binary search, and dynamic programming to reach the optimal O(n log n) solution.
Length of the Longest Increasing Path Python/Java solution
Python and Java implementations typically sort the input array and maintain a DP list representing the LIS tails. The built-in binary search utilities such as bisect in Python or Collections.binarySearch in Java help update the structure in logarithmic time.
How to solve Length of the Longest Increasing Path in O(n log n)?
First sort the points by the first coordinate. Then iterate through them while maintaining an array representing the smallest possible tail for increasing subsequences of each length. Use binary search to update the position for each second coordinate value, which keeps the sequence strictly increasing.
What is the best approach for Length of the Longest Increasing Path?
The most efficient solution sorts the points by one coordinate and then computes a Longest Increasing Subsequence (LIS) on the second coordinate. Binary search maintains the LIS structure in O(n log n) time. This approach converts a 2D ordering constraint into a classic LIS problem after sorting.
Is Length of the Longest Increasing Path asked at Google/Amazon/Meta?
Longest increasing sequence variations frequently appear in interviews at companies like Google, Amazon, and Meta. Problems that combine sorting with LIS or dynamic programming are common because they test pattern recognition and algorithm optimization.
What data structure is used in Length of the Longest Increasing Path?
Typical solutions use arrays for dynamic programming along with binary search for LIS updates. Some optimized implementations also use Fenwick Trees or segment trees after coordinate compression to query and update sequence lengths efficiently.
What is the time complexity of Length of the Longest Increasing Path?
The optimal approach runs in O(n log n) time due to sorting and binary search operations during LIS computation. Space complexity is O(n) for the DP structure that tracks the current increasing subsequence.

Ready to solve this problem?

Practice Length of the Longest Increasing Path with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays