674. Longest Continuous Increasing Subsequence
Problem Description
The task is to find the length of the longest strictly increasing contiguous subsequence within an array of integers, nums
. A subsequence is considered continuous increasing if each element is strictly greater than the preceding one with no interruptions. In more concrete terms, given indices l
and r
where l < r
, the elements at [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]
must satisfy nums[i] < nums[i + 1]
for all l <= i < r
. The aim is to determine the maximum length of such a subsequence within the given array.
Intuition
To find this maximum length of a continuous increasing subsequence, we iterate through the array, keeping track of the length of the current increasing subsequence (f
) and the longest increasing subsequence found so far (res
).
As we move through the array, we compare each element with its predecessor. If the current element is greater than the previous one, it can extend an increasing subsequence; thus, we increment the length of the current increasing subsequence (f
). If the element does not increase compared to the previous one, it signifies the end of the current increasing subsequence, and we reset the current length (f
) to 1, starting a new subsequence from this element.
After each step, we need to check if the last computed increasing subsequence length (f
) is greater than the current maximum length we've found (res
). If it is, we update res
with the new maximum length. This process continues until we go through all the array elements. By the end, res
will hold the length of the longest continuous increasing subsequence in the array.
Solution Approach
The solution uses a simple linear scan of the array, which is an efficient algorithmic pattern suited for this problem. No additional data structures are used, leveraging the original array to find the solution, which grants an O(1)
space complexity.
Here's how the algorithm works in detail:
-
Initialization: Two variables are initialized:
res
andf
, both with the value1
.res
will store the maximum length of a continuous increasing subsequence found so far, andf
tracks the length of the current increasing subsequence as we iterate through the array. -
Iteration: We then iterate through the array starting from the second element (at index
1
) all the way to the end. -
Subsequence Extension: For every element
nums[i]
, we compare it with the previous elementnums[i - 1]
. Ifnums[i]
is greater thannums[i - 1]
, the current subsequence is increasing, and so we incrementf
by1
. In essence, the operation isf = 1 + (f if nums[i - 1] < nums[i] else 0)
, which can be read as "setf
to1
plus (continue adding tof
if the subsequence is increasing, otherwise resetf
to1
)". -
Update Maximum Length: After evaluating whether the subsequence can be extended or needs to be restarted, we next update
res
to be the maximum of its current value orf
. The expressionres = max(res, f)
ensures thatres
always contains the length of the longest continuous increasing subsequence found at any point in the scan. -
Result: After the iteration completes, the value of
res
is the final answer and is returned. This represents the longest length of a continuous increasing subsequence in the arraynums
.
No complex data structures are needed because we only track the length of the subsequences, not the subsequences themselves. The core pattern used here is a single-pass iteration with constant-time checks and updates, leading to an O(n)
time complexity, where n
is the number of elements in the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example array nums
to illustrate the solution approach: [2, 6, 4, 7, 8]
.
-
Initialization: We start by initializing
res
andf
to1
. This is because the minimum length for an increasing subsequence, by default, is1
(a single element).Currently
res = 1
,f = 1
. -
Iteration: We start iterating from the second element:
- At index
1
:nums[1]
is6
,nums[0]
is2
. Since6 > 2
, the subsequence is increasing. We incrementf
:f = f + 1 => 2
. - Now, we update
res
to be the maximum ofres
andf
. Sincef
is2
andres
is1
,res
becomes2
.
Current status:
res = 2
,f = 2
. - At index
-
Subsequence Extension:
- At index
2
:nums[2]
is4
,nums[1]
is6
. Since4
is not greater than6
, we resetf
to1
. res
remains unchanged because it is still holding the maximum found so far which is2
.
Current status:
res = 2
,f = 1
. - At index
-
Continuing the Iteration:
- At index
3
:nums[3]
is7
,nums[2]
is4
. Since7 > 4
, we consider this a continuation of an increasing subsequence and incrementf
:f = 1 + 1 => 2
. - Update
res
: It remains2
sincef
is not greater thanres
.
Current status:
res = 2
,f = 2
. - At index
-
Final Update:
- At index
4
:nums[4]
is8
,nums[3]
is7
. The increasing pattern continues; thus, we incrementf
:f = 2 + 1 => 3
. - Update
res
:res
becomes3
becausef
is now greater thanres
.
Current status (final):
res = 3
,f = 3
. - At index
-
Result: After completing the iteration, we have found that the length of the longest continuous increasing subsequence in
nums
is3
([4, 7, 8]), and we return this value.
This walkthrough has shown that the algorithm successfully identifies and tracks the lengths of increasing subsequences and maintains the length of the longest one found as it progresses through the array. With the time complexity of O(n)
and constant space usage, it is an efficient method for solving this problem.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findLengthOfLCIS(self, nums: List[int]) -> int:
5 # Initialize the length of the array
6 array_length = len(nums)
7
8 # Initialize the result and the current length of longest consecutive increasing subsequence (LCIS)
9 result = current_length = 1
10
11 # Loop through the array starting from the second element
12 for i in range(1, array_length):
13 # If the current number is greater than the previous one, increment current_length
14 if nums[i - 1] < nums[i]:
15 current_length += 1
16 else:
17 # Reset current_length if the sequence is not increasing
18 current_length = 1
19
20 # Update result with the maximum length found so far
21 result = max(result, current_length)
22
23 # Return the length of the longest consecutive increasing subsequence
24 return result
25
1class Solution {
2 public int findLengthOfLCIS(int[] nums) {
3 int maxLength = 1; // Initialize maxLength to 1 since the minimal length of subsequence is 1
4 int currentLength = 1; // Start with currentLength of 1, this will track the length of the current subsequence
5
6 // Loop through the array starting from the second element
7 for (int i = 1; i < nums.length; ++i) {
8 // If the current number is greater than the previous one, increase currentLength
9 if (nums[i - 1] < nums[i]) {
10 currentLength++;
11 } else {
12 currentLength = 1; // Reset currentLength to 1 if the sequence breaks
13 }
14
15 // Update maxLength if we found a longer subsequence
16 maxLength = Math.max(maxLength, currentLength);
17 }
18
19 return maxLength; // Return the result which is the length of longest continuous increasing subsequence
20 }
21}
22
1#include<vector>
2using namespace std;
3
4class Solution {
5public:
6 // This method finds the length of the longest contiguous increasing subsequence in the vector.
7 int findLengthOfLCIS(vector<int>& nums) {
8 if (nums.empty()) return 0; // If the vector is empty, return 0 because there's no subsequence.
9
10 int maxLength = 1; // Initialize maxLength to 1 since the minimum length is 1 if the vector is not empty.
11 int currentLength = 1; // This will keep track of the current increasing subsequence length.
12
13 // Loop through the vector starting from the second element.
14 for (int i = 1; i < nums.size(); ++i) {
15 // If the current element is greater than the previous one, increment the currentLength.
16 if (nums[i - 1] < nums[i]) {
17 currentLength++;
18 } else {
19 // Otherwise, reset currentLength to 1 because the sequence has been broken.
20 currentLength = 1;
21 }
22
23 // Update the maxLength if we found a longer subsequence.
24 maxLength = max(maxLength, currentLength);
25 }
26
27 // Return the length of the longest contiguous increasing subsequence.
28 return maxLength;
29 }
30};
31
1function findLengthOfLCIS(nums: number[]): number {
2 // The length of the input array.
3 const lengthOfNums = nums.length;
4 // Maximum length of the longest continuous increasing subsequence found so far.
5 let maxLength = 1;
6 // Starting index of the current subsequence under consideration.
7 let startIndex = 0;
8
9 // Loop through the array starting from index 1 to compare with previous elements.
10 for (let currentIndex = 1; currentIndex < lengthOfNums; currentIndex++) {
11 // If the current element is not larger than the previous,
12 // handle the end of the current increasing subsequence.
13 if (nums[currentIndex - 1] >= nums[currentIndex]) {
14 // Update the maxLength with the length of the just-ended subsequence if it's longer.
15 maxLength = Math.max(maxLength, currentIndex - startIndex);
16 // Update the startIndex to the current index as the start of a new subsequence.
17 startIndex = currentIndex;
18 }
19 }
20 // After the loop, compare the final subsequence with the current max length.
21 // This handles the case when the longest subsequence reaches the end of the array.
22 return Math.max(maxLength, lengthOfNums - startIndex);
23}
24
Time and Space Complexity
The code provided calculates the length of the longest continuous increasing subsequence (LCIS) in an array of integers.
Time Complexity
To determine the time complexity, we analyze the number of operations that are performed in relation to the size of the input array nums
.
The function iterates once over the array, starting from the second element, and performs a constant amount of work for each element by checking if the current element is greater than the previous element and updating the f
and res
variables accordingly.
Since there is only one loop over n
elements of the array, and within each iteration, the operations are performed in constant time, the time complexity of the function is O(n)
, where n
is the length of the input array nums
.
Space Complexity
To determine the space complexity, we analyze the amount of additional memory that the code uses in relation to the size of the input.
The function uses a fixed number of variables: n
, res
, and f
. No additional data structures that grow with input size are used. This means that the space used does not depend on the size of the input array, but is instead constant.
As a result, the space complexity of the function is O(1)
, indicating that it uses a constant amount of memory regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!