Longest Increasing Subsequence II

Longest Increasing Subsequence II

What is this problem about?

The Longest Increasing Subsequence II is a significantly harder variation of the classic LIS problem. You are given an integer array nums and an integer k. You need to find the length of the longest strictly increasing subsequence where the difference between any two adjacent elements in the subsequence is at most k. So, it must be increasing, but it can't jump up by too much at once.

Why is this asked in interviews?

This problem is a phenomenal gauge of a senior candidate's algorithmic depth. A standard DP approach takes $O(N^2)$, which is too slow for the tight constraints typically imposed on this problem. The interviewer wants to see if you can recognize that finding the "best previous element" can be modeled as a Range Maximum Query. It rigorously tests your ability to implement advanced data structures like Segment Trees or Binary Indexed Trees (Fenwick Trees).

Algorithmic pattern used

This problem leverages Dynamic Programming optimized by a Segment Tree (or Binary Indexed Tree). Let dp[x] be the length of the longest valid subsequence ending with the value x. When processing nums[i], the best element to append it to is the one that gives the maximum dp value in the value range [nums[i] - k, nums[i] - 1]. A Segment Tree allows us to query this maximum in $O(\log M)$ time (where $M$ is the max value in the array) and update dp[nums[i]] in $O(\log M)$ time.

Example explanation

Let nums = [4, 2, 1, 4, 3, 4, 5, 8, 15] and k = 3. We process elements one by one, using a Segment Tree to query the max length ending in the range [current - 3, current - 1].

• For 4: Query range [1, 3]. Max is 0. Update tree[4] = 1.
• For 2: Query range [0, 1]. Max is 0. Update tree[2] = 1.
• For 1: Query range [0, 0]. Max is 0. Update tree[1] = 1.
• For 3: Query range [0, 2]. Max is tree[2] or tree[1] which is 1. Update tree[3] = 1 + 1 = 2. (Sequence: [2, 3] or [1, 3]).
• For 5: Query range [2, 4]. Max is tree[3] or tree[4] which is 2. Update tree[5] = 2 + 1 = 3. (Sequence: [2, 3, 5]). By looking up the best previous tail in the allowed range, we build the longest sequence efficiently.

Common mistakes candidates make

The most prevalent mistake is writing the standard $O(N^2)$ nested loop DP solution, checking if (nums[i] > nums[j] && nums[i] - nums[j] <= k). This will immediately trigger a Time Limit Exceeded error. Another mistake when building the Segment Tree is making its size based on N (the length of the array) instead of $M$ (the maximum possible value in the array), since we are querying based on values, not indices.

Interview preparation tip

To master the Longest Increasing Subsequence II coding problem, you must become fluent in writing a basic Segment Tree. Practice writing a Segment Tree class from scratch that supports update(index, value) and query(left, right). Once you understand that DP states can be indexed by value rather than array position, this problem transforms from a scary DP puzzle into a straightforward Range Query task.