Longest Increasing Subsequence II
HardPrompt
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 <= 1051 <= nums[i], k <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward dynamic programming solution. We define dp[i] as the length of the longest valid subsequence ending at index i. To compute dp[i], we iterate through all previous elements nums[j] (where j < i) and check if they can form a valid pair with nums[i]. If they can, we update dp[i] based on dp[j].
Algorithm
- Initialize an array
dpof sizen(the length ofnums) with all elements set to 1.dp[i]will store the length of the longest valid subsequence ending at indexi. - Initialize a variable
maxLengthto 1, which will store the final answer. - Iterate through the
numsarray with an indexifrom 1 ton-1. - For each
i, iterate through all previous indicesjfrom 0 toi-1. - Inside the inner loop, check if
nums[j]can precedenums[i]in a valid subsequence. The conditions are:nums[i] > nums[j](strictly increasing).nums[i] - nums[j] <= k(difference at mostk).
- If both conditions are met, it means we can extend the subsequence ending at
jwithnums[i]. Updatedp[i]to the maximum of its current value and1 + dp[j]. - After the inner loop finishes for a given
i, updatemaxLength = max(maxLength, dp[i]). - After the outer loop completes,
maxLengthwill hold the length of the longest valid subsequence. ReturnmaxLength.
Walkthrough
This method is a direct application of dynamic programming for subsequence problems. We build up the solution by finding the longest subsequence ending at each position in the input array.
Let dp[i] be the length of the longest increasing subsequence that satisfies the condition and ends with the element nums[i]. To calculate dp[i], we look at all previous elements nums[j] where j < i. If nums[j] is smaller than nums[i] and their difference is at most k, then nums[i] can extend the subsequence ending at nums[j]. Therefore, we can update dp[i] with 1 + dp[j]. We take the maximum over all such valid j's.
The base case is dp[i] = 1 for all i, as any single element is a valid subsequence of length 1. The final answer is the maximum value in the dp array after it has been fully computed.
class Solution { public int lengthOfLIS(int[] nums, int k) { int n = nums.length; if (n == 0) { return 0; } int[] dp = new int[n]; java.util.Arrays.fill(dp, 1); int maxLength = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j] && nums[i] - nums[j] <= k) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } maxLength = Math.max(maxLength, dp[i]); } return maxLength; }}Complexity
Time
O(n^2), where `n` is the length of `nums`. The nested loops iterate through all pairs `(j, i)` with `j < i`, resulting in a quadratic number of operations.
Space
O(n), where `n` is the length of `nums`. We use an auxiliary array `dp` of size `n`.
Trade-offs
Pros
Simple to understand and implement.
It's a direct translation of the problem's recurrence relation.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will result in a Time Limit Exceeded (TLE) error on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution {public int lengthOfLIS(int[] nums, int k) { int mx = nums[0]; for (int v : nums) { mx = Math.max(mx, v); } SegmentTree tree = new SegmentTree(mx); int ans = 0; for (int v : nums) { int t = tree.query(1, v - k, v - 1) + 1; ans = Math.max(ans, t); tree.modify(1, v, t); } return ans; }} class Node { int l; int r; int v;} class SegmentTree {private Node[] tr;public SegmentTree(int n) { tr = new Node[4 * n]; for (int i = 0; i < tr.length; ++i) { tr[i] = new Node(); } build(1, 1, n); }public void build(int u, int l, int r) { tr[u].l = l; tr[u].r = r; if (l == r) { return; } int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); }public void modify(int u, int x, int v) { if (tr[u].l == x && tr[u].r == x) { tr[u].v = v; return; } int mid = (tr[u].l + tr[u].r) >> 1; if (x <= mid) { modify(u << 1, x, v); } else { modify(u << 1 | 1, x, v); } pushup(u); }public void pushup(int u) { tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v); }public int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { return tr[u].v; } int mid = (tr[u].l + tr[u].r) >> 1; int v = 0; if (l <= mid) { v = query(u << 1, l, r); } if (r > mid) { v = Math.max(v, query(u << 1 | 1, l, r)); } return v; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.