Longest Strictly Increasing or Strictly Decreasing Subarray

EASY

Description

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

Example 1:

Input: nums = [1,4,3,3,2]

Output: 2

Explanation:

The strictly increasing subarrays of nums are [1], [2], [3], [3], [4], and [1,4].

The strictly decreasing subarrays of nums are [1], [2], [3], [3], [4], [3,2], and [4,3].

Hence, we return 2.

Example 2:

Input: nums = [3,3,3,3]

Output: 1

Explanation:

The strictly increasing subarrays of nums are [3], [3], [3], and [3].

The strictly decreasing subarrays of nums are [3], [3], [3], and [3].

Hence, we return 1.

Example 3:

Input: nums = [3,2,1]

Output: 3

Explanation:

The strictly increasing subarrays of nums are [3], [2], and [1].

The strictly decreasing subarrays of nums are [3], [2], [1], [3,2], [2,1], and [3,2,1].

Hence, we return 3.

Constraints:

1 <= nums.length <= 50
1 <= nums[i] <= 50

Approaches

Checkout 2 different approaches to solve Longest Strictly Increasing or Strictly Decreasing Subarray. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

This approach iterates through each possible starting point of a subarray. For each starting point, it expands the subarray to the right, checking for both strictly increasing and strictly decreasing properties. It keeps track of the maximum length found across all possible starting points.

Algorithm

Initialize a variable maxLength to 1.
Iterate through the array with an index i from 0 to n-1, considering each element as a potential starting point of a subarray.
For each i, find the length of the longest strictly increasing subarray starting at i.
- Initialize currentIncLength = 1.
- Iterate with index j from i + 1 to n-1. If nums[j] > nums[j-1], increment currentIncLength. Otherwise, break the inner loop.
- Update maxLength = max(maxLength, currentIncLength).
For each i, find the length of the longest strictly decreasing subarray starting at i.
- Initialize currentDecLength = 1.
- Iterate with index j from i + 1 to n-1. If nums[j] < nums[j-1], increment currentDecLength. Otherwise, break the inner loop.
- Update maxLength = max(maxLength, currentDecLength).
After checking all starting points i, return maxLength.

In this approach, we systematically check every possible subarray. We use a nested loop structure. The outer loop selects a starting index i for a subarray. The inner loops then extend this subarray from i to the right, one element at a time, checking for two conditions separately: if the subarray remains strictly increasing and if it remains strictly decreasing.

For each starting index i, we calculate the length of the longest strictly increasing subarray that begins at i and the length of the longest strictly decreasing subarray that also begins at i. We then update a global maxLength variable with the larger of these two lengths if they exceed the current maxLength. By iterating i through the entire array, we ensure that we have considered all possible monotonic subarrays.

class Solution {
    public int longestMonotonicSubarray(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int maxLength = 1;
        for (int i = 0; i < nums.length; i++) {
            // Check for longest increasing subarray starting at i
            int currentIncLength = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[j - 1]) {
                    currentIncLength++;
                } else {
                    break;
                }
            }
            maxLength = Math.max(maxLength, currentIncLength);

            // Check for longest decreasing subarray starting at i
            int currentDecLength = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[j - 1]) {
                    currentDecLength++;
                } else {
                    break;
                }
            }
            maxLength = Math.max(maxLength, currentDecLength);
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n^2), where `n` is the length of `nums`. The outer loop runs `n` times, and for each iteration, the inner loops can run up to `n` times in the worst case (e.g., a sorted or reverse-sorted array).Space Complexity: O(1) extra space. We only use a few variables to store lengths and indices, which does not depend on the input size.

Pros and Cons

Pros:

More efficient than a naive O(n^3) approach which checks every single subarray independently.
Relatively simple to reason about and implement.

Cons:

Not the most optimal solution as it has a quadratic time complexity.
It performs redundant computations by re-scanning parts of the array multiple times.

Code Solutions

Checking out 4 solutions in different languages for Longest Strictly Increasing or Strictly Decreasing Subarray. Click on different languages to view the code.

class Solution {
public
  int longestMonotonicSubarray(int[] nums) {
    int ans = 1;
    for (int i = 1, t = 1; i < nums.length; ++i) {
      if (nums[i - 1] < nums[i]) {
        ans = Math.max(ans, ++t);
      } else {
        t = 1;
      }
    }
    for (int i = 1, t = 1; i < nums.length; ++i) {
      if (nums[i - 1] > nums[i]) {
        ans = Math.max(ans, ++t);
      } else {
        t = 1;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Longest Strictly Increasing or Strictly Decreasing Subarray

Data Structures:

Array

Companies:

Larsen Toubro |

Longest Strictly Increasing or Strictly Decreasing Subarray

Description

Approaches

Brute Force with Nested Loops

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Data Structures:

Companies:

On this page

Subscribe to Scale Engineer newsletter