How to Solve Longest Increasing Subsequence II

Start by applying dynamic programming with state transitions to track subsequences ending at each value. Use a segment tree or binary indexed tree to efficiently query the maximum subsequence length for previous values within k distance. This approach ensures each extension respects the max difference constraint while building the longest valid subsequence.

Problem Statement

Given an integer array nums and an integer k, compute the length of the longest increasing subsequence where the difference between consecutive elements is at most k. Each element in the subsequence must be strictly larger than the previous element but not more than k units apart.

Return the length of this subsequence. Consider the constraints where nums can have up to 10^5 elements and values may be as large as 10^5, requiring an efficient approach that avoids naive O(n^2) comparisons.

Examples

Example 1

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3

Output: 5

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

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

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

Solution Approach

Dynamic Programming with State Transition

Define dp[val] as the maximum length of a subsequence ending with value val. Iterate through nums and update dp[val] = max(dp[prev] + 1) for all prev within [val-k, val-1]. This captures the state transition pattern and ensures the subsequence respects the k-difference constraint.

Use Segment Tree or Binary Indexed Tree

To efficiently query the maximum dp value in the range [val-k, val-1], implement a segment tree or BIT. This reduces the time complexity from O(nk) to O(nlog(max_val)), making it feasible for large arrays and high k values.

Iterative Update and Result Extraction

Iterate through all nums updating the segment tree with dp[val] after querying the previous range. At the end, the longest increasing subsequence length is the maximum value stored in the tree. This approach avoids redundant recomputation and respects array size constraints.

Complexity Analysis

Time complexity is O(n*log(max_val)) with segment tree or BIT due to log(max_val) query/update per element. Space complexity is O(max_val) for storing dp values and tree structure.

What Interviewers Usually Probe

• Looking for efficient use of DP combined with data structures to handle large input.
• Expect candidates to recognize the k-difference constraint and avoid naive O(n^2) solutions.
• Check understanding of segment trees or BIT for range maximum queries.

Common Pitfalls or Variants

Common pitfalls

• Using simple nested loops leading to O(n^2) and timeouts on large inputs.
• Ignoring the k-difference restriction and counting non-valid subsequences.
• Incorrectly updating dp values before querying the maximum for previous valid values.

Follow-up variants

• Longest decreasing subsequence with a similar max difference constraint.
• Count the number of longest increasing subsequences under the same k-difference.
• Find the subsequence itself, not just its length, respecting the k constraint.

How GhostInterview Helps

• Automatically translates the problem into a DP state transition framework.
• Suggests segment tree or BIT for efficient range queries matching the problem's performance needs.
• Highlights edge cases and correct value updates to avoid common mistakes with k-difference subsequences.

Topic Pages

• Array
• Divide and Conquer
• Dynamic Programming
• Binary Indexed Tree
• Segment Tree
• Queue
• Monotonic Queue

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Longest Increasing Subsequence II?

The primary pattern is state transition dynamic programming combined with range maximum queries using a segment tree or BIT.

How do you handle the k-difference constraint efficiently?

Use a segment tree or binary indexed tree to query the maximum dp value in the range [val-k, val-1] before updating dp[val].

Can this problem be solved without extra data structures?

Yes, but naive nested loops are O(n*k) and may timeout on large arrays, making segment trees or BIT necessary for performance.

What happens if k is very large?

When k is large relative to the values in nums, the range query may cover most values, so efficiency of the tree or BIT remains crucial.

Is this approach similar to classic LIS?

It extends classic LIS by adding a k-difference constraint and using range queries to maintain valid state transitions efficiently.