Jobs

Interviews

Discussions

Longest Increasing Subsequence

Medium

Samsung

1 view

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

Samsung

1 view

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 range of values for the integers in the input array?
Can the input array be empty or null?
If there are multiple increasing subsequences of the same maximum length, do I need to return a specific one, or is any of them acceptable?
Does the given array `nums` contain duplicate values, and if so, how should those be handled when determining increasing subsequences?
What is the maximum possible length of the input array `nums`? This will help me consider space complexity implications.

Brute Force Solution

Approach

Imagine you're searching for the longest chain of numbers in a given list, where each number in the chain must be bigger than the one before it. A brute force approach involves checking every single possible chain you could make from the numbers in the list. It's like trying out every path to see which one is the longest climb.

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

Start by considering each number in the list as a potential starting point for a chain of increasing numbers.
From that starting number, examine all the numbers that come after it in the list.
If you find a number that's bigger than your current number, you can extend the chain to include that number.
Keep extending the chain as long as you can find numbers that are bigger than the last number you added.
Once you can't extend the chain any further, record the length of that chain.
Repeat this process, starting from every single number in the list.
Finally, compare the lengths of all the chains you found and pick the longest one. That's the longest increasing sequence.

Code Implementation

def longest_increasing_subsequence_brute_force(numbers):
    max_length = 0

    for start_index in range(len(numbers)):
        current_length = 0
        current_sequence = []

        # Start a sequence with the current number
        current_sequence.append(numbers[start_index])
        current_length = 1

        for next_index in range(start_index + 1, len(numbers)):
            # Extend sequence only if it increases
            if numbers[next_index] > current_sequence[-1]:
                current_sequence.append(numbers[next_index])
                current_length += 1

        # Keep track of the longest one
        if current_length > max_length:
            max_length = current_length

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array as a potential starting point for an increasing subsequence. For each starting element, it then iterates through the remaining elements of the array to find elements that can extend the subsequence. In the worst case, for each element, we may need to examine almost all the other elements, leading to nested loops that perform approximately n * (n-1) comparisons. Thus, the time complexity approximates n * n/2, which simplifies to O(n²).

Space Complexity

O(N) – The described brute force approach calculates the length of an increasing subsequence starting from each element. While it doesn't explicitly mention a data structure, to avoid recalculating the length of a subsequence repeatedly, an optimization using memoization could be applied, storing the length of the longest increasing subsequence starting at each index. This would require an auxiliary array of size N, where N is the length of the input list. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The goal is to find the longest possible ordered chain within a sequence. The key is to build the best possible chain as we go, replacing elements if a better option appears for a chain of a given length.

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

Imagine you're building many potential chains at once, each with a different last number.
As you go through the sequence, check if the current number can extend any of your existing chains.
If it can, extend the shortest chain possible. This helps in keeping the chains as flexible as possible.
If the number is smaller than the smallest last number in any chain, then you found a new chain of length 1.
If the number is bigger than all chains, you found a way to extend the longest chain.
If you find a chain that you can extend to a better chain, replace the last value of the longer sequence with this new value, this helps optimize the length of the chain.
By the end, the length of the longest chain you've built is the length of the longest increasing subsequence.

Code Implementation

def find_longest_increasing_subsequence(sequence):
    tails = []

    for number in sequence:
        if not tails or number > tails[-1]:
            tails.append(number)

        else:
            # Find the smallest tail that is >= number.
            left, right = 0, len(tails) - 1

            while left <= right:
                middle = (left + right) // 2

                if tails[middle] < number:
                    left = middle + 1
                else:
                    right = middle - 1

            # Replace that found tail.
            tails[left] = number

    # Length of tails is our LIS length.
    return len(tails)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – We iterate through the input sequence of size n. For each element, we perform a binary search on a sorted list of the smallest tail elements of increasing subsequences. The binary search takes O(log n) time. Since we perform this binary search for each of the n elements, the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm maintains a list of the last elements of increasing subsequences. In the worst case, the input sequence is already increasing, and this list will store all N elements of the input sequence. Therefore, the auxiliary space used scales linearly with the size of the input sequence. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 as the length of the longest increasing subsequence is 0 when the input is empty.
Input array with a single element	Return 1, as a single element is a subsequence of length 1.
Input array with all elements in descending order	The longest increasing subsequence will be of length 1 for each element.
Input array with all elements being identical	The longest increasing subsequence will be of length 1.
Input array containing duplicate elements	The algorithm should correctly skip duplicate elements when building the increasing subsequence.
Input array containing negative numbers and/or zeros	The algorithm should correctly handle negative numbers and zeros as they can be part of an increasing subsequence.
Input array with extremely large numbers (close to integer limits)	Ensure that the algorithm does not cause integer overflow when comparing elements.
Large input array, nearing memory limits	A solution with O(n log n) time complexity and O(n) space complexity is preferable to avoid exceeding time or memory limits.

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 for the integers in the input array?
Can the input array be empty or null?
If there are multiple increasing subsequences of the same maximum length, do I need to return a specific one, or is any of them acceptable?
Does the given array `nums` contain duplicate values, and if so, how should those be handled when determining increasing subsequences?
What is the maximum possible length of the input array `nums`? This will help me consider space complexity implications.

Brute Force Solution

Approach

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

Start by considering each number in the list as a potential starting point for a chain of increasing numbers.
From that starting number, examine all the numbers that come after it in the list.
If you find a number that's bigger than your current number, you can extend the chain to include that number.
Keep extending the chain as long as you can find numbers that are bigger than the last number you added.
Once you can't extend the chain any further, record the length of that chain.
Repeat this process, starting from every single number in the list.
Finally, compare the lengths of all the chains you found and pick the longest one. That's the longest increasing sequence.

Code Implementation

def longest_increasing_subsequence_brute_force(numbers):
    max_length = 0

    for start_index in range(len(numbers)):
        current_length = 0
        current_sequence = []

        # Start a sequence with the current number
        current_sequence.append(numbers[start_index])
        current_length = 1

        for next_index in range(start_index + 1, len(numbers)):
            # Extend sequence only if it increases
            if numbers[next_index] > current_sequence[-1]:
                current_sequence.append(numbers[next_index])
                current_length += 1

        # Keep track of the longest one
        if current_length > max_length:
            max_length = current_length

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're building many potential chains at once, each with a different last number.
As you go through the sequence, check if the current number can extend any of your existing chains.
If it can, extend the shortest chain possible. This helps in keeping the chains as flexible as possible.
If the number is smaller than the smallest last number in any chain, then you found a new chain of length 1.
If the number is bigger than all chains, you found a way to extend the longest chain.
If you find a chain that you can extend to a better chain, replace the last value of the longer sequence with this new value, this helps optimize the length of the chain.
By the end, the length of the longest chain you've built is the length of the longest increasing subsequence.

Code Implementation

def find_longest_increasing_subsequence(sequence):
    tails = []

    for number in sequence:
        if not tails or number > tails[-1]:
            tails.append(number)

        else:
            # Find the smallest tail that is >= number.
            left, right = 0, len(tails) - 1

            while left <= right:
                middle = (left + right) // 2

                if tails[middle] < number:
                    left = middle + 1
                else:
                    right = middle - 1

            # Replace that found tail.
            tails[left] = number

    # Length of tails is our LIS length.
    return len(tails)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 as the length of the longest increasing subsequence is 0 when the input is empty.
Input array with a single element	Return 1, as a single element is a subsequence of length 1.
Input array with all elements in descending order	The longest increasing subsequence will be of length 1 for each element.
Input array with all elements being identical	The longest increasing subsequence will be of length 1.
Input array containing duplicate elements	The algorithm should correctly skip duplicate elements when building the increasing subsequence.
Input array containing negative numbers and/or zeros	The algorithm should correctly handle negative numbers and zeros as they can be part of an increasing subsequence.
Input array with extremely large numbers (close to integer limits)	Ensure that the algorithm does not cause integer overflow when comparing elements.
Large input array, nearing memory limits	A solution with O(n log n) time complexity and O(n) space complexity is preferable to avoid exceeding time or memory limits.