Practice/Google/Leetcode 2407. Longest Increasing Subsequence II

Leetcode 2407. Longest Increasing Subsequence II

CodingOptional

Problem

You are given an array of integers nums and an integer k. Your task is to find the length of the longest strictly increasing subsequence where the difference between any two consecutive elements in the subsequence is at most k.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. The subsequence must be strictly increasing, meaning each element must be greater than the previous one.

Requirements

1. Return the maximum length of a valid subsequence
2. The subsequence must maintain the original order of elements from nums
3. Each pair of consecutive elements in the subsequence must satisfy: next_element - prev_element <= k
4. The subsequence must be strictly increasing: next_element > prev_element

Constraints

• 1 ≤= nums.length ≤= 100,000
• 1 ≤= nums[i] ≤= 100,000
• 1 ≤= k ≤= 100,000
• Target time complexity: O(n log m) where n is the length of nums and m is the range of values
• Target space complexity: O(m)

Examples

Example 1:

Input: nums = [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3 Output: 5 Explanation: One optimal subsequence is [1, 3, 4, 5, 8]. The differences are: 3-1=2, 4-3=1, 5-4=1, 8-5=3, all <= 3.

Example 2:

Input: nums = [7, 4, 5, 1, 8, 12, 4, 7], k = 2 Output: 4 Explanation: One optimal subsequence is [4, 5, 7, 8]. The differences are: 5-4=1, 7-5=2, 8-7=1, all <= 2.

Example 3:

Input: nums = [5, 5, 5, 5], k = 0 Output: 1 Explanation: With k=0, strictly increasing means we cannot use duplicates. Maximum length is 1.