Find the Longest Continuous Increasing Subsequence
GoogleSoftware Engineer · OnsiteLast updated
Tests array traversal, state tracking, and boundary handling to find the maximum length of a contiguous, strictly increasing run in linear time.
Problem Statement
Given an array of integers nums, find the length of the longest continuous strictly increasing subarray.
A continuous increasing subarray is defined as a sequence of adjacent elements [nums[i], nums[i + 1], ..., nums[j]] such that for all k where i <= k < j, nums[k] < nums[k + 1].
Note that equal adjacent values (e.g., nums[k] == nums[k + 1]) do not qualify as strictly increasing and must terminate the current run.
Function Signature
def find_length_of_lcis(nums: list[int]) -> int:
pass
Examples
Example 1
Input: nums = [1, 3, 5, 4, 7]
Output: 3
Explanation: The longest continuous increasing subarray is [1, 3, 5] with length 3.
Even though [1, 3, 5, 7] is increasing, it is not continuous (index 3 is skipped).
Example 2
Input: nums = [2, 2, 2, 2, 2]
Output: 1
Explanation: The longest continuous increasing subarray is [2] with length 1 because equal adjacent elements break the strictly increasing condition.
Example 3
Input: nums = []
Output: 0
Explanation: An empty array has no elements, so the maximum length is 0.
Constraints
0 <= len(nums) <= 10^5-10^9 <= nums[i] <= 10^9- Time complexity should be
O(n)withO(1)auxiliary space.
Hints
Hint 1
Because the elements must be contiguous, any element that is less than or equal to its preceding element immediately terminates the current increasing sequence.
Hint 2
Maintain two variables as you iterate: one to track the length of the current run and another to record the maximum length found so far.
Hint 3
Ensure your initialization properly accounts for an empty array versus an array containing at least one element.
Follow-up questions
- How would you modify the solution to return the starting and ending indices of the longest run, breaking ties by returning the earliest occurrence?
- How would the problem change if the array were circular (i.e., the last element connects to the first element)?
- What if you were allowed to remove at most one element to potentially merge two adjacent increasing runs?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.