3105. Longest Strictly Increasing or Strictly Decreasing Subarray

  • Array
TIME
O(n)
SPACE
O(1)
problem on leetcode ↗source on github ↗

Intuition

A strictly increasing subarray ending at i extends the one ending at i - 1 exactly when nums[i] > nums[i - 1]; otherwise it starts over at length 1. The same holds for decreasing with <. So two running lengths are enough, and the answer is the largest value either one ever reaches.

Approach

  1. Start with inc = dec = best = 1 (a single element counts as both).
  2. For each i from 1:
    • nums[i] > nums[i - 1]: inc += 1, dec = 1
    • nums[i] < nums[i - 1]: dec += 1, inc = 1
    • equal: both reset to 1, since neither run can include an equal pair
  3. After each step, best = max(best, inc, dec).

Complexity

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

Edge Cases

  • A single element: the answer is 1
  • All equal (example 2): every step resets, so the answer stays 1
  • An equal pair inside a run ([1, 2, 2, 3]): it breaks the run, so the answer is 2, not 3
  • The whole array is monotonic (example 3): the answer is n
  • A run that changes direction ([1, 3, 2]): the peak element ends one run and starts the next, so the answer is 2

Code

from typing import List


class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        """
        3105. Longest Strictly Increasing or Strictly Decreasing Subarray
        Time: O(n)
        Space: O(1)
        """
        # inc / dec = length of the strictly increasing / decreasing run ending here.
        inc = dec = best = 1
        for prev, cur in zip(nums, nums[1:]):
            if cur > prev:
                inc, dec = inc + 1, 1
            elif cur < prev:
                inc, dec = 1, dec + 1
            else:
                inc = dec = 1
            best = max(best, inc, dec)
        return best