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 (1)

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

  1. Coordinate-compress the values in nums to allow efficient segment tree indexing.
  2. Initialize a segment tree to support range maximum queries and point updates.
  3. 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].
  4. 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

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
 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

// Omitted for brevity. See Python for main logic.

1

// Omitted for brevity. See Python for main logic.

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.