Longest Strictly Increasing or Strictly Decreasing Subarray

Easy
1843.

Longest Strictly Increasing or Strictly Decreasing Subarray

Longest Strictly Increasing or Strictly Decreasing Subarray is an easy coding problem on arrays, asked in Amazon and Google interviews.

Given an integer array nums, return the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing.

A single element counts as both.

Example 1

Input
nums = [1,4,3,3,2]
Output
2
Explanation
[1,4] is increasing and [4,3] and [3,2] are decreasing; nothing longer works because of the repeated 3.

Example 2

Input
nums = [3,3,3,3]
Output
1
Explanation
Equal neighbours break both kinds of run, so only single elements qualify.

Example 3

Input
nums = [3,2,1]
Output
3
Explanation
The whole array is strictly decreasing.

Constraints

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestMonotonicSubarray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Strictly Increasing or Strictly Decreasing Subarray Solution

Longest Strictly Increasing or Strictly Decreasing Subarray solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Strictly Increasing or Strictly Decreasing Subarray is an easy coding problem on arrays, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums, return the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing.

A single element counts as both.

Example 1

Input: nums = [1,4,3,3,2]
Output: 2
Explanation: [1,4] is increasing and [4,3] and [3,2] are decreasing; nothing longer works because of the repeated 3.

Example 2

Input: nums = [3,3,3,3]
Output: 1
Explanation: Equal neighbours break both kinds of run, so only single elements qualify.

Example 3

Input: nums = [3,2,1]
Output: 3
Explanation: The whole array is strictly decreasing.

Constraints

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

Hints for Longest Strictly Increasing or Strictly Decreasing Subarray

  1. Hint 1

    A strictly increasing subarray can always be extended as long as the next element is larger — think in terms of maximal runs.

  2. Hint 2

    Walk the array once, keeping the length of the increasing run and of the decreasing run that end at the current index.

  3. Hint 3

    When nums[i] > nums[i - 1] the increasing run grows and the decreasing run restarts at 1; the opposite for <; both restart on equality.

How to solve Longest Strictly Increasing or Strictly Decreasing Subarray

Track two run lengths ending at each index — one for strictly increasing, one for strictly decreasing. Each step either extends a run or resets it to 1, and the answer is the largest value either reaches.

Approach

  1. Set inc = dec = best = 1.
  2. For each i >= 1: if nums[i] > nums[i - 1], then inc += 1 and dec = 1; if nums[i] < nums[i - 1], then dec += 1 and inc = 1; otherwise both become 1.
  3. Update best = max(best, inc, dec) and return it.

Why it works

inc at index i is exactly the length of the longest strictly increasing subarray ending at i: it can extend the one ending at i - 1 precisely when nums[i] > nums[i - 1]. The same holds for dec, and every candidate subarray ends somewhere, so the maximum over all i is the answer.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Equal neighbours break both runs — "strictly" means [3,3] is neither increasing nor decreasing.
  • Start best at 1: a one-element array is a valid answer of length 1.

Reference solution

Python

from typing import List

def longestMonotonicSubarray(nums: List[int]) -> int:
    inc = dec = best = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            inc, dec = inc + 1, 1
        elif nums[i] < nums[i - 1]:
            inc, dec = 1, dec + 1
        else:
            inc = dec = 1
        best = max(best, inc, dec)
    return best

Java

public static int longestMonotonicSubarray(int[] nums) {
    int inc = 1, dec = 1, best = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) { inc++; dec = 1; }
        else if (nums[i] < nums[i - 1]) { dec++; inc = 1; }
        else { inc = 1; dec = 1; }
        best = Math.max(best, Math.max(inc, dec));
    }
    return best;
}

C++

int longestMonotonicSubarray(vector<int>& nums) {
    int inc = 1, dec = 1, best = 1;
    for (size_t i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) { inc++; dec = 1; }
        else if (nums[i] < nums[i - 1]) { dec++; inc = 1; }
        else { inc = 1; dec = 1; }
        best = max(best, max(inc, dec));
    }
    return best;
}

JavaScript

var longestMonotonicSubarray = function(nums) {
    var inc = 1, dec = 1, best = 1;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) { inc++; dec = 1; }
        else if (nums[i] < nums[i - 1]) { dec++; inc = 1; }
        else { inc = 1; dec = 1; }
        best = Math.max(best, inc, dec);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays