Command Palette

Search for a command to run...

Hectal
Problem 36.6 · Advanced Data StructuresHard

Longest Increasing Subsequence II

PatternRange Queries (Fenwick & Segment Trees)Longest Increasing Subsequence

What it teaches: A segment tree over values answers "best LIS ending at a value in [v − k, v − 1]" in O(log V).

Practise it on judges as “Longest Increasing Subsequence II”.

In plain words

Pick numbers left to right, each bigger than the last but by at most k. For each value, remember the longest chain that ends with it. A new number x extends the best chain ending at any value from x − k to x − 1. A segment tree answers "best in this range of values" fast.

Return the longest such chain. Example: nums = [4,2,1,4,3,4,5,8,15], k = 3 → 5.

The problem

Return the length of the longest strictly increasing subsequence where adjacent elements differ by at most k.

Example 1

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5

1, 3, 4, 5, 8.

Constraints

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ nums[i], k ≤ 10⁵

Pattern clues in the wording

  • → LIS with a constraint on the previous value
  • → Range maximum over values

These clues point to Range Queries (Fenwick & Segment Trees): Answer sums, minimums or counts over any range while the array keeps changing, in O(log n) per query and update.

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public int lengthOfLIS(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums = [4,2,1,4,3,4,5,8,15]
k = 3
5
2
nums = [7,4,5,1,8,12,4,7]
k = 5
4
3
nums = [1,5]
k = 1
1

From slow to fast

Approaches

1. Segment tree over values · O(n log V)
1

Segment tree over values

Time O(n log V) Space O(V)

Iterative max segment tree of size max value + 1. For each x: best = query(max(0, x − k), x) (exclusive end), update x with best + 1.

▶ Dry run: Best chain ending at each valuenums = [4,2,1,4,3,4,5,8,15], k = 3
1
1
1
2
0
3
1
4
0
5
0
6
0
7
0
8

Step 1/5Cells are values 1 to 8. 4, 2 and 1 find nothing smaller in their range, so each starts a chain of 1.

Approach 1
class Solution {
    private int size;
    private int[] t;

    public int lengthOfLIS(int[] nums, int k) {
        int max = 0;
        for (int x : nums) max = Math.max(max, x);
        size = max + 1;
        t = new int[2 * size];
        int best = 0;
        for (int x : nums) {
            int len = query(Math.max(0, x - k), x) + 1;   // values in [x - k, x - 1]
            update(x, len);
            best = Math.max(best, len);
        }
        return best;
    }

    private void update(int i, int v) {
        i += size;
        if (t[i] >= v) return;
        for (t[i] = v; i > 1; i >>= 1) t[i >> 1] = Math.max(t[i], t[i ^ 1]);
    }

    private int query(int l, int r) {
        int res = 0;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if ((l & 1) == 1) res = Math.max(res, t[l++]);
            if ((r & 1) == 1) res = Math.max(res, t[--r]);
        }
        return res;
    }
}

Verdict: The tails trick doesn't handle the k limit; range max does.

Before you submit

Edge cases and common mistakes

Test these inputs

  • k = 1 (consecutive values only)
  • Repeated values (strictly increasing)

Mistakes people make

  • Using a Fenwick tree for prefix max, which can't restrict the lower end of the range.

Interview

Follow-up questions

Why can't the O(n log n) tails method handle k?