algoadvance

Leetcode 674. Longest Continuous Increasing Subsequence

Problem Statement

Given an unsorted array of integers, find the length of the longest continuous increasing subsequence (subarray).

Example:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is an increasing subsequence, it’s not continuous as elements 5 and 7 are separated by 4.

Example:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Clarifying Questions

  1. Are the input numbers always integers?
    • Yes, they are.
  2. Can the input contain negative numbers or zeros?
    • Yes, the input can contain any integer values.
  3. What is the expected size of the input array?
    • The size of the array can vary, typically within the constraints of typical online coding problems, might be up to 10^4.
  4. What should be returned if the input array is empty?
    • If the input array is empty, the function should return 0.

Strategy

This problem can be effectively solved using a single pass (O(n) time complexity) algorithm. We can maintain a variable to keep track of the current length of the increasing subsequence and another variable to store the maximum length found so far.

  1. Initialize two variables, maxLen and currLen, to 1 since the minimum length for any subsequence with at least one element is 1.
  2. Iterate through the array starting from the second element:
    • If the current element is larger than the previous element, increase currLen by 1.
    • Otherwise, compare currLen with maxLen and update maxLen if necessary, then reset currLen to 1.
  3. After the loop, do a final comparison between currLen and maxLen in case the longest subsequence is at the end of the array.
  4. Return maxLen.

Code

#include <vector>
#include <algorithm> // For std::max

class Solution {
public:
    int findLengthOfLCIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int maxLen = 1;
        int currLen = 1;
        
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) {
                ++currLen;
            } else {
                maxLen = std::max(maxLen, currLen);
                currLen = 1;
            }
        }
        
        // Final comparison in case the longest sequence ends at the last element
        maxLen = std::max(maxLen, currLen);
        
        return maxLen;
    }
};

Time Complexity

The time complexity for this algorithm is O(n), where n is the size of the input array. This is because we only make a single pass through the array.

The space complexity is O(1) since we are only using a fixed amount of extra space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI