2407. Longest Increasing Subsequence II

Longest Increasing Subsequence II (LeetCode 2407) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.

How to solve Longest Increasing Subsequence II

Longest Increasing Subsequence II is a Longest Increasing Subsequence problem, part of Dynamic Programming (DP) Patterns. Find LIS using DP and binary search optimization. O(n log n) solution.

Work towards the solution in these steps:

1. We can use dynamic programming. Let dp[i][val] be the answer using only the first i + 1 elements, and the last element in the subsequence is equal to val.
2. The only value that might change between dp[i - 1] and dp[i] are dp[i - 1][val] and dp[i][val].
3. Try using dp[i - 1] and the fact that the second last element in the subsequence has to fall within a range to calculate dp[i][val].

The reference solution runs in O(nlogn) time and O(n) space.

The Longest Increasing Subsequence II solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Array, Divide and Conquer, Dynamic Programming, Binary Indexed Tree, Segment Tree, Queue, Monotonic Queue.

How to practise Longest Increasing Subsequence II on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Longest Increasing Subsequence II in the code editor, or read the Longest Increasing Subsequence II editorial for a worked solution with its approach and complexity analysis.

Where Longest Increasing Subsequence II sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• Longest Increasing Subsequence (LIS) subpattern
• The full DSA patterns sheet

Problems related to Longest Increasing Subsequence II

Other problems that use the same Longest Increasing Subsequence (LIS) and Dynamic Programming (DP) Patterns techniques:

• Longest Increasing Subsequence — Medium, same subpattern
• Minimum Number of Removals to Make Mountain Array — Hard, same subpattern
• Russian Doll Envelopes — Hard, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern

Longest Increasing Subsequence II FAQ