#674

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Longest Continuous Increasing Subsequence

Find the length of the longest continuous increasing subsequence in an unsorted integer array using an array-driven solution strategy.

array

Problem Statement

Given an unsorted array of integers, you need to return the length of the longest continuous increasing subsequence (subarray). A continuous increasing subsequence must consist of strictly increasing consecutive elements. Your task is to identify and return the length of this subsequence efficiently.

In other words, you are looking for two indices l and r (where l < r) such that the subarray between l and r forms a strictly increasing sequence. The subsequence must be continuous, and each element at index i should be smaller than the element at index i+1. For example, in the array [1,3,5,4,7], the longest subsequence is [1,3,5], which has a length of 3.

Examples

Example 1

Input: nums = [1,3,5,4,7]

Output: 3

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

The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

Constraints

1 <= nums.length <= 104
-109 <= nums[i] <= 109

Solution Approach

Iterative Approach with Tracking

The problem can be solved in a single pass over the array. Start by initializing two variables: one to keep track of the longest increasing subsequence and another to track the current subsequence length. As you iterate through the array, check if each element is greater than the previous one. If so, increase the current subsequence length. Otherwise, compare and update the longest subsequence length, then reset the current subsequence length to 1.

No Extra Space

The solution can be achieved in constant space, O(1), because it doesn't require any additional data structures. You only need a few variables to store the current and maximum subsequence lengths, making the solution both space-efficient and time-efficient.

Edge Case Handling

It is crucial to handle edge cases such as arrays with all equal elements or a single element. These cases should correctly return 1 since the subsequence of a single number is trivially considered increasing.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N), where N is the length of the array. This is because we are iterating through the array only once. The space complexity is O(1) since we only need a few variables for tracking the subsequence lengths, regardless of the input size.

What Interviewers Usually Probe

Look for an understanding of array traversal and state tracking.
Check for proper handling of edge cases like repeated elements or single-element arrays.
Evaluate the candidate’s ability to implement a solution with O(N) time complexity and O(1) space complexity.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reset the current subsequence length after encountering a non-increasing element.
Misunderstanding that the subsequence must be strictly increasing, not just increasing or equal.
Not considering edge cases, such as arrays where all elements are the same or have only one element.

Follow-up variants

Find the longest decreasing subsequence instead of an increasing one.
Find the longest increasing subsequence with a given maximum allowed difference between consecutive elements.
Handle multiple subarrays and return the sum of the lengths of all increasing subsequences.

FAQ

What is the time complexity of the solution to Longest Continuous Increasing Subsequence?

The time complexity of the solution is O(N), where N is the length of the input array, because the array is traversed only once.

How do I handle arrays with all equal elements?

In this case, the longest continuous increasing subsequence will have a length of 1, since no element is greater than the previous one.

Is there a way to solve this problem without using extra space?

Yes, the solution can be achieved with O(1) space complexity, using just a few variables to track the current and maximum subsequence lengths.

What happens if the array has only one element?

If the array has only one element, the longest increasing subsequence is the array itself, and its length will be 1.

Can I apply dynamic programming to solve this problem?

Dynamic programming is not necessary for this problem, as the solution can be optimized to a single pass with constant space.

terminal

Solution

Solution 1: One-pass Scan

We can traverse the array $nums$, using a variable $cnt$ to record the length of the current consecutive increasing sequence. Initially, $cnt = 1$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = cnt = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] < x:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 1
        return ans

Solution 2: Two Pointers

We can also use two pointers $i$ and $j$ to find each consecutive increasing sequence, and find the length of the longest consecutive increasing sequence as the answer.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = cnt = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] < x:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 1
        return ans

Continue Practicing

#673 number of longest increasing subsequence #675 cut off trees for golf event #679 24 game