Jobs

Interviews

Discussions

Longest Increasing Subsequence

Medium

Google

19 views

Topics:

ArraysDynamic ProgrammingBinary Search

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-10⁴ <= nums[i] <= 10⁴

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Longest Increasing Subsequence

Medium

Google

19 views

Topics:

ArraysDynamic ProgrammingBinary Search

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-10⁴ <= nums[i] <= 10⁴

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

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 maximum size of the input array `nums`? Are there any memory constraints I should be aware of?
Can the input array `nums` contain negative numbers, zero, or non-integer values?
Are duplicate numbers allowed in the input array `nums`? If so, how should they be handled in determining the 'strictly increasing' subsequence?
If the input array `nums` is empty or null, what should the function return?
Are we looking for the length of *any* longest increasing subsequence, or is there a specific longest increasing subsequence we need to find (e.g., the lexicographically smallest)?

Brute Force Solution

Approach

The brute force way to find the longest increasing sequence is to look at every possible sequence you can make from the given numbers. We will check each of these sequences to see if it's increasing, and then remember the longest one we found that actually is.

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

Start by considering the first number by itself as a potential sequence.
Then, consider every possible pair of numbers, then every possible group of three numbers, and so on, until you have looked at all possible combinations of numbers from the original set.
For each combination of numbers you pick, check if the numbers are in increasing order (each number bigger than the one before it).
If the numbers are in increasing order, see how many numbers are in that sequence. This is the sequence's length.
Keep track of the longest increasing sequence you have found so far.
Once you have examined all possible combinations, the longest increasing sequence that you kept track of is your answer.

Code Implementation

def find_longest_increasing_subsequence_brute_force(numbers):
    longest_subsequence_length = 0

    # Iterate through all possible subsequences
    for i in range(1 << len(numbers)):
        subsequence = []
        for j in range(len(numbers)):
            # Check if the j-th bit is set in i
            if (i >> j) & 1:
                subsequence.append(numbers[j])

        # Check if subsequence is increasing
        is_increasing = True
        if len(subsequence) > 1:
            for k in range(1, len(subsequence)):
                #Ensure each element is greater than the previous
                if subsequence[k] <= subsequence[k - 1]:
                    is_increasing = False
                    break

        if is_increasing:
            #Update longest subsequence length found so far
            longest_subsequence_length = max(longest_subsequence_length, len(subsequence))

    return longest_subsequence_length

Big(O) Analysis

Time Complexity

O(2^n * n) – The brute force approach involves generating all possible subsequences of the input array. For an array of size n, there are 2^n possible subsequences. For each subsequence, we need to check if it is increasing, which takes O(n) time in the worst case, as we need to iterate through all the elements of the subsequence. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(1) – The described brute force approach involves iterating through combinations of numbers from the input. While the algorithm implicitly considers various sequences, it does not explicitly construct and store them in auxiliary data structures. It only keeps track of the length of the longest increasing sequence found so far, using a constant amount of extra space for storing variables like the current sequence length and the maximum length encountered. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The trick is to efficiently keep track of the smallest possible ending number for an increasing sequence of a given length. As we go through the numbers, we update our knowledge of these smallest ending numbers, always aiming to improve the sequences we've seen so far.

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

Imagine you have a collection of 'best possible endings' for increasing sequences of different lengths. Initially, this collection is empty.
Go through the numbers one by one, from left to right.
For each number, check if it can extend any of the existing increasing sequences we've found so far. More specifically, see if it's bigger than the 'best possible ending' of a sequence of some length.
If it can extend a sequence, find the longest existing sequence that it can extend. We can do this efficiently.
If extending a sequence creates a new, longer increasing sequence, add the current number as the 'best possible ending' of that new sequence length.
If the current number is smaller than the 'best possible ending' of some sequence length, it means we can improve that sequence. Replace the old 'best possible ending' with the current number, because it gives us a chance to build an even better sequence later on.
After processing all the numbers, the length of your collection of 'best possible endings' will be the length of the longest increasing sequence.

Code Implementation

def longest_increasing_subsequence(numbers):
    smallest_ending_numbers = []

    for current_number in numbers:

        # Find the smallest ending that current number can extend.
        left = 0
        right = len(smallest_ending_numbers) - 1
        index_to_update = -1

        while left <= right:
            middle = (left + right) // 2
            if smallest_ending_numbers[middle] < current_number:
                index_to_update = middle
                left = middle + 1
            else:
                right = middle - 1

        # If extends the longest sequence, add to smallest_ending_numbers.
        if index_to_update == len(smallest_ending_numbers) - 1:
            smallest_ending_numbers.append(current_number)

        else:

            # If current number improves existing sequence, replace ending.
            if index_to_update + 1 < len(smallest_ending_numbers) and current_number < smallest_ending_numbers[index_to_update + 1]:
                smallest_ending_numbers[index_to_update + 1] = current_number

    # The length of smallest_ending_numbers is the result.
    return len(smallest_ending_numbers)

Big(O) Analysis

Time Complexity

O(n log n) – We iterate through the input array of size n once. For each element, we perform a binary search on a sorted list of best possible endings. Binary search takes O(log k) time where k is the length of the sorted list. In the worst case, k can be n, making the binary search O(log n). Thus, the overall time complexity is O(n log n) because we perform a binary search for each of the n elements.

Space Complexity

O(N) – The algorithm maintains a collection of 'best possible endings' for increasing subsequences. This collection is implemented as an auxiliary array or list. In the worst-case scenario, where the input array is already sorted in increasing order, each element becomes a 'best possible ending' for a subsequence of increasing length, resulting in a collection whose size grows linearly with the input size N. Therefore, the auxiliary space required is proportional to N. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as the length of the longest increasing subsequence for a null or empty array is 0.
Array with a single element	Return 1 as a single element array has a longest increasing subsequence of length 1.
Array with all elements identical	Return 1 since the subsequence can only contain a single element when all elements are the same.
Array sorted in strictly decreasing order	Return 1, as each element by itself constitutes an increasing subsequence of length 1.
Array already sorted in strictly increasing order	Return the length of the array as the entire array is the longest increasing subsequence.
Array contains negative numbers	The algorithm should handle negative numbers correctly as the comparison is based on numerical order, which applies to negative numbers as well.
Array with a large number of elements to test for performance.	Ensure the algorithm chosen has an optimal time complexity (O(n log n) using patience sorting with binary search) to handle large inputs efficiently, rather than a naive O(n^2) dynamic programming approach.
Integer overflow if calculating lengths for extremely large arrays.	While the problem only asks for the length, not the subsequence itself, be mindful of potential integer overflows if dealing with extremely long arrays and consider using a larger data type like long if necessary for intermediate calculations.

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 maximum size of the input array `nums`? Are there any memory constraints I should be aware of?
Can the input array `nums` contain negative numbers, zero, or non-integer values?
Are duplicate numbers allowed in the input array `nums`? If so, how should they be handled in determining the 'strictly increasing' subsequence?
If the input array `nums` is empty or null, what should the function return?
Are we looking for the length of *any* longest increasing subsequence, or is there a specific longest increasing subsequence we need to find (e.g., the lexicographically smallest)?

Brute Force Solution

Approach

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

Start by considering the first number by itself as a potential sequence.
Then, consider every possible pair of numbers, then every possible group of three numbers, and so on, until you have looked at all possible combinations of numbers from the original set.
For each combination of numbers you pick, check if the numbers are in increasing order (each number bigger than the one before it).
If the numbers are in increasing order, see how many numbers are in that sequence. This is the sequence's length.
Keep track of the longest increasing sequence you have found so far.
Once you have examined all possible combinations, the longest increasing sequence that you kept track of is your answer.

Code Implementation

def find_longest_increasing_subsequence_brute_force(numbers):
    longest_subsequence_length = 0

    # Iterate through all possible subsequences
    for i in range(1 << len(numbers)):
        subsequence = []
        for j in range(len(numbers)):
            # Check if the j-th bit is set in i
            if (i >> j) & 1:
                subsequence.append(numbers[j])

        # Check if subsequence is increasing
        is_increasing = True
        if len(subsequence) > 1:
            for k in range(1, len(subsequence)):
                #Ensure each element is greater than the previous
                if subsequence[k] <= subsequence[k - 1]:
                    is_increasing = False
                    break

        if is_increasing:
            #Update longest subsequence length found so far
            longest_subsequence_length = max(longest_subsequence_length, len(subsequence))

    return longest_subsequence_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have a collection of 'best possible endings' for increasing sequences of different lengths. Initially, this collection is empty.
Go through the numbers one by one, from left to right.
For each number, check if it can extend any of the existing increasing sequences we've found so far. More specifically, see if it's bigger than the 'best possible ending' of a sequence of some length.
If it can extend a sequence, find the longest existing sequence that it can extend. We can do this efficiently.
If extending a sequence creates a new, longer increasing sequence, add the current number as the 'best possible ending' of that new sequence length.
If the current number is smaller than the 'best possible ending' of some sequence length, it means we can improve that sequence. Replace the old 'best possible ending' with the current number, because it gives us a chance to build an even better sequence later on.
After processing all the numbers, the length of your collection of 'best possible endings' will be the length of the longest increasing sequence.

Code Implementation

def longest_increasing_subsequence(numbers):
    smallest_ending_numbers = []

    for current_number in numbers:

        # Find the smallest ending that current number can extend.
        left = 0
        right = len(smallest_ending_numbers) - 1
        index_to_update = -1

        while left <= right:
            middle = (left + right) // 2
            if smallest_ending_numbers[middle] < current_number:
                index_to_update = middle
                left = middle + 1
            else:
                right = middle - 1

        # If extends the longest sequence, add to smallest_ending_numbers.
        if index_to_update == len(smallest_ending_numbers) - 1:
            smallest_ending_numbers.append(current_number)

        else:

            # If current number improves existing sequence, replace ending.
            if index_to_update + 1 < len(smallest_ending_numbers) and current_number < smallest_ending_numbers[index_to_update + 1]:
                smallest_ending_numbers[index_to_update + 1] = current_number

    # The length of smallest_ending_numbers is the result.
    return len(smallest_ending_numbers)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as the length of the longest increasing subsequence for a null or empty array is 0.
Array with a single element	Return 1 as a single element array has a longest increasing subsequence of length 1.
Array with all elements identical	Return 1 since the subsequence can only contain a single element when all elements are the same.
Array sorted in strictly decreasing order	Return 1, as each element by itself constitutes an increasing subsequence of length 1.
Array already sorted in strictly increasing order	Return the length of the array as the entire array is the longest increasing subsequence.
Array contains negative numbers	The algorithm should handle negative numbers correctly as the comparison is based on numerical order, which applies to negative numbers as well.
Array with a large number of elements to test for performance.	Ensure the algorithm chosen has an optimal time complexity (O(n log n) using patience sorting with binary search) to handle large inputs efficiently, rather than a naive O(n^2) dynamic programming approach.
Integer overflow if calculating lengths for extremely large arrays.	While the problem only asks for the length, not the subsequence itself, be mindful of potential integer overflows if dealing with extremely long arrays and consider using a larger data type like long if necessary for intermediate calculations.