#2407

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Increasing Subsequence II

Determine the longest increasing subsequence in an array where consecutive elements differ by at most k using dynamic programming.

array divide and conquer dynamic programming binary indexed tree segment tree

Problem Statement

Given an integer array nums and an integer k, compute the length of the longest increasing subsequence where the difference between consecutive elements is at most k. Each element in the subsequence must be strictly larger than the previous element but not more than k units apart.

Return the length of this subsequence. Consider the constraints where nums can have up to 10^5 elements and values may be as large as 10^5, requiring an efficient approach that avoids naive O(n^2) comparisons.

Examples

Example 1

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

Output: 5

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

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

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

Solution Approach

Dynamic Programming with State Transition

Define dp[val] as the maximum length of a subsequence ending with value val. Iterate through nums and update dp[val] = max(dp[prev] + 1) for all prev within [val-k, val-1]. This captures the state transition pattern and ensures the subsequence respects the k-difference constraint.

Use Segment Tree or Binary Indexed Tree

To efficiently query the maximum dp value in the range [val-k, val-1], implement a segment tree or BIT. This reduces the time complexity from O(n k) to O(n log(max_val)), making it feasible for large arrays and high k values.

Iterative Update and Result Extraction

Iterate through all nums updating the segment tree with dp[val] after querying the previous range. At the end, the longest increasing subsequence length is the maximum value stored in the tree. This approach avoids redundant recomputation and respects array size constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*log(max_val)) with segment tree or BIT due to log(max_val) query/update per element. Space complexity is O(max_val) for storing dp values and tree structure.

What Interviewers Usually Probe

Looking for efficient use of DP combined with data structures to handle large input.
Expect candidates to recognize the k-difference constraint and avoid naive O(n^2) solutions.
Check understanding of segment trees or BIT for range maximum queries.

Common Pitfalls or Variants

Common pitfalls

Using simple nested loops leading to O(n^2) and timeouts on large inputs.
Ignoring the k-difference restriction and counting non-valid subsequences.
Incorrectly updating dp values before querying the maximum for previous valid values.

Follow-up variants

Longest decreasing subsequence with a similar max difference constraint.
Count the number of longest increasing subsequences under the same k-difference.
Find the subsequence itself, not just its length, respecting the k constraint.

FAQ

What is the main pattern used in Longest Increasing Subsequence II?

The primary pattern is state transition dynamic programming combined with range maximum queries using a segment tree or BIT.

How do you handle the k-difference constraint efficiently?

Use a segment tree or binary indexed tree to query the maximum dp value in the range [val-k, val-1] before updating dp[val].

Can this problem be solved without extra data structures?

Yes, but naive nested loops are O(n*k) and may timeout on large arrays, making segment trees or BIT necessary for performance.

What happens if k is very large?

When k is large relative to the values in nums, the range query may cover most values, so efficiency of the tree or BIT remains crucial.

Is this approach similar to classic LIS?

It extends classic LIS by adding a k-difference constraint and using range queries to maintain valid state transitions efficiently.

terminal

Solution

Solution 1: Segment Tree

We assume that $f[v]$ represents the length of the longest increasing subsequence ending with the number $v$.

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

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

Continue Practicing

#1687 delivering boxes from storage to ports #2426 number of pairs satisfying inequality #2179 count good triplets in an array