LeetCode Solutions Blog

Longest Increasing Subsequence II

Number: 2526

Difficulty: Hard

Paid? No

Companies: Google, Apple

Problem Description

Given an integer array nums and an integer k, find the longest subsequence of nums that is strictly increasing and where the difference between any two adjacent elements is at most k. Return the length of such longest subsequence.

Key Insights

The subsequence must be strictly increasing.
The difference between two consecutive elements must be ≤ k.
A dynamic programming approach can be used where we compute dp[x] as the length of the longest valid subsequence ending with a number x.
To efficiently query the maximum dp value in a range (specifically, from [num - k, num - 1]), we can use a segment tree or BIT (Fenwick Tree).
The problem constraints (n up to 10^5 and values up to 10^5) require an O(n log M) solution.

Space and Time Complexity

Time Complexity: O(n log M), where M is the maximum possible value (up to 10^5)
Space Complexity: O(M) (for the segment tree/BIT)

Solution

We iterate through the array nums. For each number, we want to find the maximum dp value for all valid previous numbers in the range [num - k, num - 1]. We then use that value plus one as the dp for the current number and update our data structure accordingly.

A segment tree is used because it allows us to efficiently query the maximum value in an arbitrary interval and update a single index. In our segment tree, each leaf represents a possible number value (from 1 to the maximum value in nums). For each num in the array, we:

Compute leftBound = max(1, num - k) and rightBound = num - 1. If rightBound < leftBound we treat the best previous value as 0.
Query the segment tree in the interval [leftBound, rightBound] to get the maximum dp value.
Set current dp as (queried value + 1).
Update the segment tree at index num with the maximum of its current value and the new dp.
Keep track of the global maximum dp value across iterations.

This method guarantees that we are considering all valid previous subsequences that can extend to the current number while satisfying the constraints.

Code Solutions

# Python solution with segment tree

class SegmentTree:
    # Build segment tree with size n (1-indexed positions)
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
    
    # Internal function to update the tree
    def update_rec(self, idx, left, right, pos, value):
        if left == right:
            self.tree[idx] = max(self.tree[idx], value)
            return
        mid = (left + right) // 2
        if pos <= mid:
            self.update_rec(idx * 2, left, mid, pos, value)
        else:
            self.update_rec(idx * 2 + 1, mid + 1, right, pos, value)
        self.tree[idx] = max(self.tree[idx * 2], self.tree[idx * 2 + 1])
    
    # Update position pos to value (taking maximum)
    def update(self, pos, value):
        self.update_rec(1, 1, self.n, pos, value)
    
    # Internal function query maximum in interval [ql, qr]
    def query_rec(self, idx, left, right, ql, qr):
        if ql > right or qr < left:
            return 0
        if ql <= left and right <= qr:
            return self.tree[idx]
        mid = (left + right) // 2
        return max(self.query_rec(idx * 2, left, mid, ql, qr),
                   self.query_rec(idx * 2 + 1, mid + 1, right, ql, qr))
    
    # Query maximum value in interval [ql, qr]
    def query(self, ql, qr):
        if ql > qr:
            return 0
        return self.query_rec(1, 1, self.n, ql, qr)

def longestIncreasingSubsequenceII(nums, k):
    # Maximum value possible as given in constraints
    MAX_VAL = 10**5
    seg_tree = SegmentTree(MAX_VAL)
    
    longest = 0
    for num in nums:
        left_bound = max(1, num - k)
        right_bound = num - 1
        best_prev = seg_tree.query(left_bound, right_bound) if right_bound >= left_bound else 0
        current_dp = best_prev + 1
        # Update the segment tree for number 'num'
        seg_tree.update(num, current_dp)
        longest = max(longest, current_dp)
    return longest

# Example usage:
nums1 = [4,2,1,4,3,4,5,8,15]
k1 = 3
print(longestIncreasingSubsequenceII(nums1, k1))  # Expected output: 5