LeetCode 2407 - Longest Increasing Subsequence II

LeetCode Problem 2407

Difficulty: 🔴 Hard
Topics: Array, Divide and Conquer, Dynamic Programming, Binary Indexed Tree, Segment Tree, Queue, Monotonic Queue

Solution

Problem Understanding

The problem asks us to find the length of the longest subsequence in an integer array nums such that the subsequence is strictly increasing and the difference between consecutive elements does not exceed a given integer k. A subsequence is formed by deleting zero or more elements from the array without reordering the remaining elements.

The input nums is an array of integers with length up to 100,000, and each element can be as large as 100,000. The integer k also ranges up to 100,000. The output is a single integer representing the maximum possible length of a valid subsequence that satisfies both constraints.

The key challenges are the size of the input and the second constraint on the maximum allowed difference between consecutive elements. A naive solution that considers all subsequences will be far too slow. Important edge cases include arrays that are already strictly increasing, arrays where no two elements can be part of the same valid subsequence due to k, and arrays with repeated elements.

Approaches

The brute-force approach would attempt to generate all possible subsequences, check if each is strictly increasing and respects the k difference, and then track the maximum length. This is correct but infeasible due to the combinatorial number of subsequences: O(2^n) for an array of length n.

A better solution leverages dynamic programming along with an efficient data structure to query the maximum subsequence length within a range. Specifically, we can use a segment tree (or a binary indexed tree) to track the maximum length of a subsequence ending at any number. For each number num in nums, we query the maximum length among all numbers in the range [num - k, num - 1] and then update num’s position in the segment tree. This approach reduces the time complexity from exponential to O(n log M), where M is the maximum possible number in nums.

Algorithm Walkthrough

1. Initialize a segment tree or binary indexed tree of size equal to the maximum value in nums. Each node will store the maximum length of a valid subsequence ending at that number.
2. Iterate through each element num in nums.
3. For the current num, query the segment tree to find the maximum subsequence length among numbers in the range [num - k, num - 1]. This ensures that any subsequence extended by num respects both strictly increasing order and the maximum allowed difference k.
4. The length of the subsequence ending at num is max_length_in_range + 1.
5. Update the segment tree at index num with the new subsequence length.
6. Track the global maximum subsequence length as you iterate.
7. Return the global maximum after processing all elements.

Why it works: At each step, the segment tree ensures that we can efficiently retrieve the longest valid subsequence that num can extend. By updating the tree, we maintain the invariant that the tree always stores the best subsequence length ending at each number. This guarantees the correct global maximum.

Python Solution

from typing import List

class SegmentTree:
    def __init__(self, size: int):
        self.N = 1
        while self.N < size:
            self.N *= 2
        self.tree = [0] * (2 * self.N)
    
    def update(self, index: int, value: int):
        index += self.N
        self.tree[index] = max(self.tree[index], value)
        while index > 1:
            index //= 2
            self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])
    
    def query(self, left: int, right: int) -> int:
        left += self.N
        right += self.N
        result = 0
        while left <= right:
            if left % 2 == 1:
                result = max(result, self.tree[left])
                left += 1
            if right % 2 == 0:
                result = max(result, self.tree[right])
                right -= 1
            left //= 2
            right //= 2
        return result

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_num = max(nums)
        seg_tree = SegmentTree(max_num + 1)
        max_length = 0
        for num in nums:
            left = max(1, num - k)
            right = num - 1
            best_prev = seg_tree.query(left, right) if left <= right else 0
            curr_length = best_prev + 1
            seg_tree.update(num, curr_length)
            max_length = max(max_length, curr_length)
        return max_length

This Python solution uses a segment tree to track the maximum subsequence length for each number. For each num, it queries the maximum value in [num - k, num - 1] and updates the tree. The max_length is updated iteratively to maintain the global maximum.

Go Solution

package main

func lengthOfLIS(nums []int, k int) int {
    maxNum := 0
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }

    size := 1
    for size < maxNum+1 {
        size *= 2
    }
    tree := make([]int, 2*size)

    var query func(l, r int) int
    query = func(l, r int) int {
        res := 0
        l += size
        r += size
        for l <= r {
            if l%2 == 1 {
                if tree[l] > res {
                    res = tree[l]
                }
                l++
            }
            if r%2 == 0 {
                if tree[r] > res {
                    res = tree[r]
                }
                r--
            }
            l /= 2
            r /= 2
        }
        return res
    }

    update := func(index, value int) {
        index += size
        if value > tree[index] {
            tree[index] = value
        }
        for index > 1 {
            index /= 2
            if tree[2*index] > tree[2*index+1] {
                tree[index] = tree[2*index]
            } else {
                tree[index] = tree[2*index+1]
            }
        }
    }

    maxLength := 0
    for _, num := range nums {
        left := num - k
        if left < 1 {
            left = 1
        }
        right := num - 1
        bestPrev := 0
        if left <= right {
            bestPrev = query(left, right)
        }
        currLength := bestPrev + 1
        update(num, currLength)
        if currLength > maxLength {
            maxLength = currLength
        }
    }
    return maxLength
}

The Go implementation mirrors the Python version, using a segment tree. The primary differences are explicit slice initialization and integer operations, which avoid Python-specific constructs like dynamic typing.

Worked Examples

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

Final answer is 5 as expected based on constraints on differences.

Complexity Analysis