You are given an integer array nums and an integer k.
Find the longest subsequence of nums that meets the following requirements:
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 <= 1051 <= nums[i], k <= 105Problem 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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| Segment Tree Optimization | Time Complexity: O(n log M), where n is the length of nums and M is the maximum element in nums. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Quadratic Dynamic Programming | O(n²) | O(n) | Conceptual baseline or when input size is small |
| DP with Binary Indexed Tree | O(n log V) | O(V) | Efficient when using coordinate compression and prefix queries |
| Segment Tree Optimization | O(n log V) | O(V) | Best general solution for fast range maximum queries |
2407. Longest Increasing Subsequence II | Leetcode Weekly Contest 310 | LeetCode 2407 • Bro Coders • 7,174 views views
Watch 5 more video solutions →Practice Longest Increasing Subsequence II with our built-in code editor and test cases.
Practice on FleetCode