Longest Increasing Subsequence II

Hard

Google

2 views

Topics:

ArraysDynamic Programming

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.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

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].
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
Explanation:
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
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁵

Longest Increasing Subsequence II

Hard

Google

2 views

Topics:

ArraysDynamic Programming

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.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

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].
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
Explanation:
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
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the range of values within `nums`?
Can the input array `nums` contain duplicate numbers, and if so, how should they be handled in determining the longest increasing subsequence?
If there are multiple longest increasing subsequences with the same length, should I return any one of them, or is there a specific one I should prioritize based on a specific criterion, such as lexicographical order of indices?
Is the input array guaranteed to be non-empty? What should I return if the input array is null or empty?
Does the term 'increasing' imply strictly increasing (nums[i] < nums[j]) or non-decreasing (nums[i] <= nums[j]) for i < j in the subsequence?

Brute Force Solution

Approach

The brute force method for finding the longest increasing sequence involves exploring every possible subsequence. We systematically generate each subsequence, check if it's increasing, and keep track of the longest one we find. This guarantees we find the true answer, but takes a long time.

Here's how the algorithm would work step-by-step:

Start by considering each number in the input sequence as a potential starting point for our increasing subsequence.
For each starting number, look at every number that comes after it in the sequence.
If a number after the starting number is bigger than the starting number, add it to the subsequence.
Now, look at all the numbers after the second number in our subsequence. If any of them are bigger than the second number, add them to the subsequence.
Keep doing this until you reach the end of the sequence, forming one possible increasing subsequence.
Repeat this process, starting with all the other numbers in the input sequence as the initial number.
As you create all the different possible increasing subsequences, remember the length of each one.
Once you've checked every possible subsequence, find the one with the greatest length. That's the longest increasing subsequence.

Code Implementation

def longest_increasing_subsequence_brute_force(sequence):
    longest_subsequence_length = 0

    for starting_index in range(len(sequence)):
        # Consider each element as the start of a potential subsequence.

        current_subsequence = [sequence[starting_index]]
        current_length = 1
        longest_subsequence_length = max(longest_subsequence_length, current_length)

        longest_subsequence_length = find_longest_from(
            sequence, starting_index, current_subsequence, longest_subsequence_length
        )

    return longest_subsequence_length

def find_longest_from(sequence, current_index, current_subsequence, longest_subsequence_length):
    for next_index in range(current_index + 1, len(sequence)):
        # Look for numbers greater than the last number in the current subsequence.

        if sequence[next_index] > current_subsequence[-1]:
            current_subsequence.append(sequence[next_index])
            current_length = len(current_subsequence)
            longest_subsequence_length = max(longest_subsequence_length, current_length)
            
            # Recursively find the longest subsequence starting from the next index.
            longest_subsequence_length = find_longest_from(
                sequence, next_index, current_subsequence, longest_subsequence_length
            )
            current_subsequence.pop()

    #Backtrack to explore other possibilities.
    return longest_subsequence_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The provided brute force approach explores all possible subsequences. For each element in the input sequence of size n, we have two choices: either include it in a subsequence or exclude it. This leads to 2*2*...*2 (n times) possible subsequences, resulting in 2^n operations to generate and check them. Therefore, the time complexity is O(2^n).

Space Complexity

O(N) – The brute force method, as described, implicitly uses recursion to explore subsequences. In the worst-case scenario, the recursive calls can stack up to a depth of N, where N is the length of the input sequence, as each call explores adding another element to the potential subsequence. Each recursive call requires space on the call stack to store function arguments and local variables. Therefore, the auxiliary space complexity is O(N) due to the recursion depth.

Optimal Solution

Approach

The best way to find the longest increasing subsequence, when there's a maximum difference allowed between numbers, is to keep track of the end numbers of all possible increasing sequences we've seen so far. We maintain only the shortest possible sequence for each ending number to optimize for later extensions.

Here's how the algorithm would work step-by-step:

Imagine building increasing sequences step by step as you look at each number in the input.
For each number you see, check if it can extend any of the existing sequences while respecting the maximum difference rule.
If it can extend multiple sequences, extend the shortest one, because a shorter sequence offers more chances to be extended later.
If the number can't extend any existing sequence, it becomes the start of a brand-new sequence of length one.
Keep only the 'best' (shortest) sequence ending with each possible number; older sequences that end with the same number are useless to consider.
The longest length among all built sequences is the length of the longest increasing subsequence with the given maximum difference constraint.

Code Implementation

def longest_increasing_subsequence_ii(numbers, max_difference):
    tails = {}

    for number in numbers:
        # Find the longest sequence 'number' can extend.
        longest_length = 0
        best_tail_value = None
        for tail_value, length in tails.items():
            if number > tail_value and number - tail_value <= max_difference:
                if length > longest_length:
                    longest_length = length
                    best_tail_value = tail_value

        new_length = longest_length + 1

        # If 'number' can extend a sequence.
        if best_tail_value is not None:
            # Extend the shortest sequence ending with a smaller number
            tails[number] = new_length

        # Otherwise, 'number' starts a new sequence
        else:
            tails[number] = 1

        # Optimization: Remove longer sequences ending with the same number.
        keys_to_remove = []
        for tail_value, length in tails.items():
            if tail_value > number and length <= new_length:
                keys_to_remove.append(tail_value)

        for key in keys_to_remove:
            del tails[key]

    # The result is the length of the longest subsequence.
    if not tails:
        return 0
    return max(tails.values())

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – We iterate through each of the n elements in the input array. For each element, we use a binary search (or a similar logarithmic time operation on a sorted data structure) to find the appropriate sequence to extend or to determine if we need to start a new sequence. Since the iteration takes n steps, and each step potentially involves a log n operation, the overall time complexity is O(n log n).

Space Complexity

O(N) – The solution maintains a data structure to store the shortest possible sequence ending with each number encountered so far. In the worst-case scenario, where all N numbers in the input are distinct and form an increasing sequence within the allowed difference, the algorithm might store N different sequences. This implies the need to store N end numbers, resulting in an auxiliary space usage proportional to the input size. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 as the length of the longest increasing subsequence in an empty array is 0.
Input array with a single element	Return 1 as the longest increasing subsequence contains just that single element.
Input array with all identical elements	Return 1 because no two elements can be strictly increasing.
Input array is already sorted in strictly increasing order	The longest increasing subsequence is the array itself, so return the array's length.
Input array is sorted in strictly decreasing order	The longest increasing subsequence is of length 1, as any single element forms such a sequence; return 1.
Input array contains negative numbers, zeros and positive numbers	The algorithm should handle this correctly, as long as it compares elements correctly using the < operator.
Large input array with integer overflow when calculating lengths of subsequences	Ensure that the length of subsequences is stored in a data type that can hold sufficiently large values (e.g., long).
Large input array that results in exceeding time limit if the algorithm is inefficient	Optimize the algorithm, possibly using binary search or segment tree to achieve O(n log n) time complexity.