Jobs

Interviews

Discussions

Longest Continuous Increasing Subsequence

Easy

Asked by:

More companies

12 views

Topics:

Arrays

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example 1:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

Example 2:

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.

Constraints:

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

Try coding it in LeetCode

Longest Continuous Increasing Subsequence

Easy

Asked by:

12 views

Topics:

Arrays

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

Example 2:

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.

Constraints:

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

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 expected behavior if the input array is empty or null?
Can the input array contain negative numbers, zeros, or floating-point numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled (e.g., do they break the increasing subsequence)?
Should I return the length of the longest increasing subsequence, or the subsequence itself (as a new array)?
What is the range of possible values for the integers in the array?

Brute Force Solution

Approach

The brute force approach to finding the longest increasing sequence involves checking every possible subsequence within the given sequence. We explore all combinations, comparing each to find the longest one that strictly increases as you go from left to right. Essentially, we leave no stone unturned.

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

Start by considering each number in the sequence as the potential beginning of an increasing subsequence.
For each starting number, look at all the numbers that come after it.
For each of these following numbers, check if it's bigger than the current last number in your potential increasing subsequence.
If it is bigger, add it to the end of your subsequence and keep going, looking for even bigger numbers later in the sequence.
If it's not bigger, ignore it and try the next number following the current last number.
Once you've reached the end of the sequence, or can't find a bigger number to add, remember how long your increasing subsequence was.
Repeat this whole process, starting from each number in the original sequence as the beginning of a new potential increasing subsequence.
After trying all possible starting numbers and building all possible increasing subsequences, compare the lengths of all the subsequences you found.
The longest one you discovered is your answer.

Code Implementation

def find_longest_increasing_subsequence(number_list):
    longest_subsequence_length = 0

    for starting_index in range(len(number_list)):
        current_subsequence_length = 0
        current_subsequence = []

        # Start a subsequence with the current number
        current_subsequence.append(number_list[starting_index])
        current_subsequence_length += 1

        for next_index in range(starting_index + 1, len(number_list)):
            # Check if the next number extends subsequence
            if number_list[next_index] > current_subsequence[-1]:
                current_subsequence.append(number_list[next_index])
                current_subsequence_length += 1

        # Compare and update longest subsequence
        if current_subsequence_length > longest_subsequence_length:
            longest_subsequence_length = current_subsequence_length

    return longest_subsequence_length

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each of the n elements of the input array, considering each as a potential start to an increasing subsequence. For each starting element, it checks all subsequent elements to extend that subsequence, potentially examining up to n-1 elements in the worst case. This nested exploration of subsequences leads to a number of comparisons proportional to n * (n-1), which is roughly equivalent to n * n/2. Thus, the time complexity is O(n²).

Space Complexity

O(N) – The brute force approach, as described, explores all possible subsequences. In the process of building each potential increasing subsequence, we are essentially creating temporary subsequences which, in the worst case, can be as long as the original input sequence of length N. Although the plain English explanation does not explicitly state that we store each subsequence, the process of comparing to find the *longest* implies we must keep track of each subsequence's elements (implicitly stored in a list or similar). Therefore, the space required to store these temporary subsequences can grow linearly with the size of the input, resulting in a space complexity of O(N).

Optimal Solution

Approach

The most efficient way to find the longest continuous increasing sequence is to scan the numbers once, keeping track of how long the current streak is. We only need to update our answer when we find a longer streak, skipping all possible sub-sequences.

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

Start at the beginning of the list of numbers.
Assume the current streak is one number long (just the first number).
Move to the next number in the list.
If the next number is bigger than the last number, increase the length of the current streak by one.
If the next number is not bigger than the last number, the streak is broken, so reset the current streak length back to one.
Keep track of the longest streak you've seen so far. If the current streak is longer than the longest streak you've seen so far, update the longest streak.
Repeat steps 3-6 until you've checked all the numbers in the list.
The longest streak you've kept track of is the length of the longest continuous increasing sequence.

Code Implementation

def find_longest_increasing_subsequence(numbers):
    if not numbers:
        return 0

    longest_streak_length = 1
    current_streak_length = 1

    for i in range(1, len(numbers)):
        # Check if current number continues sequence.
        if numbers[i] > numbers[i - 1]:
            current_streak_length += 1

            # Update longest streak if needed.
            if current_streak_length > longest_streak_length:
                longest_streak_length = current_streak_length

        # Reset streak if sequence is broken.
        else:
            current_streak_length = 1

    return longest_streak_length

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array of n numbers only once. In each iteration, it performs a constant amount of work: comparing two adjacent numbers and potentially updating the current streak length and the maximum streak length. Since the number of operations grows linearly with the input size n, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the current streak length and the longest streak seen so far. These variables occupy constant space, regardless of the size of the input list, denoted as N. No additional data structures, such as arrays or hash maps, are created that depend on the input size. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there is no subsequence.
Array with a single element	Return 1 immediately as a single element is a subsequence of length 1.
Array with all elements in descending order	The algorithm should still return 1 because a single element is an increasing subsequence.
Array with all elements being identical	The algorithm should return 1, as the longest increasing subsequence consists of any single element.
Array with a very long continuous increasing subsequence	The algorithm should handle this efficiently (O(n) time complexity) without stack overflow.
Array with negative numbers and/or zero	The algorithm should correctly handle negative and zero values as they can be part of an increasing sequence.
Array contains Integer.MAX_VALUE and/or Integer.MIN_VALUE	The algorithm should handle these boundary values without causing integer overflow issues during comparison.
Very large input array size nearing memory limits	Ensure the algorithm doesn't allocate excessive memory that could lead to out-of-memory errors.

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 expected behavior if the input array is empty or null?
Can the input array contain negative numbers, zeros, or floating-point numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled (e.g., do they break the increasing subsequence)?
Should I return the length of the longest increasing subsequence, or the subsequence itself (as a new array)?
What is the range of possible values for the integers in the array?

Brute Force Solution

Approach

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

Start by considering each number in the sequence as the potential beginning of an increasing subsequence.
For each starting number, look at all the numbers that come after it.
For each of these following numbers, check if it's bigger than the current last number in your potential increasing subsequence.
If it is bigger, add it to the end of your subsequence and keep going, looking for even bigger numbers later in the sequence.
If it's not bigger, ignore it and try the next number following the current last number.
Once you've reached the end of the sequence, or can't find a bigger number to add, remember how long your increasing subsequence was.
Repeat this whole process, starting from each number in the original sequence as the beginning of a new potential increasing subsequence.
After trying all possible starting numbers and building all possible increasing subsequences, compare the lengths of all the subsequences you found.
The longest one you discovered is your answer.

Code Implementation

def find_longest_increasing_subsequence(number_list):
    longest_subsequence_length = 0

    for starting_index in range(len(number_list)):
        current_subsequence_length = 0
        current_subsequence = []

        # Start a subsequence with the current number
        current_subsequence.append(number_list[starting_index])
        current_subsequence_length += 1

        for next_index in range(starting_index + 1, len(number_list)):
            # Check if the next number extends subsequence
            if number_list[next_index] > current_subsequence[-1]:
                current_subsequence.append(number_list[next_index])
                current_subsequence_length += 1

        # Compare and update longest subsequence
        if current_subsequence_length > longest_subsequence_length:
            longest_subsequence_length = current_subsequence_length

    return longest_subsequence_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the beginning of the list of numbers.
Assume the current streak is one number long (just the first number).
Move to the next number in the list.
If the next number is bigger than the last number, increase the length of the current streak by one.
If the next number is not bigger than the last number, the streak is broken, so reset the current streak length back to one.
Keep track of the longest streak you've seen so far. If the current streak is longer than the longest streak you've seen so far, update the longest streak.
Repeat steps 3-6 until you've checked all the numbers in the list.
The longest streak you've kept track of is the length of the longest continuous increasing sequence.

Code Implementation

def find_longest_increasing_subsequence(numbers):
    if not numbers:
        return 0

    longest_streak_length = 1
    current_streak_length = 1

    for i in range(1, len(numbers)):
        # Check if current number continues sequence.
        if numbers[i] > numbers[i - 1]:
            current_streak_length += 1

            # Update longest streak if needed.
            if current_streak_length > longest_streak_length:
                longest_streak_length = current_streak_length

        # Reset streak if sequence is broken.
        else:
            current_streak_length = 1

    return longest_streak_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there is no subsequence.
Array with a single element	Return 1 immediately as a single element is a subsequence of length 1.
Array with all elements in descending order	The algorithm should still return 1 because a single element is an increasing subsequence.
Array with all elements being identical	The algorithm should return 1, as the longest increasing subsequence consists of any single element.
Array with a very long continuous increasing subsequence	The algorithm should handle this efficiently (O(n) time complexity) without stack overflow.
Array with negative numbers and/or zero	The algorithm should correctly handle negative and zero values as they can be part of an increasing sequence.
Array contains Integer.MAX_VALUE and/or Integer.MIN_VALUE	The algorithm should handle these boundary values without causing integer overflow issues during comparison.
Very large input array size nearing memory limits	Ensure the algorithm doesn't allocate excessive memory that could lead to out-of-memory errors.