# Longest Increasing Subsequence II
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-increasing-subsequence-ii)
Canonical: https://scaleengineer.com/dsa/problems/longest-increasing-subsequence-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Binary Indexed Tree, Segment Tree, Queue, Monotonic Queue
---
## 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 the **longest** **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.

**Example 1:**

**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:**

**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:**

**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 <= 105`
* `1 <= nums[i], k <= 105`

# Approaches
## Brute-Force Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define `dp[i]` as the length of the longest valid subsequence ending at index `i`. To compute `dp[i]`, we iterate through all previous elements `nums[j]` (where `j < i`) and check if they can form a valid pair with `nums[i]`. If they can, we update `dp[i]` based on `dp[j]`.
**Time:** O(n^2), where `n` is the length of `nums`. The nested loops iterate through all pairs `(j, i)` with `j < i`, resulting in a quadratic number of operations. · **Space:** O(n), where `n` is the length of `nums`. We use an auxiliary array `dp` of size `n`.
**Pros:** Simple to understand and implement.; It's a direct translation of the problem's recurrence relation.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will result in a Time Limit Exceeded (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
This method is a direct application of dynamic programming for subsequence problems. We build up the solution by finding the longest subsequence ending at each position in the input array.

Let `dp[i]` be the length of the longest increasing subsequence that satisfies the condition and ends with the element `nums[i]`. To calculate `dp[i]`, we look at all previous elements `nums[j]` where `j < i`. If `nums[j]` is smaller than `nums[i]` and their difference is at most `k`, then `nums[i]` can extend the subsequence ending at `nums[j]`. Therefore, we can update `dp[i]` with `1 + dp[j]`. We take the maximum over all such valid `j`'s.

The base case is `dp[i] = 1` for all `i`, as any single element is a valid subsequence of length 1. The final answer is the maximum value in the `dp` array after it has been fully computed.

```java
class Solution {
    public int lengthOfLIS(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && nums[i] - nums[j] <= k) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize an array `dp` of size `n` (the length of `nums`) with all elements set to 1. `dp[i]` will store the length of the longest valid subsequence ending at index `i`.
- Initialize a variable `maxLength` to 1, which will store the final answer.
- Iterate through the `nums` array with an index `i` from 1 to `n-1`.
- For each `i`, iterate through all previous indices `j` from 0 to `i-1`.
- Inside the inner loop, check if `nums[j]` can precede `nums[i]` in a valid subsequence. The conditions are:
  1. `nums[i] > nums[j]` (strictly increasing).
  2. `nums[i] - nums[j] <= k` (difference at most `k`).
- If both conditions are met, it means we can extend the subsequence ending at `j` with `nums[i]`. Update `dp[i]` to the maximum of its current value and `1 + dp[j]`.
- After the inner loop finishes for a given `i`, update `maxLength = max(maxLength, dp[i])`.
- After the outer loop completes, `maxLength` will hold the length of the longest valid subsequence. Return `maxLength`.

## Dynamic Programming with Segment Tree
This approach optimizes the DP solution by changing the state representation and using a powerful data structure. Instead of a DP state based on indices, we use a state based on values: `dp[v]` is the length of the longest valid subsequence ending with value `v`. The key challenge is, for each number `num`, to efficiently find the maximum `dp[v]` where `v` is in the range `[num - k, num - 1]`. This is a range maximum query problem, which can be solved efficiently using a Segment Tree.
**Time:** O(n * log V), where `n` is the length of `nums` and `V` is the maximum value in `nums`. For each of the `n` elements, we perform a query and an update on the Segment Tree, both of which take `O(log V)` time. · **Space:** O(V), where `V` is the maximum value in `nums`. The Segment Tree requires space proportional to the range of values it covers.
**Pros:** Highly efficient and passes the given constraints.; A generalizable technique for optimizing DP problems with range query substructures.
**Cons:** More complex to implement due to the need for a Segment Tree.; Space complexity depends on the range of values (`V`) in `nums`, which might be large even if the number of elements (`n`) is small (though not an issue with the given constraints).
### Explanation
The `O(n^2)` DP approach is slow because for each element, we linearly scan all previous elements. We can optimize this search. The condition `nums[i] > nums[j]` and `nums[i] - nums[j] <= k` is equivalent to finding a `j < i` such that `nums[j]` is in the range `[nums[i] - k, nums[i] - 1]`.

This suggests a DP state based on values rather than indices. Let `lengths[v]` be the length of the longest valid subsequence ending with value `v`. When processing a number `num` from the input, we need to find `1 + max(lengths[v])` for all `v` in `[num - k, num - 1]`. This is a range maximum query.

A Segment Tree is an ideal data structure for this. It can perform range maximum queries and point updates in logarithmic time. We build a segment tree over the range of possible values in `nums` (e.g., `[1, 10^5]`).

For each `num` in `nums`, we query the segment tree for the maximum length in the range `[max(1, num - k), num - 1]`. Let the result be `L`. The new length for a subsequence ending in `num` is `L + 1`. We then update the segment tree at position `num` with this new length. The overall maximum length found during this process is the answer.

```java
class Solution {
    // Segment Tree array
    int[] tree;
    // The size of the value range the tree covers
    int valueRange;

    // Helper to build/initialize the tree
    private void build(int size) {
        valueRange = size;
        tree = new int[4 * valueRange];
    }

    // Helper to update a value at a specific index (value)
    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
    }

    // Helper to query for the maximum value in a given range [l, r]
    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l || l > r) {
            return 0; // Return 0 for no overlap or invalid range
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        int p1 = query(2 * node, start, mid, l, r);
        int p2 = query(2 * node + 1, mid + 1, end, l, r);
        return Math.max(p1, p2);
    }

    public int lengthOfLIS(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        build(maxVal);
        int ans = 0;

        for (int num : nums) {
            int startRange = Math.max(1, num - k);
            int endRange = num - 1;

            int prevMaxLen = query(1, 1, valueRange, startRange, endRange);
            int currentLen = prevMaxLen + 1;

            update(1, 1, valueRange, num, currentLen);
            ans = Math.max(ans, currentLen);
        }
        return ans;
    }
}
```
### Algorithm
- Determine the maximum possible value `maxVal` in `nums` to set the range for our data structure.
- Initialize a Segment Tree data structure that can perform range maximum queries and point updates over the values `[1, maxVal]`. All lengths in the tree are initialized to 0.
- Initialize a variable `ans` to 0 to track the maximum length found so far.
- Iterate through each number `num` in the input array `nums`.
- For each `num`, determine the query range for valid preceding values: `[max(1, num - k), num - 1]`.
- Query the Segment Tree for the maximum length within this range. Let this be `prevMaxLen`.
- The length of the longest subsequence ending with the current `num` is `currentLen = 1 + prevMaxLen`.
- Update the Segment Tree at index `num` with this new `currentLen`.
- Update the overall answer: `ans = max(ans, currentLen)`.
- After iterating through all numbers, `ans` will be the final result.

# Solutions
### Java

```java
class Solution {
public
  int lengthOfLIS(int[] nums, int k) {
    int mx = nums[0];
    for (int v : nums) {
      mx = Math.max(mx, v);
    }
    SegmentTree tree = new SegmentTree(mx);
    int ans = 0;
    for (int v : nums) {
      int t = tree.query(1, v - k, v - 1) + 1;
      ans = Math.max(ans, t);
      tree.modify(1, v, t);
    }
    return ans;
  }
} class Node {
  int l;
  int r;
  int v;
} class SegmentTree {
private
  Node[] tr;
public
  SegmentTree(int n) {
    tr = new Node[4 * n];
    for (int i = 0; i < tr.length; ++i) {
      tr[i] = new Node();
    }
    build(1, 1, n);
  }
public
  void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
  }
public
  void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {
      tr[u].v = v;
      return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) {
      modify(u << 1, x, v);
    } else {
      modify(u << 1 | 1, x, v);
    }
    pushup(u);
  }
public
  void pushup(int u) { tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v); }
public
  int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
      return tr[u].v;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    int v = 0;
    if (l <= mid) {
      v = query(u << 1, l, r);
    }
    if (r > mid) {
      v = Math.max(v, query(u << 1 | 1, l, r));
    }
    return v;
  }
}

```

### CPP

```cpp
class Node { public: int l ; int r ; int v ; }; class SegmentTree { public: vector < Node *> tr ; SegmentTree ( int n ) { tr . resize ( 4 * n ); for ( int i = 0 ; i < tr . size (); ++ i ) tr [ i ] = new Node (); build ( 1 , 1 , n ); } void build ( int u , int l , int r ) { tr [ u ] -> l = l ; tr [ u ] -> r = r ; if ( l == r ) return ; int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); } void modify ( int u , int x , int v ) { if ( tr [ u ] -> l == x && tr [ u ] -> r == x ) { tr [ u ] -> v = v ; return ; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; if ( x <= mid ) modify ( u << 1 , x , v ); else modify ( u << 1 | 1 , x , v ); pushup ( u ); } void pushup ( int u ) { tr [ u ] -> v = max ( tr [ u << 1 ] -> v , tr [ u << 1 | 1 ] -> v ); } int query ( int u , int l , int r ) { if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) return tr [ u ] -> v ; int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; int v = 0 ; if ( l <= mid ) v = query ( u << 1 , l , r ); if ( r > mid ) v = max ( v , query ( u << 1 | 1 , l , r )); return v ; } }; class Solution { public: int lengthOfLIS ( vector < int >& nums , int k ) { SegmentTree * tree = new SegmentTree ( * max_element ( nums . begin (), nums . end ())); int ans = 1 ; for ( int v : nums ) { int t = tree -> query ( 1 , v - k , v - 1 ) + 1 ; ans = max ( ans , t ); tree -> modify ( 1 , v , t ); } return ans ; } };
```

### Python

```python
class Node : def __init__ ( self ): self . l = 0 self . r = 0 self . v = 0 class SegmentTree : def __init__ ( self , n ): self . tr = [ Node () for _ in range ( 4 * n )] self . build ( 1 , 1 , n ) def build ( self , u , l , r ): self . tr [ u ]. l = l self . tr [ u ]. r = r if l == r : return mid = ( l + r ) >> 1 self . build ( u << 1 , l , mid ) self . build ( u << 1 | 1 , mid + 1 , r ) def modify ( self , u , x , v ): if self . tr [ u ]. l == x and self . tr [ u ]. r == x : self . tr [ u ]. v = v return mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 if x <= mid : self . modify ( u << 1 , x , v ) else : self . modify ( u << 1 | 1 , x , v ) self . pushup ( u ) def pushup ( self , u ): self . tr [ u ]. v = max ( self . tr [ u << 1 ]. v , self . tr [ u << 1 | 1 ]. v ) def query ( self , u , l , r ): if self . tr [ u ]. l >= l and self . tr [ u ]. r <= r : return self . tr [ u ]. v mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 v = 0 if l <= mid : v = self . query ( u << 1 , l , r ) if r > mid : v = max ( v , self . query ( u << 1 | 1 , l , r )) return v class Solution : def lengthOfLIS ( self , nums : List [ int ], k : int ) -> int : tree = SegmentTree ( max ( nums )) ans = 1 for v in nums : t = tree . query ( 1 , v - k , v - 1 ) + 1 ans = max ( ans , t ) tree . modify ( 1 , v , t ) return ans
```