algoadvance

Leetcode 674. Longest Continuous Increasing Subsequence

Problem Statement

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (LCIS).

A subsequence is continuous if it appears in consecutive indices of the array.

Clarifying Questions

  1. Array Contents: Can the array contain negative numbers and zero?
    • Yes, the array can contain any integers.
  2. Array Length: What is the typical size range of the array?
    • The array can have a length from 0 to 10,000.
  3. Duplicates: Are duplicates allowed in the array?
    • Yes, duplicates are allowed.
  4. Output: What should be the output if the array is empty?
    • The output should be 0 since there are no elements to form a subsequence.

Strategy

To solve this problem effectively:

  1. We will initialize two variables:
    • maxLength to keep track of the maximum length of any LCIS found.
    • currentLength to keep track of the current LCIS length as we iterate through the array.
  2. We will iterate through the array starting from the first element.
  3. For each element, we will compare it with the previous element.
    • If the current element is greater than the previous element, it means the subsequence is still increasing, so we increment currentLength.
    • If not, we potentially found the end of a subsequence. We then:
      • Update maxLength if currentLength is greater.
      • Reset currentLength to 1 since a new subsequence might begin at the current element.
  4. After iterating through the array, we perform a final comparison to ensure the last subsequence is considered.

Code

public class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxLength = 1;
        int currentLength = 1;

        // Iterate through the array
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                currentLength++;
            } else {
                maxLength = Math.max(maxLength, currentLength);
                currentLength = 1;
            }
        }

        // Final check to update maxLength in case the longest LCIS ends at the last element
        maxLength = Math.max(maxLength, currentLength);

        return maxLength;
    }
}

Time Complexity

This approach ensures an efficient and clear solution to the problem of finding the longest continuous increasing subsequence.

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