Scale Engineer

Longest Strictly Increasing or Strictly Decreasing Subarray

Easy
#2758Time: 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: O(1) extra space. We only use a few variables to store lengths and indices, which does not depend on the input size.1 company
Data structures
Array
Companies
Larsen Toubro

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1) extra space. We only use a few variables to store lengths and indices, which does not depend on the input size.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem