Jobs

Interviews

Discussions

Number of Longest Increasing Subsequence

Medium

Microsoft

2 views

Topics:

Dynamic ProgrammingArrays

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Constraints:

1 <= nums.length <= 2000
-10⁶ <= nums[i] <= 10⁶
The answer is guaranteed to fit inside a 32-bit integer.

Try coding it in LeetCode

Number of Longest Increasing Subsequence

Medium

Microsoft

2 views

Topics:

Dynamic ProgrammingArrays

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Constraints:

1 <= nums.length <= 2000
-10⁶ <= nums[i] <= 10⁶
The answer is guaranteed to fit inside a 32-bit integer.

Try coding it in LeetCode

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 is the range of values within the input array, and can the array contain negative numbers or zeros?
What should I return if the input array is null or empty?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when calculating the longest increasing subsequence and its count?
Is there a specific data type that I should use for the input array elements or the returned count?
Could you provide a few example inputs and their corresponding outputs to illustrate the expected behavior, particularly around edge cases or small inputs?

Brute Force Solution

Approach

To find the number of longest increasing sequences, the brute force way involves checking every possible sequence within the given set of numbers. We examine each subsequence to see if it is increasing and then compare its length to the longest one we've seen so far.

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

Consider every possible sequence you can make from the numbers, even sequences with only one number or sequences that skip numbers.
For each of those sequences, check if the sequence is 'increasing'. This means that each number in the sequence is bigger than the number before it.
If a sequence is increasing, find its length (the number of numbers in the sequence).
Keep track of the length of the longest increasing sequence you've found so far. Also, keep track of how many different sequences have that same longest length.
If you find a new increasing sequence that's longer than the longest one you've seen, update the longest length and reset the count to one (because you've only found one sequence that long so far).
If you find a new increasing sequence that's the same length as the longest one you've seen, increase the count (because you've found another sequence with the same longest length).
Once you've checked every possible sequence, the count you have is the number of longest increasing sequences.

Code Implementation

def number_of_longest_increasing_subsequence_brute_force(numbers):
    longest_increasing_subsequence_length = 0
    number_of_longest_increasing_subsequences = 0

    def is_increasing(subsequence):
        for i in range(1, len(subsequence)):
            if subsequence[i] <= subsequence[i - 1]:
                return False
        return True

    def find_all_subsequences(index, current_subsequence):
        nonlocal longest_increasing_subsequence_length
        nonlocal number_of_longest_increasing_subsequences

        if index == len(numbers):
            # Base case: We've reached the end of the input array.
            if len(current_subsequence) > 0:
                if is_increasing(current_subsequence):

                    current_length = len(current_subsequence)

                    # Update longest length, reset count if new longest
                    if current_length > longest_increasing_subsequence_length:
                        longest_increasing_subsequence_length = current_length
                        number_of_longest_increasing_subsequences = 1

                    # Increment count if same as current longest
                    elif current_length == longest_increasing_subsequence_length:
                        number_of_longest_increasing_subsequences += 1

            return

        # Recursive case 1: Exclude the current number.
        find_all_subsequences(index + 1, current_subsequence)

        # Recursive case 2: Include the current number.
        find_all_subsequences(index + 1, current_subsequence + [numbers[index]])

    # Initiates the recursive calls to generate all subsequences
    find_all_subsequences(0, [])

    # The result holds the total count
    return number_of_longest_increasing_subsequences

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through all possible subsequences of the input array nums of size n. Each element in nums can either be present or absent in a subsequence, resulting in 2 options for each element. Therefore, the total number of subsequences to consider is 2^n. Checking if each subsequence is increasing takes O(n) in the worst case. So the overall time complexity is O(n * 2^n) which simplifies to O(2^n) because 2^n grows much faster than n.

Space Complexity

O(1) – The described brute force approach does not explicitly mention any auxiliary data structures like arrays, lists, or hash maps. It primarily involves comparing lengths and maintaining counters for the longest length found and the count of such sequences. Since only a few scalar variables are used to track these values, and their number remains constant regardless of the input size N (the number of numbers), the space complexity is constant.

Optimal Solution

Approach

The optimal approach solves this problem by cleverly building increasing sequences one element at a time. We keep track of both the length of the longest increasing sequence ending at each position, and the number of such sequences. This avoids recalculating information and allows us to efficiently determine the final answer.

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

Imagine you are going through a list of numbers one by one.
For each number, check all the numbers that came before it in the list.
If you find a number that's smaller than the current number, it means you can potentially extend an increasing sequence ending at that smaller number.
Keep track of the longest increasing sequence that you can create ending at the current number. Also, keep track of how many different ways you can create that longest increasing sequence.
If extending a previous sequence creates a longer sequence than any you've seen before for the current number, update the longest sequence length and reset the count of ways to create it.
If extending a previous sequence creates a sequence of the same length as the longest you've seen before for the current number, add the number of ways to create the previous sequence to the count of ways to create the current sequence.
Once you've gone through all the numbers, find the overall longest increasing sequence length.
Add up the number of ways to create all the sequences that have that overall longest length. This total will be your final answer.

Code Implementation

def find_number_of_lis(nums):    array_length = len(nums)
    if array_length == 0:
        return 0

    lengths = [1] * array_length
    counts = [1] * array_length

    for i in range(array_length):
        for j in range(i):
            #Extend LIS if current element is greater.
            if nums[i] > nums[j]:
                if lengths[j] + 1 > lengths[i]:
                    lengths[i] = lengths[j] + 1
                    #Reset count for new longest
                    counts[i] = counts[j]
                elif lengths[j] + 1 == lengths[i]:
                    #Accumulate counts for equal length
                    counts[i] += counts[j]

    longest_sequence_length = max(lengths)
    number_of_longest_sequences = 0

    #Sum counts of all LIS with max length
    for i in range(array_length):
        if lengths[i] == longest_sequence_length:
            number_of_longest_sequences += counts[i]

    return number_of_longest_sequences

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element, it iterates through all preceding elements to find potential extensions of increasing subsequences. This results in a nested loop structure where, for each of the n elements, we perform up to n-1 comparisons and updates. The number of operations can be approximated by the sum 1 + 2 + ... + (n-1), which is proportional to n * (n-1) / 2. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The algorithm uses two arrays, lengths and counts, to store the length and number of longest increasing subsequences ending at each position. Both arrays have a size equal to the input list's length, N. Therefore, the auxiliary space used by the algorithm is directly proportional to the size of the input list. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0, since there's no increasing subsequence.
Array with a single element	Return 1, as the single element itself forms an increasing subsequence of length 1, with count 1.
Array with all identical values	Return 1, as each element is a LIS of length 1, but only one is counted.
Array in strictly decreasing order	Return the length of the array (n), as each element is a LIS of length 1, and there are n of them.
Array with maximum integer values	Ensure that integer overflow does not occur when calculating the count of LIS, potentially using larger data types for counts.
Large input array size	Ensure the solution has acceptable time complexity, such as O(n^2) using dynamic programming.
Array with duplicate numbers	Dynamic programming approach handles duplicates naturally by considering only increasing subsequences.
Input array with negative numbers	The dynamic programming approach correctly handles negative numbers without any modification.

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 is the range of values within the input array, and can the array contain negative numbers or zeros?
What should I return if the input array is null or empty?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when calculating the longest increasing subsequence and its count?
Is there a specific data type that I should use for the input array elements or the returned count?
Could you provide a few example inputs and their corresponding outputs to illustrate the expected behavior, particularly around edge cases or small inputs?

Brute Force Solution

Approach

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

Consider every possible sequence you can make from the numbers, even sequences with only one number or sequences that skip numbers.
For each of those sequences, check if the sequence is 'increasing'. This means that each number in the sequence is bigger than the number before it.
If a sequence is increasing, find its length (the number of numbers in the sequence).
Keep track of the length of the longest increasing sequence you've found so far. Also, keep track of how many different sequences have that same longest length.
If you find a new increasing sequence that's longer than the longest one you've seen, update the longest length and reset the count to one (because you've only found one sequence that long so far).
If you find a new increasing sequence that's the same length as the longest one you've seen, increase the count (because you've found another sequence with the same longest length).
Once you've checked every possible sequence, the count you have is the number of longest increasing sequences.

Code Implementation

def number_of_longest_increasing_subsequence_brute_force(numbers):
    longest_increasing_subsequence_length = 0
    number_of_longest_increasing_subsequences = 0

    def is_increasing(subsequence):
        for i in range(1, len(subsequence)):
            if subsequence[i] <= subsequence[i - 1]:
                return False
        return True

    def find_all_subsequences(index, current_subsequence):
        nonlocal longest_increasing_subsequence_length
        nonlocal number_of_longest_increasing_subsequences

        if index == len(numbers):
            # Base case: We've reached the end of the input array.
            if len(current_subsequence) > 0:
                if is_increasing(current_subsequence):

                    current_length = len(current_subsequence)

                    # Update longest length, reset count if new longest
                    if current_length > longest_increasing_subsequence_length:
                        longest_increasing_subsequence_length = current_length
                        number_of_longest_increasing_subsequences = 1

                    # Increment count if same as current longest
                    elif current_length == longest_increasing_subsequence_length:
                        number_of_longest_increasing_subsequences += 1

            return

        # Recursive case 1: Exclude the current number.
        find_all_subsequences(index + 1, current_subsequence)

        # Recursive case 2: Include the current number.
        find_all_subsequences(index + 1, current_subsequence + [numbers[index]])

    # Initiates the recursive calls to generate all subsequences
    find_all_subsequences(0, [])

    # The result holds the total count
    return number_of_longest_increasing_subsequences

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you are going through a list of numbers one by one.
For each number, check all the numbers that came before it in the list.
If you find a number that's smaller than the current number, it means you can potentially extend an increasing sequence ending at that smaller number.
Keep track of the longest increasing sequence that you can create ending at the current number. Also, keep track of how many different ways you can create that longest increasing sequence.
If extending a previous sequence creates a longer sequence than any you've seen before for the current number, update the longest sequence length and reset the count of ways to create it.
If extending a previous sequence creates a sequence of the same length as the longest you've seen before for the current number, add the number of ways to create the previous sequence to the count of ways to create the current sequence.
Once you've gone through all the numbers, find the overall longest increasing sequence length.
Add up the number of ways to create all the sequences that have that overall longest length. This total will be your final answer.

Code Implementation

def find_number_of_lis(nums):    array_length = len(nums)
    if array_length == 0:
        return 0

    lengths = [1] * array_length
    counts = [1] * array_length

    for i in range(array_length):
        for j in range(i):
            #Extend LIS if current element is greater.
            if nums[i] > nums[j]:
                if lengths[j] + 1 > lengths[i]:
                    lengths[i] = lengths[j] + 1
                    #Reset count for new longest
                    counts[i] = counts[j]
                elif lengths[j] + 1 == lengths[i]:
                    #Accumulate counts for equal length
                    counts[i] += counts[j]

    longest_sequence_length = max(lengths)
    number_of_longest_sequences = 0

    #Sum counts of all LIS with max length
    for i in range(array_length):
        if lengths[i] == longest_sequence_length:
            number_of_longest_sequences += counts[i]

    return number_of_longest_sequences

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0, since there's no increasing subsequence.
Array with a single element	Return 1, as the single element itself forms an increasing subsequence of length 1, with count 1.
Array with all identical values	Return 1, as each element is a LIS of length 1, but only one is counted.
Array in strictly decreasing order	Return the length of the array (n), as each element is a LIS of length 1, and there are n of them.
Array with maximum integer values	Ensure that integer overflow does not occur when calculating the count of LIS, potentially using larger data types for counts.
Large input array size	Ensure the solution has acceptable time complexity, such as O(n^2) using dynamic programming.
Array with duplicate numbers	Dynamic programming approach handles duplicates naturally by considering only increasing subsequences.
Input array with negative numbers	The dynamic programming approach correctly handles negative numbers without any modification.