978. Longest Turbulent Subarray

📝 Problem Details

• Title: 978. Longest Turbulent Subarray
• Link: https://leetcode.com/problems/longest-turbulent-subarray/
• Difficulty: Medium
• Tags/Categories: Sliding-Window Arrays

💭What Were My Initial Thoughts?

- we can use a sliding window to maintain the bounds of the current turbulent subarray
- expand of shrink the iwndow based on whether the condition is satisfied 

🤔What Did I Struggle With?

~ phrasing of the question was difficult to grasp in an interview setting

💡 Explanation of Solution

- **Initialization**:
    - Start with a window `[start, end]` where `start = 0` and `end = 1`.
    - Track the maximum turbulent length using `maxLength`.

- **Sliding the Window**:    
    - As `end` expands, check the turbulent condition for the triplet arr[end−2],arr[end−1],arr[end]arr[end-2], arr[end-1], arr[end]arr[end−2],arr[end−1],arr[end]:
        - If turbulent: Continue expanding the window (`end++`).
        - If not turbulent: Reset the `start` to `end - 1` and begin a new window.

- **Update the Result**:
    - For every valid turbulent window, update `maxLength` to the size of the current window (end−start+1end - start + 1end−start+1).

- **Edge Cases**:    
    - Handle cases where arr[i]==arr[i+1]arr[i] == arr[i+1]arr[i]==arr[i+1] (restart the window).
    - Arrays of length 1 or 2 are edge cases.

⌛ Complexity Analysis

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

💻 Implementation of Solution

int maxTurbulenceSize(vector<int>& arr) {
    int n = arr.size();
    if (n < 2) return n; // Edge case: single-element array
 
    int start = 0, maxLength = 1; // Initialize start and max length
 
    for (int end = 1; end < n; ++end) {
        // Determine the comparison between arr[end-1] and arr[end]
        int cmp = (arr[end] > arr[end-1]) - (arr[end] < arr[end-1]);
 
        if (cmp == 0) {
            // Not turbulent, reset the window
            start = end;
        } else if (end == n - 1 || cmp * ((arr[end+1] > arr[end]) - (arr[end+1] < arr[end])) != -1) {
            // End of a turbulent segment
            maxLength = max(maxLength, end - start + 1);
            start = end; // Reset the window for the next segment
        }
    }
 
    return maxLength;
}