easyStackPattern: Monotonic Stack

Longest Decreasing Subsequence Length Solution

Problem Statement

Given an array of integers `values`, find the length of the longest subsequence such that each element is strictly less than the element preceding it in the subsequence.

Examples

Example 1:

Input:[5, 3, 4, 2, 1]

Output:2

Explanation: The longest decreasing subsequence is [5, 3, 2, 1] or [5, 4, 2, 1], both of length 4.

Example 2:

Input:[10, 9, 2, 5, 3, 7, 101, 18]

Output:4

Explanation: The longest decreasing subsequence is [10, 9, 5, 3] or [10, 9, 2] or [10, 5, 3]. The maximum length is 4.

Example 3:

Input:[1, 1, 1, 1]

Output:1

Explanation: Since elements must be strictly decreasing, the longest subsequence has length 1 (any single element).

Constraints

1 <= values.length <= 2500
-10^9 <= values[i] <= 10^9
All elements in `values` are integers.

Time: O(n log n) Space: O(n)

This problem can be solved using dynamic programming in O(n^2) time. A more optimized O(n log n) solution involves maintaining an auxiliary array that stores the smallest tail of all decreasing subsequences of a given length. Binary search is used to efficiently update this array.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

def longest_decreasing_subsequence_length(values):
    if not values:
        return 0

    tails = []  # stores the smallest tail of all decreasing subsequences of length i+1

    for value in values:
        # Find the first element in tails that is strictly smaller than value
        # Using binary search for efficiency
        low = 0
        high = len(tails)
        
        while low < high:
            mid = (low + high) // 2
            if tails[mid] >= value: # We want to find the smallest tail < value, so if tails[mid] >= value, we search right
                low = mid + 1
            else: # tails[mid] < value, this is a potential candidate
                high = mid
        
        # After the loop, 'low' is the index of the first element in tails that is < value
        if low == len(tails):
            tails.append(value) # If no element is < value, extend the longest subsequence
        else:
            tails[low] = value # Otherwise, replace the smallest tail that is < value

    return len(tails)