Longest Increasing Subsequence II

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

1
2
3
4
5
6


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

1
2
3
4
5


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

1
2
3
4
5


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^5
1 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


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.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Segment Tree Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#