LeetCode 674 - Longest Continuous Increasing Subsequence

LeetCode Problem 674

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to find the length of the longest strictly increasing contiguous segment in an array. The key detail is that the subsequence must be continuous, which means the elements must appear next to each other in the original array.

Given an integer array nums, we need to determine the maximum length of any subarray where every element is strictly greater than the element before it. In other words, for every adjacent pair inside the chosen subarray, the condition nums[i] < nums[i + 1] must hold.

For example, in the array [1,3,5,4,7], the sequence [1,3,5] is continuous and strictly increasing, so its length is 3. Although [1,3,5,7] is increasing, it is not continuous because the element 4 appears between 5 and 7.

The input size is relatively small, with nums.length up to 10^4, but this is still large enough that inefficient quadratic solutions become undesirable. The values inside the array can range from -10^9 to 10^9, but the actual magnitude of the numbers does not matter because we only compare adjacent values.

The problem guarantees that the array contains at least one element. This is important because it means the answer is always at least 1.

Several edge cases are important to consider:

• An array with only one element should return 1.
• An array where all elements are equal should also return 1, because the sequence must be strictly increasing.
• A completely increasing array should return the full array length.
• A completely decreasing array should return 1.
• Repeated values break the increasing streak because equality does not satisfy strict increase.

Approaches

Brute Force Approach

A straightforward approach is to examine every possible continuous subarray and check whether it is strictly increasing.

We can choose every starting index i, then extend the subarray to every ending index j. For each subarray, we verify whether every adjacent pair satisfies the increasing condition.

This approach is correct because it explicitly checks all possible continuous subsequences and keeps track of the maximum valid length found.

However, this method is inefficient. There are O(n^2) possible subarrays, and checking whether each one is increasing can take another O(n) time in the worst case. This leads to a total complexity of O(n^3). Even with small optimizations, the approach remains unnecessarily slow compared to what is possible.

Optimal Approach

The key observation is that we do not need to repeatedly recheck earlier elements. Since the subsequence must be continuous, we only care about whether the current element continues the increasing streak from the previous element.

We can scan the array once from left to right while maintaining:

• The current increasing streak length
• The maximum streak length seen so far

If nums[i] > nums[i - 1], the increasing sequence continues, so we extend the current streak.

Otherwise, the streak is broken, and we reset the current streak length back to 1 because the current element itself starts a new potential sequence.

This works because every continuous increasing subsequence is fully determined by adjacent comparisons.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every subarray and validates increasing order
Optimal	O(n)	O(1)	Single pass while tracking current streak

Algorithm Walkthrough

1. Initialize two variables:

• current_length = 1
• max_length = 1

Since the array is guaranteed to contain at least one element, the smallest possible increasing subsequence has length 1. 2. Iterate through the array starting from index 1.

We start at index 1 because each comparison requires looking at the previous element. 3. For each position i, compare nums[i] with nums[i - 1].

This determines whether the increasing streak continues. 4. If nums[i] > nums[i - 1], increment current_length.

This means the current element extends the existing increasing subsequence. 5. Otherwise, reset current_length to 1.

The increasing sequence has been broken, so the current element becomes the start of a new possible subsequence. 6. After updating current_length, update max_length.

If the current streak is larger than the best streak seen so far, store the new maximum. 7. After the loop finishes, return max_length.

This represents the length of the longest continuous increasing subsequence in the array.

Why it works

The algorithm maintains the invariant that current_length always represents the length of the current strictly increasing contiguous segment ending at index i.

Whenever two adjacent elements satisfy the increasing condition, the streak extends naturally. When the condition fails, no continuous increasing subsequence can cross that boundary, so resetting to 1 is correct.

By tracking the maximum value reached by current_length, we guarantee that the final answer is the longest valid subsequence in the array.

Python Solution

from typing import List

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        current_length = 1
        max_length = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                current_length += 1
            else:
                current_length = 1

            max_length = max(max_length, current_length)

        return max_length

The implementation begins by initializing both current_length and max_length to 1. This reflects the fact that any individual element forms a valid increasing subsequence of length 1.

The loop starts at index 1 because each element must be compared with the previous one. If the current element is greater than the previous element, the increasing streak continues, so current_length is incremented.

If the condition fails, the streak is broken, and the algorithm resets current_length back to 1.

After each update, the algorithm compares current_length with max_length to ensure the longest streak discovered so far is preserved.

Because the array is traversed exactly once and only a few integer variables are used, the implementation is both time-efficient and space-efficient.

Go Solution

func findLengthOfLCIS(nums []int) int {
    currentLength := 1
    maxLength := 1

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            currentLength++
        } else {
            currentLength = 1
        }

        if currentLength > maxLength {
            maxLength = currentLength
        }
    }

    return maxLength
}

The Go implementation follows the exact same logic as the Python version. Go uses explicit variable declarations with := and standard for loop syntax.

One important detail is that the problem guarantees the array has at least one element, so no special handling for empty slices is necessary.

Go slices are dynamically sized views over arrays, so indexing works similarly to Python lists. Integer overflow is not a concern because the maximum subsequence length is at most 10^4.

Worked Examples

Example 1

Input:

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

Initial state:

• current_length = 1
• max_length = 1

i	nums[i-1]	nums[i]	Increasing?	current_length	max_length
1	1	3	Yes	2	2
2	3	5	Yes	3	3
3	5	4	No	1	3
4	4	7	Yes	2	3

Final answer:

3

The longest continuous increasing subsequence is [1,3,5].

Example 2

Input:

nums = [2,2,2,2,2]

Initial state:

• current_length = 1
• max_length = 1

i	nums[i-1]	nums[i]	Increasing?	current_length	max_length
1	2	2	No	1	1
2	2	2	No	1	1
3	2	2	No	1	1
4	2	2	No	1	1

Final answer:

1

Since equal values are not strictly increasing, every streak has length 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm performs one pass through the input array, making a constant amount of work for each element. No additional data structures proportional to input size are required, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.findLengthOfLCIS([1, 3, 5, 4, 7]) == 3  # standard mixed case
assert solution.findLengthOfLCIS([2, 2, 2, 2, 2]) == 1  # all equal values
assert solution.findLengthOfLCIS([1]) == 1  # single element
assert solution.findLengthOfLCIS([1, 2, 3, 4, 5]) == 5  # fully increasing
assert solution.findLengthOfLCIS([5, 4, 3, 2, 1]) == 1  # fully decreasing
assert solution.findLengthOfLCIS([1, 2, 2, 3, 4]) == 3  # duplicate breaks streak
assert solution.findLengthOfLCIS([-5, -4, -3, -2]) == 4  # negative increasing values
assert solution.findLengthOfLCIS([10, 20, 10, 20, 30]) == 3  # multiple streaks
assert solution.findLengthOfLCIS([1, 3, 5, 7]) == 4  # entire array valid
assert solution.findLengthOfLCIS([9, 1, 2, 3, 0, 1]) == 3  # reset and restart

Test	Why
[1,3,5,4,7]	Verifies standard mixed increasing and decreasing behavior
[2,2,2,2,2]	Ensures strict inequality is enforced
[1]	Validates single-element boundary case
[1,2,3,4,5]	Confirms entire array can be the answer
[5,4,3,2,1]	Ensures decreasing arrays return 1
[1,2,2,3,4]	Verifies duplicates correctly reset streak
[-5,-4,-3,-2]	Confirms negative values work normally
[10,20,10,20,30]	Tests multiple independent streaks
[1,3,5,7]	Validates uninterrupted increasing sequence
[9,1,2,3,0,1]	Ensures reset logic functions correctly

Edge Cases

A single-element array is the smallest valid input. A naive implementation might accidentally return 0 if it assumes at least one comparison must occur. This implementation correctly initializes both current_length and max_length to 1, ensuring the answer is valid even when the loop never executes.

Arrays with repeated values are another important edge case. Since the problem requires strict increase, equal adjacent values must break the streak. For example, [2,2,2] should return 1, not 3. The implementation uses the condition nums[i] > nums[i - 1], which correctly excludes equality.

A fully decreasing array such as [5,4,3,2,1] can expose bugs where implementations incorrectly accumulate lengths. In this case, every comparison fails, so the current streak resets to 1 at every step. The implementation handles this naturally through the reset logic.

Another subtle case occurs when the longest streak appears at the end of the array, such as [1,2,0,3,4,5]. Some implementations incorrectly update the maximum only when a streak ends. This solution updates max_length during every iteration, ensuring the final streak is properly counted.