Skip to main content
Talentd

Longest Increasing Subsequence II - Solution & Explanation

HardArrayDivide and ConquerDynamic ProgrammingBinary Indexed Tree14 min readAsked at: Google
Practice this problem

Problem Statement

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:

  • The subsequence is strictly increasing and
  • The difference between adjacent elements in the subsequence is at most k.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.

Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.

Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i], k <= 105

Approach Overview

Problem Overview: You are given an array nums and an integer k. The goal is to build the longest strictly increasing subsequence where the difference between consecutive elements is at most k. For each number x, the previous value in the subsequence must lie in the range [x - k, x - 1].

Approach 1: Quadratic Dynamic Programming (O(n²) time, O(n) space)

The most direct idea mirrors the classic LIS dynamic programming solution. Define dp[i] as the length of the best subsequence ending at index i. For each element, iterate through all previous indices j < i and update if nums[j] < nums[i] and nums[i] - nums[j] ≤ k. This checks every valid predecessor and extends the subsequence. The method clearly expresses the recurrence but performs a nested scan, giving O(n²) time. It works for small inputs but fails on large constraints where n can reach 10⁵.

Approach 2: Dynamic Programming with Binary Indexed Tree (O(n log V) time, O(V) space)

The bottleneck in the quadratic DP is searching for the best previous subsequence. Instead of scanning all earlier indices, maintain the best subsequence length for each value using a Binary Indexed Tree. When processing value x, query the maximum subsequence length stored in the value range [x - k, x - 1]. This gives the best candidate to extend. Then update position x in the tree with best + 1. The BIT supports prefix maximum queries and updates in O(log V), turning the entire process into O(n log V). This approach is compact and works well when the value range is manageable or after coordinate compression.

Approach 3: Segment Tree Optimization (O(n log V) time, O(V) space)

A Segment Tree provides the same idea with more flexible range queries. The tree stores the maximum subsequence length achievable for each value. For every element x, query the range [x - k, x - 1] to retrieve the best subsequence length that can precede it. Compute current = best + 1 and update the tree at position x. Because each query and update runs in O(log V), the total complexity remains O(n log V). Segment trees are often easier to implement for range maximum queries and avoid some prefix limitations of BITs.

Both optimized approaches rely on the same dynamic programming recurrence: dp[x] = 1 + max(dp[y]) for all y in [x - k, x - 1]. The data structure simply accelerates the range maximum lookup.

Recommended for interviews: Start by describing the quadratic DP to show you understand the LIS-style recurrence. Then explain why scanning all previous elements is too slow. Interviewers typically expect the optimized Segment Tree or Binary Indexed Tree solution with O(n log V) complexity because it demonstrates strong knowledge of range queries and advanced data structures.

Approach 1: Dynamic Programming with Binary Indexed Tree

This approach uses dynamic programming in combination with a Binary Indexed Tree (Fenwick Tree) to efficiently track the best possible subsequence length that can end at each element of the array. The idea is to iterate through the array while updating and querying the tree to determine the longest valid sequence that can be extended with the current element.

This Python implementation uses a BIT to maintain and query lengths of subsequences efficiently. By updating the BIT for each number, the longest subsequence ending with that number is checked and updated.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log M), where n is the length of the array and M is the maximum element in nums.
Space Complexity: O(M), due to the BIT array.

Try this approach in the editor →

Approach 2: Segment Tree Optimization

This method employs a segment tree to optimize the search and update operations required to find the longest increasing subsequence efficiently. This tree allows for improved access times for segment queries compared to simpler data structures.

This C++ implementation leverages a segment tree to efficiently calculate the longest subsequence ending at each index within constraints. The segment tree allows us to query and update ranges efficiently.

Code

C++C

C++

C

Complexity

Time Complexity: O(n log M), where n is the length of nums and M is the maximum element in nums.
Space Complexity: O(M), for the segment tree.

Try this approach in the editor →

Approach 3: Segment Tree

We assume that f[v] represents the length of the longest increasing subsequence ending with the number v.

We traverse each element v in the array nums, with the state transition equation: f[v] = max(f[v], f[x]), where the range of x is [v-k, v-1].

Therefore, we need a data structure to maintain the maximum value of the interval. It is not difficult to think of using a segment tree.

The segment tree divides the entire interval into multiple discontinuous subintervals, and the number of subintervals does not exceed log(width). To update the value of an element, only log(width) intervals need to be updated, and these intervals are all contained in a large interval that contains the element.

  • Each node of the segment tree represents an interval;
  • The segment tree has a unique root node, which represents the entire statistical range, such as [1,N];
  • Each leaf node of the segment tree represents an elementary interval of length 1, [x, x];
  • For each internal node [l,r], its left child is [l,mid], and the right child is [mid+1,r], where mid = \left \lfloor \frac{l+r}{2} \right \rfloor.

For this problem, the information maintained by the segment tree node is the maximum value within the interval range.

The time complexity is O(n times log n), where n is the length of the array nums.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Binary Indexed Tree

Time Complexity: O(n log M), where n is the length of the array and M is the maximum element in nums.
Space Complexity: O(M), due to the BIT array.

Segment Tree Optimization

Time Complexity: O(n log M), where n is the length of nums and M is the maximum element in nums.
Space Complexity: O(M), for the segment tree.

Segment Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Quadratic Dynamic ProgrammingO(n²)O(n)Conceptual baseline or when input size is small
DP with Binary Indexed TreeO(n log V)O(V)Efficient when using coordinate compression and prefix queries
Segment Tree OptimizationO(n log V)O(V)Best general solution for fast range maximum queries

Video Solution

2407. Longest Increasing Subsequence II | Leetcode Weekly Contest 310 | LeetCode 2407 • Bro Coders • 7,420 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Longest Increasing Subsequence II easy or hard?
LeetCode classifies Longest Increasing Subsequence II as Hard. The challenge comes from combining LIS-style dynamic programming with efficient range query data structures to meet the required O(n log V) performance.
Longest Increasing Subsequence II Python/Java solution
Python and Java implementations usually rely on a Binary Indexed Tree with coordinate compression or a Segment Tree for range maximum queries. Each step queries the range [x - k, x - 1] to get the best subsequence length and updates the structure with the new value.
How to solve Longest Increasing Subsequence II in O(n)?
A true O(n) solution is not known for the general constraints because the algorithm must repeatedly query ranges of values. The best practical complexity is O(n log V) using a Segment Tree or Binary Indexed Tree to maintain maximum subsequence lengths efficiently.
What is the best approach for Longest Increasing Subsequence II?
The most efficient approach uses dynamic programming combined with a Segment Tree or Binary Indexed Tree. For each number x, query the maximum subsequence length among values in the range [x - k, x - 1], then update the structure with the new length. This reduces the complexity to O(n log V), where V is the value range.
Is Longest Increasing Subsequence II asked at Google/Amazon/Meta?
Variants of LIS with constraints and range queries appear frequently in interviews at companies like Google, Amazon, and Meta. The problem tests dynamic programming combined with advanced data structures such as segment trees and Fenwick trees.
What data structure is used in Longest Increasing Subsequence II?
Segment Trees and Binary Indexed Trees (Fenwick Trees) are commonly used. They support fast range maximum queries and point updates, which are needed to compute the best subsequence length for values within [x − k, x − 1].
What is the time complexity of Longest Increasing Subsequence II?
The optimal solution runs in O(n log V) time using a Segment Tree or Binary Indexed Tree for range maximum queries. Each element performs one query and one update, both taking O(log V). A naive dynamic programming solution takes O(n²) time.

Ready to solve this problem?

Practice Longest Increasing Subsequence II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Booking Concert Tickets in Groups

Next

Longest Continuous Increasing Subsequence