Longest Increasing Subsequence II

How it works

We want the longest increasing subsequence where consecutive values differ by at most k.

Instead of DP over indices (dp[i]), think DP over values:

• Let best[x] = the best LIS length of any valid subsequence that ends with value x.

When we process a value num, the previous value must be:

• strictly smaller than num
• and within distance k

So the previous value must lie in the range:

• [num - k, num - 1]

That means:

• dpEndingAtNum = 1 + max(best[v]) for v ∈ [num-k, num-1]

We need a data structure that supports:

• Range maximum query over [num-k, num-1]
• Point update at index num with the new best value

A segment tree supports both in O(log M) where M is the maximum value we index.

Steps

1. Let M = max(nums) and build a segment tree over indices [0 .. M], where each index x stores best[x] (initially all zeros).
2. Initialize res = 0.
3. For each num in nums (left to right):
   • Compute query bounds:
     • l = max(0, num - k)
     • r = num - 1
   • If r < l, then there is no valid smaller value → bestPrev = 0 else bestPrev = segmentTree.query(l, r)
   • curr = bestPrev + 1
   • Update: segmentTree.update(num, curr) (keep the maximum at num)
   • res = max(res, curr)
4. Return res.

Complexity

• Time complexity: O(nlog m)
• Space complexity: O(m)

Where n is the size of the array nums and m is the maximum element in the array.

Things to watch for

Querying an Invalid Range

When the current number minus k is less than or equal to zero, or when num - 1 is less than num - k, the query range becomes invalid. You must handle the case where there are no valid previous values to extend from, which means the current element starts a new subsequence of length 1.

Using the Wrong Data Structure

This problem requires efficient range maximum queries and point updates. Using a simple DP array results in O(n*k) time complexity per element, which is too slow. A segment tree or similar data structure is necessary to achieve the O(log m) per-operation complexity needed for this problem.

Off-by-One in Range Boundaries

The constraint requires nums[j] - nums[i] <= k with strict inequality nums[j] > nums[i]. This means you should query the range [num - k, num - 1], not [num - k, num]. Including num in the query would violate the strictly increasing requirement.

Not Using Coordinate Compression When Needed

When the maximum value in nums is very large but the number of distinct values is small, building a segment tree of size max(nums) wastes memory. Coordinate compression maps values to a smaller range, but you must ensure the compressed values maintain their relative ordering and the distance constraint is correctly applied to the original values, not the compressed indices.

Updating Before Querying

The order of operations matters: you must query for the best previous subsequence before updating the current position. Updating first can cause the current element to incorrectly contribute to its own computation, leading to wrong answers.

from typing import List

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.tree = [0] * (2 * self.n)

    def update(self, i, val):
        if val <= self.tree[self.n + i]:
            return
        self.tree[self.n + i] = val
        j = (self.n + i) >> 1
        while j >= 1:
            self.tree[j] = max(self.tree[j << 1], self.tree[j << 1 | 1])
            j >>= 1

    def query(self, ql, qh):
        l = ql + self.n
        r = qh + self.n + 1
        res = 0
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_val = max(nums)
        ST = SegmentTree(max_val + 1)
        res = 0
        for num in nums:
            l = max(0, num - k)
            r = max(0, num - 1)
            curr = ST.query(l, r) + 1
            res = max(res, curr)
            ST.update(num, curr)

        return res

class SegmentTree {
public:
    int n;
    vector<int> tree;

    SegmentTree(int N) {
        n = N;
        while ((n & (n - 1)) != 0) {
            n++;
        }
        tree.resize(2 * n, 0);
    }

    void update(int i, int val) {
        if (val <= tree[n + i]) return;
        tree[n + i] = val;
        for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
            tree[j] = max(tree[j << 1], tree[(j << 1) + 1]);
        }
    }

    int query(int l, int r) {
        l += n;
        r += n + 1;
        int res = 0;
        while (l < r) {
            if (l & 1) {
                res = max(res, tree[l++]);
            }
            if (r & 1) {
                res = max(res, tree[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        int maxVal = *max_element(nums.begin(), nums.end());
        SegmentTree ST(maxVal + 1);
        int res = 0;
        for (int& num : nums) {
            int l = max(0, num - k);
            int r = max(0, num - 1);
            int curr = ST.query(l, r) + 1;
            res = max(res, curr);
            ST.update(num, curr);
        }
        return res;
    }
};