#2407
Longest Increasing Subsequence II
Hard Segment tree over values (range max)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the longest strictly increasing subsequence where each pair of neighbouring elements differs by at most k.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest increasing subsequence where neighbouring values differ by at most k.
Why this works: best[v] = the longest run ending with value v. For x, ask the max of best over [x-k, x-1], a range max query on a segment tree.
Example: [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3
1 → 3 → 4 → 5 → 8 → length 5✦Hints open one at a time
best[v] = longest valid subsequence ending with value v.
For a new value x, you need max best[v] for v in [x − k, x − 1] — a range maximum query.
Values are up to 10^5, so a segment tree indexed by value works directly.
↗Approach
For each x: len = 1 + query(max(1, x − k), x − 1); then point-update position x with len (keep the max). Track the overall best.
</>Solution (Java)
class Solution {
private int size;
private int[] tree;
public int lengthOfLIS(int[] nums, int k) {
int max = 0;
for (int x : nums) max = Math.max(max, x);
size = 1;
while (size <= max) size <<= 1;
tree = new int[2 * size]; // iterative segment tree, leaves at size..2*size-1
int best = 0;
for (int x : nums) {
int len = 1 + query(Math.max(1, x - k), x - 1);
update(x, len);
best = Math.max(best, len);
}
return best;
}
private void update(int pos, int val) {
int i = pos + size;
tree[i] = Math.max(tree[i], val);
for (i >>= 1; i >= 1; i >>= 1) tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
}
// max over [l, r]
private int query(int l, int r) {
if (l > r) return 0;
int res = 0;
for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) res = Math.max(res, tree[l++]);
if ((r & 1) == 1) res = Math.max(res, tree[--r]);
}
return res;
}
}!Common mistake
Using the O(n²) LIS DP — too slow for n = 10^5.
Complexity
- Time: O(n log M).
- Space: O(M).
Topic: Segment Tree, Fenwick & Sparse Table
🎬 Episodes 98–100: video coming soon