How hard is LeetCode 2407. Longest Increasing Subsequence II?

LeetCode 2407. Longest Increasing Subsequence II is rated Hard on LeetCode.

Longest Increasing Subsequence II — LeetCode 2407 Python Solution

HardBinary Indexed TreeSegment TreeQueueArrayDivide and ConquerDynamic ProgrammingMonotonic Queue

Problem: #2407
Pattern: Stack
Reading time: 10 min
Source: leetcode.com

The 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.

Example

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].

Python solution

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

Complexity

Measure	Complexity
Time	O(n \times \log n), where n is the length of the array nums
Space	O(n·m) or optimized auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2407. Longest Increasing Subsequence II is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2407. Longest Increasing Subsequence II?: LeetCode 2407. Longest Increasing Subsequence II is rated Hard on LeetCode.
What topics does LeetCode 2407. Longest Increasing Subsequence II cover?: LeetCode 2407. Longest Increasing Subsequence II is tagged Binary Indexed Tree, Segment Tree, Queue, Array, Divide and Conquer, Dynamic Programming and Monotonic Queue on LeetCode.