LeetCode, 𝐃𝐚𝐲-34/365-DSA-Coding 𝐉𝐨𝐮𝐫𝐧𝐞𝐲…Google Prep…

Problem: 3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Problem Overview

Given an integer array nums, find the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing. A strictly monotonic subarray means that consecutive elements must be either strictly increasing or strictly decreasing without any equality.

Challenges Involved

• Handling Transitions: The array may switch between increasing and decreasing trends at any index.
• Avoiding Equality: Unlike general monotonic problems, elements must be strictly increasing or decreasing (i.e., nums[i] != nums[i+1]).
• Edge Cases: Single-element arrays, completely increasing/decreasing arrays, and arrays with repeated elements.

Solution Approach

Single Pass with Two Counters

• Maintain two counters: inc_length for strictly increasing sequences and dec_length for strictly decreasing sequences.
• Reset counters when encountering equal elements.
• Track the maximum value of either counter throughout the traversal.
• Time Complexity: O(N), as we iterate through nums once.

Python Code

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        inc_length = dec_length = max_length = 1

        for i in range(len(nums) - 1):
            if nums[i + 1] > nums[i]:  # Increasing case
                inc_length += 1
                dec_length = 1  # Reset decreasing counter
            elif nums[i + 1] < nums[i]:  # Decreasing case
                dec_length += 1
                inc_length = 1  # Reset increasing counter
            else:  # Equality case (reset both)
                inc_length = dec_length = 1
            
            max_length = max(max_length, inc_length, dec_length)
        
        return max_length

Other Approaches

Sliding Window Approach

• Maintain two pointers marking the start and end of a monotonic subarray.
• Expand the window while maintaining strict monotonicity.
• Reset the window on equality or transition.
• Time Complexity: O(N).

Sorting and Binary Search

• Sort nums to find possible longest increasing or decreasing subarrays.
• Use binary search to find the longest valid sequence.
• Time Complexity: O(N log N) (due to sorting).

Dynamic Programming (DP)

• Maintain inc[i] and dec[i] arrays, tracking longest increasing and decreasing sequences ending at index i.
• Use DP transitions based on comparisons.
• Time Complexity: O(N) but requires extra O(N) space.

Learnings

• Tracking two counters efficiently handles monotonic sequences in one pass.
• Sorting-based approaches provide alternative methods but aren’t optimal.
• Sliding window techniques dynamically adjust subarray length.

Real-Life Applications

• Stock Market Analysis: Identifying longest bullish/bearish trends.
• Sports Performance Tracking: Finding longest streaks of increasing or decreasing scores.
• User Engagement Trends: Detecting longest continuous increase or decrease in app usage.

Short Takeaway

This problem is about finding the longest strictly increasing or decreasing subarray. The optimal approach uses a single-pass method with two counters to track increasing and decreasing trends efficiently.