algoadvance

Leetcode 3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Problem Statement

You are given an integer array nums. A subarray of a given array is called strictly increasing if all the elements of this subarray are in increasing order, and strictly decreasing if all the elements of this subarray are in decreasing order. Return the length of the longest subarray that is either strictly increasing or strictly decreasing.

Example 1:

Example 2:

Example 3:

Clarifying Questions

  1. Are the elements in the array all integers?
    • Yes, the array contains integers.
  2. Is an empty array possible as input?
    • The problem doesn’t clarify, but typically an empty array would have a longest subarray of length 0.
  3. What is the upper limit on the length of the input array?
    • Let’s assume the typical constraint for a LeetCode problem, which is up to 10^5 elements.

Strategy

  1. Iterate through the array:
    • Track lengths of both increasing and decreasing subarrays.
    • Use two pointers inc and dec, to keep track of the current length of strictly increasing and strictly decreasing subarrays.
    • Update the maximum length encountered during the traversal.
  2. Handle corner cases:
    • Single-element arrays should return a length of 1.
    • Empty arrays should return a length of 0.

Algorithm

  1. Initialize variables max_length, inc, and dec to store the maximum required length and current lengths of subarrays.
  2. Traverse the array:
    • Update inc and reset dec if a strictly increasing sequence is found.
    • Update dec and reset inc if a strictly decreasing sequence is found.
    • Always update max_length with the maximum value of inc or dec.
  3. Return the max_length.

Code

Here’s how you might implement this algorithm in C++:

#include <vector>
#include <algorithm>

int longest_strictly_inc_or_dec_subarray(const std::vector<int>& nums) {
    int inc = 1, dec = 1, max_length = 1;
    
    // Edge case for empty array
    if (nums.empty()) {
        return 0;
    }

    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i - 1]) {
            inc = dec + 1;
            dec = 1;
        } else if (nums[i] < nums[i - 1]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = dec = 1;
        }
        max_length = std::max(max_length, std::max(inc, dec));
    }
    
    return max_length;
}

Time Complexity

The time complexity of this approach is O(n) where n is the length of the input array nums. This is because we are traversing the array exactly once.

The space complexity is O(1) as only a constant amount of extra space is used, regardless of the input array size.

This ensures the solution is efficient and can handle large input sizes within typical constraints.

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