Longest Increasing Subsequence II - Video Solutions

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.