Problem statement

Given an integer array nums and an integer k, find the longest subsequence of nums that is

• strictly increasing, and
• has a difference of at most k between every pair of adjacent elements in the subsequence.

Return its length. (A subsequence keeps the original order but may skip elements.)

Example 1

Input: nums = [3,1,6,2,4,7,10], k = 2
Output: 3
Explanation: `[1,2,4]` climbs by 1 and then 2; nothing longer keeps every step at most 2.

Example 2

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation: `[1,3,4,5,8]` — the jump from 8 to 15 is too big.

Example 3

Input: nums = [1,5], k = 1
Output: 1

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i], k <= 10^5

Hints for Longest Increasing Subsequence II

1. Hint 1

   Let best[v] be the length of the longest valid subsequence seen so far that ends with the value v.

2. Hint 2

   Processing nums left to right, a new element x extends the best chain ending at any value in [x - k, x - 1].

3. Hint 3

   You need range-maximum queries and point updates over the value axis — a segment tree indexed by value does both in O(log V).

How to solve Longest Increasing Subsequence II

Run the classic LIS dynamic programme over values instead of indices: the answer for an element x is one more than the best chain ending at a value in the window [x - k, x - 1]. A max segment tree over values answers that window query and absorbs the update in logarithmic time.

Approach

1. Build a max segment tree over values 0..max(nums), all zeros.
2. For each x in order: len = 1 + max(tree[max(0, x - k) .. x - 1]).
3. Update position x to max(tree[x], len) and track the overall maximum.
4. Return the overall maximum.

Why it works

When x is processed, the tree holds, for every value, the longest valid chain ending there using only earlier elements — exactly the candidates x may extend (strictly smaller, at most k below). Taking the maximum over that value window is therefore the correct DP transition, and storing the result at x keeps the invariant for later elements.

Complexity

• Time — O(n log V) with V = max(nums)
• Space — O(V)

Pitfalls

• Strictly increasing: query up to x - 1, not x, so equal values never chain.
• The patience-sorting O(n log n) LIS trick does not carry over — the difference limit breaks its greedy choice.
• Size the tree by the largest value present rather than the 10^5 bound when many small inputs are processed.

Reference solution

Python

from typing import List

def lengthOfLIS(nums: List[int], k: int) -> int:
    size = max(nums) + 1
    tree = [0] * (2 * size)
    best = 0
    for x in nums:
        l = max(0, x - k) + size
        r = x + size
        cur = 0
        while l < r:
            if l & 1:
                if tree[l] > cur:
                    cur = tree[l]
                l += 1
            if r & 1:
                r -= 1
                if tree[r] > cur:
                    cur = tree[r]
            l >>= 1
            r >>= 1
        cur += 1
        if cur > best:
            best = cur
        p = x + size
        if cur > tree[p]:
            tree[p] = cur
            p >>= 1
            while p >= 1:
                tree[p] = max(tree[2 * p], tree[2 * p + 1])
                p >>= 1
    return best

Java

public static int lengthOfLIS(int[] nums, int k) {
    int size = 1;
    for (int v : nums) size = Math.max(size, v + 1);
    int[] tree = new int[2 * size];
    int best = 0;
    for (int x : nums) {
        int l = Math.max(0, x - k) + size, r = x + size, cur = 0;
        while (l < r) {
            if ((l & 1) == 1) cur = Math.max(cur, tree[l++]);
            if ((r & 1) == 1) cur = Math.max(cur, tree[--r]);
            l >>= 1;
            r >>= 1;
        }
        cur += 1;
        best = Math.max(best, cur);
        int p = x + size;
        if (cur > tree[p]) {
            tree[p] = cur;
            for (p >>= 1; p >= 1; p >>= 1) tree[p] = Math.max(tree[2 * p], tree[2 * p + 1]);
        }
    }
    return best;
}

C++

int lengthOfLIS(vector<int>& nums, int k) {
    int size = 1;
    for (int v : nums) size = max(size, v + 1);
    vector<int> tree(2 * size, 0);
    int best = 0;
    for (int x : nums) {
        int l = max(0, x - k) + size, r = x + size, cur = 0;
        while (l < r) {
            if (l & 1) cur = max(cur, tree[l++]);
            if (r & 1) cur = max(cur, tree[--r]);
            l >>= 1;
            r >>= 1;
        }
        cur += 1;
        best = max(best, cur);
        int p = x + size;
        if (cur > tree[p]) {
            tree[p] = cur;
            for (p >>= 1; p >= 1; p >>= 1) tree[p] = max(tree[2 * p], tree[2 * p + 1]);
        }
    }
    return best;
}

JavaScript

var lengthOfLIS = function(nums, k) {
    var size = 1;
    for (var i = 0; i < nums.length; i++) if (nums[i] + 1 > size) size = nums[i] + 1;
    var tree = new Array(2 * size).fill(0);
    var best = 0;
    for (var j = 0; j < nums.length; j++) {
        var x = nums[j];
        var l = Math.max(0, x - k) + size, r = x + size, cur = 0;
        while (l < r) {
            if (l & 1) { if (tree[l] > cur) cur = tree[l]; l++; }
            if (r & 1) { r--; if (tree[r] > cur) cur = tree[r]; }
            l >>= 1;
            r >>= 1;
        }
        cur += 1;
        if (cur > best) best = cur;
        var p = x + size;
        if (cur > tree[p]) {
            tree[p] = cur;
            for (p >>= 1; p >= 1; p >>= 1) tree[p] = Math.max(tree[2 * p], tree[2 * p + 1]);
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard