674. Longest Continuous Increasing Subsequence
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 46.0%
Problem Breakdown
The problem asks us to find the length of the longest continuous increasing subsequence in an unsorted array of integers. A continuous increasing subsequence means that each element in the subarray is strictly greater than the previous one.
Inputs:
- An array of integers
nums.
Outputs:
- The length of the longest continuous increasing subsequence.
Implicit Constraints or Tricky Edge Cases:
- If the input array is empty, the output should be 0.
- If all elements are the same, the longest continuous increasing subsequence will have a length of 1 (each element is by itself).
- Negative numbers and large integers are possible in the array.
Intuition
A brute-force approach would involve checking every possible subarray to see if it is strictly increasing. This would result in a time complexity of O(n^2), which is inefficient for larger arrays.
The key insight is that we can use a single pass through the array while keeping track of the current length of the increasing subsequence. Whenever we encounter an element that is not greater than the previous one, we reset our counter and start a new subsequence. This approach ensures that we only traverse the array once, leading to a time complexity of O(n).
Approach
- Initialize two variables:
max_lengthto keep track of the maximum length of continuous increasing subsequences found so far, andcurrent_lengthto count the current length of the ongoing subsequence. - Iterate through the array starting from the second element.
- For each element, compare it with the previous one:
- If the current element is greater than the previous one, increment
current_length. - Otherwise, update
max_lengthifcurrent_lengthis greater, and resetcurrent_lengthto 1.
- If the current element is greater than the previous one, increment
- After the loop, perform a final check to update
max_lengthin case the longest subsequence ends at the last element of the array. - Return
max_length.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input array. We only traverse the array once.
- Space Complexity: O(1). We use a constant amount of extra space for variables.
Solution
def findLengthOfLCIS(nums):
if not nums:
return 0
max_length = 1
current_length = 1
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
current_length += 1
else:
max_length = max(max_length, current_length)
current_length = 1
# Final check to update max_length
max_length = max(max_length, current_length)
return max_length
Edge Cases Handled
- Empty Array: The function returns 0 immediately if the input array is empty.
- All Elements Same: Each element forms its own subsequence of length 1, so the result will be 1.
- Negative Numbers and Large Integers: The algorithm handles these naturally without any special cases.