{x}
blog image

Longest Increasing Subsequence II

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

Solution Explanation: Longest Increasing Subsequence II

This problem asks for the length of the longest strictly increasing subsequence where the difference between adjacent elements is at most k. A straightforward approach using dynamic programming is inefficient for large inputs. The optimal solution uses a Segment Tree or Binary Indexed Tree to efficiently manage updates and queries.

Approach: Segment Tree

The core idea revolves around representing the length of the longest increasing subsequence ending at a particular value v as f[v]. We iterate through the input array nums. For each element v, we want to find the maximum length of an increasing subsequence ending at a value within the range [v-k, v-1]. This maximum length plus 1 will be the new length of the increasing subsequence ending at v.

A Segment Tree is ideal for this task because:

  1. Efficient Range Queries: It allows us to quickly find the maximum value within a given range ([v-k, v-1]).
  2. Efficient Updates: Updating the value f[v] is also efficient.

The Segment Tree is built to cover the range of possible values in nums. Each node stores the maximum value in its sub-range.

Algorithm:

  1. Build Segment Tree: Construct a Segment Tree covering the range [1, max(nums)]. Each node stores the maximum length of a subsequence ending at a value within its range. Initially, all values are 0.
  2. Iterate Through nums: For each element v in nums:
    • Query: Use the Segment Tree to find the maximum value (max_len) in the range [v-k, v-1]. This represents the length of the longest increasing subsequence ending at a value less than v and with a difference of at most k.
    • Update: Update the Segment Tree by setting the value at index v to max_len + 1.
    • Track Maximum: Keep track of the overall maximum length encountered so far.
  3. Return Maximum: Return the overall maximum length found.

Time Complexity Analysis:

  • Building the Segment Tree takes O(N) time, where N is the maximum value in nums.
  • Iterating through nums takes O(M) time, where M is the length of nums.
  • Each query and update operation on the Segment Tree takes O(log N) time.
  • Therefore, the overall time complexity is O(M log N). In many cases, N will be significantly larger than M, but this approach is much more efficient than a naive dynamic programming approach with O(M²) complexity.

Space Complexity Analysis:

The space complexity is dominated by the Segment Tree, which requires O(N) space.

Code Examples (Python, Java, C++, Go)

The code examples above demonstrate the implementation of this approach using a Segment Tree in Python, Java, C++, and Go. They all follow the same algorithm but differ in syntax and data structures. Note that the Go solution uses slices.Max from the golang.org/x/exp/slices package. Make sure to go get golang.org/x/exp/slices to use this function.