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 <= 104-109 <= nums[i] <= 109The key idea in Longest Continuous Increasing Subsequence is to track the length of increasing elements that appear consecutively in an array. Unlike general subsequence problems, the elements here must remain adjacent, which simplifies the approach significantly.
A common strategy is to perform a single linear scan of the array while maintaining a counter for the current increasing streak. If the current element is greater than the previous one, the streak continues; otherwise, it resets. During traversal, you keep updating the maximum length encountered so far.
This method works efficiently because each element is processed only once. By comparing adjacent values and updating counters, you can determine the longest increasing continuous segment without additional data structures.
The approach runs in O(n) time since the array is scanned once, and it uses O(1) extra space because only a few variables are maintained.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass Linear Scan | O(n) | O(1) |
NeetCode
This approach involves iterating through the array while maintaining a variable to track the length of the current continuous increasing subsequence. As we encounter each element, we check if it is larger than the previous one to decide if we should continue the current subsequence or start a new one. We also maintain a global maximum to store the maximum length found during our iteration.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we use a constant amount of space.
1#include <stdio.h>
2
3int findLengthOfLCIS(int* nums, int numsSize) {
4 if (numsSize == 0) return 0;
The function findLengthOfLCIS accepts an array and its size. We initialize maxLen and currLen to 1. We iterate through the array, and whenever the current element is greater than the previous one, we increase currLen. If currLen exceeds maxLen, we update maxLen. When the sequence breaks, we reset currLen to 1.
The greedy approach leverages a single pass through the array to determine the maximum length of an increasing subsequence. This method is optimal because it immediately processes each element only once, updating the sequence lengths on the fly, and computing the maximum without revisiting any part of the array.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as no additional space other than variables is utilized.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
LIS (Longest Increasing Subsequence) allows elements to be non-adjacent, while LCIS requires elements to be strictly increasing and continuous in the array. Because of this constraint, LCIS can often be solved with a simpler linear scan approach.
Yes, variations of array traversal and sequence tracking problems are common in FAANG-style interviews. This problem helps assess a candidate's ability to handle array scanning, edge cases, and optimal time complexity.
No special data structure is required for this problem. A few integer variables are enough to track the current sequence length and the maximum length while scanning the array.
The optimal approach is a single-pass linear scan of the array. Track the current increasing streak and reset it whenever the sequence stops increasing. Maintain a maximum length variable to store the longest streak found during traversal.
This code utilizes a greedy solution where it enters the loop with the ability to modify the beginning of sequences implicitly by re-syncing the currLen, ensuring we keep the cost constant per iteration.