Longest Increasing Subsequence II
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 thelongest 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.
Examples
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 <= 10^51 <= nums[i], k <= 10^5
Solution
Method 1 – Segment Tree Dynamic Programming
Intuition
To efficiently find the longest increasing subsequence with adjacent difference at most k, we use a segment tree (or binary indexed tree) to keep track of the maximum dp value for all possible previous numbers in the valid range. For each number, we query the segment tree for the best previous result and update the tree with the new dp value.
Approach
- Coordinate-compress the values in nums to allow efficient segment tree indexing.
- Initialize a segment tree to support range maximum queries and point updates.
- For each number x in nums:
- Query the segment tree for the maximum dp value in the range [x-k, x-1].
- Set dp[x] = max_query + 1.
- Update the segment tree at position x with dp[x].
- The answer is the maximum value in the dp array.
Code
C++
class SegmentTree {
vector<int> tree;
int n;
public:
SegmentTree(int size) : n(size), tree(2*size) {}
void update(int i, int val) {
i += n;
tree[i] = max(tree[i], val);
for (i /= 2; i > 0; i /= 2)
tree[i] = max(tree[2*i], tree[2*i+1]);
}
int query(int l, int r) {
int res = 0;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l%2) res = max(res, tree[l++]);
if (r%2) res = max(res, tree[--r]);
}
return res;
}
};
class Solution {
public:
int lengthOfLIS(vector<int>& nums, int k) {
set<int> s(nums.begin(), nums.end());
vector<int> vals(s.begin(), s.end());
unordered_map<int, int> idx;
for (int i = 0; i < vals.size(); ++i) idx[vals[i]] = i;
SegmentTree st(vals.size());
int ans = 0;
for (int x : nums) {
int l = lower_bound(vals.begin(), vals.end(), x-k) - vals.begin();
int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
int best = st.query(l, r);
int cur = best + 1;
st.update(idx[x], cur);
ans = max(ans, cur);
}
return ans;
}
};
Go
import (
"sort"
)
type SegmentTree struct {
tree []int
n int
}
func NewSegmentTree(size int) *SegmentTree {
return &SegmentTree{
tree: make([]int, 2*size),
n: size,
}
}
func (st *SegmentTree) update(i, val int) {
i += st.n
if st.tree[i] < val {
st.tree[i] = val
}
for i /= 2; i > 0; i /= 2 {
st.tree[i] = max(st.tree[2*i], st.tree[2*i+1])
}
}
func (st *SegmentTree) query(l, r int) int {
res := 0
l += st.n
r += st.n
for l < r {
if l%2 == 1 {
res = max(res, st.tree[l])
l++
}
if r%2 == 1 {
r--
res = max(res, st.tree[r])
}
l /= 2
r /= 2
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func lengthOfLIS(nums []int, k int) int {
// Get unique values and sort them
valSet := make(map[int]bool)
for _, num := range nums {
valSet[num] = true
}
vals := make([]int, 0, len(valSet))
for val := range valSet {
vals = append(vals, val)
}
sort.Ints(vals)
// Create index mapping
idx := make(map[int]int)
for i, val := range vals {
idx[val] = i
}
st := NewSegmentTree(len(vals))
ans := 0
for _, x := range nums {
// Find range [x-k, x)
l := sort.SearchInts(vals, x-k)
r := sort.SearchInts(vals, x)
best := st.query(l, r)
cur := best + 1
st.update(idx[x], cur)
ans = max(ans, cur)
}
return ans
}
Java
import java.util.*;
class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int size) {
this.n = size;
this.tree = new int[2 * size];
}
public void update(int i, int val) {
i += n;
tree[i] = Math.max(tree[i], val);
for (i /= 2; i > 0; i /= 2) {
tree[i] = Math.max(tree[2*i], tree[2*i+1]);
}
}
public int query(int l, int r) {
int res = 0;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l % 2 == 1) res = Math.max(res, tree[l++]);
if (r % 2 == 1) res = Math.max(res, tree[--r]);
}
return res;
}
}
class Solution {
public int lengthOfLIS(int[] nums, int k) {
Set<Integer> valSet = new TreeSet<>();
for (int num : nums) {
valSet.add(num);
}
List<Integer> vals = new ArrayList<>(valSet);
Map<Integer, Integer> idx = new HashMap<>();
for (int i = 0; i < vals.size(); i++) {
idx.put(vals.get(i), i);
}
SegmentTree st = new SegmentTree(vals.size());
int ans = 0;
for (int x : nums) {
int l = Collections.binarySearch(vals, x - k);
if (l < 0) l = -l - 1;
int r = Collections.binarySearch(vals, x);
if (r < 0) r = -r - 1;
int best = st.query(l, r);
int cur = best + 1;
st.update(idx.get(x), cur);
ans = Math.max(ans, cur);
}
return ans;
}
}
Kotlin
class SegmentTree(size: Int) {
private val tree = IntArray(2 * size)
private val n = size
fun update(i: Int, `val`: Int) {
var idx = i + n
tree[idx] = maxOf(tree[idx], `val`)
idx /= 2
while (idx > 0) {
tree[idx] = maxOf(tree[2 * idx], tree[2 * idx + 1])
idx /= 2
}
}
fun query(l: Int, r: Int): Int {
var res = 0
var left = l + n
var right = r + n
while (left < right) {
if (left % 2 == 1) {
res = maxOf(res, tree[left])
left++
}
if (right % 2 == 1) {
right--
res = maxOf(res, tree[right])
}
left /= 2
right /= 2
}
return res
}
}
class Solution {
fun lengthOfLIS(nums: IntArray, k: Int): Int {
val vals = nums.toSet().sorted()
val idx = vals.withIndex().associate { it.value to it.index }
val st = SegmentTree(vals.size)
var ans = 0
for (x in nums) {
val l = vals.binarySearch(x - k).let { if (it < 0) -it - 1 else it }
val r = vals.binarySearch(x).let { if (it < 0) -it - 1 else it }
val best = st.query(l, r)
val cur = best + 1
st.update(idx[x]!!, cur)
ans = maxOf(ans, cur)
}
return ans
}
}
Python
class SegmentTree:
def __init__(self, size):
self.N = 1
while self.N < size:
self.N <<= 1
self.tree = [0] * (2*self.N)
def update(self, i, val):
i += self.N
self.tree[i] = max(self.tree[i], val)
while i > 1:
i //= 2
self.tree[i] = max(self.tree[2*i], self.tree[2*i+1])
def query(self, l, r):
res = 0
l += self.N
r += self.N
while l < r:
if l % 2:
res = max(res, self.tree[l])
l += 1
if r % 2:
r -= 1
res = max(res, self.tree[r])
l //= 2
r //= 2
return res
class Solution:
def lengthOfLIS(self, nums: list[int], k: int) -> int:
vals = sorted(set(nums))
idx = {v: i for i, v in enumerate(vals)}
st = SegmentTree(len(vals))
ans = 0
for x in nums:
l = bisect.bisect_left(vals, x-k)
r = bisect.bisect_left(vals, x)
best = st.query(l, r)
cur = best + 1
st.update(idx[x], cur)
ans = max(ans, cur)
return ans
Rust
use std::collections::{HashMap, BTreeSet};
struct SegmentTree {
tree: Vec<i32>,
n: usize,
}
impl SegmentTree {
fn new(size: usize) -> Self {
Self {
tree: vec![0; 2 * size],
n: size,
}
}
fn update(&mut self, mut i: usize, val: i32) {
i += self.n;
self.tree[i] = self.tree[i].max(val);
i /= 2;
while i > 0 {
self.tree[i] = self.tree[2 * i].max(self.tree[2 * i + 1]);
i /= 2;
}
}
fn query(&self, mut l: usize, mut r: usize) -> i32 {
let mut res = 0;
l += self.n;
r += self.n;
while l < r {
if l % 2 == 1 {
res = res.max(self.tree[l]);
l += 1;
}
if r % 2 == 1 {
r -= 1;
res = res.max(self.tree[r]);
}
l /= 2;
r /= 2;
}
res
}
}
impl Solution {
pub fn length_of_lis(nums: Vec<i32>, k: i32) -> i32 {
let val_set: BTreeSet<i32> = nums.iter().cloned().collect();
let vals: Vec<i32> = val_set.into_iter().collect();
let idx: HashMap<i32, usize> = vals.iter()
.enumerate()
.map(|(i, &v)| (v, i))
.collect();
let mut st = SegmentTree::new(vals.len());
let mut ans = 0;
for x in nums {
let l = vals.binary_search(&(x - k))
.unwrap_or_else(|i| i);
let r = vals.binary_search(&x)
.unwrap_or_else(|i| i);
let best = st.query(l, r);
let cur = best + 1;
st.update(idx[&x], cur);
ans = ans.max(cur);
}
ans
}
}
TypeScript
class SegmentTree {
private tree: number[];
private n: number;
constructor(size: number) {
this.n = size;
this.tree = new Array(2 * size).fill(0);
}
update(i: number, val: number): void {
i += this.n;
this.tree[i] = Math.max(this.tree[i], val);
for (i = Math.floor(i / 2); i > 0; i = Math.floor(i / 2)) {
this.tree[i] = Math.max(this.tree[2 * i], this.tree[2 * i + 1]);
}
}
query(l: number, r: number): number {
let res = 0;
l += this.n;
r += this.n;
while (l < r) {
if (l % 2 === 1) {
res = Math.max(res, this.tree[l]);
l++;
}
if (r % 2 === 1) {
r--;
res = Math.max(res, this.tree[r]);
}
l = Math.floor(l / 2);
r = Math.floor(r / 2);
}
return res;
}
}
function lengthOfLIS(nums: number[], k: number): number {
const valSet = new Set(nums);
const vals = Array.from(valSet).sort((a, b) => a - b);
const idx = new Map<number, number>();
vals.forEach((val, i) => idx.set(val, i));
const st = new SegmentTree(vals.length);
let ans = 0;
for (const x of nums) {
const l = binarySearchLeft(vals, x - k);
const r = binarySearchLeft(vals, x);
const best = st.query(l, r);
const cur = best + 1;
st.update(idx.get(x)!, cur);
ans = Math.max(ans, cur);
}
return ans;
}
function binarySearchLeft(arr: number[], target: number): number {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
Complexity
- ⏰ Time complexity:
O(n log n), where n is the length of nums. Each update/query is O(log n). - 🧺 Space complexity:
O(n), for the segment tree and coordinate compression.