978.longest-turbulent-subarray.md

978. Longest Turbulent Subarray

Hints

• Try to use two pointers or a sliding window to track the current turbulent subarray: start..end.
• What is the condition for a subarray to be turbulent? How do you check if the pattern is broken?

Group by Consecutive (Edges)

A subarray is turbulent if the comparison sign between every adjacent pair alternates (i.e., > < > < or < > < >).

The key idea is to iterate through the array, and for each position, check if the current and previous comparisons alternate. If yes, try to expand the window. If not (either equal or the sign doesn't flip), reset the window.

// Backward
fun maxTurbulenceSize(arr: IntArray): Int {
    var ans = 1
    var i = 1 // I start from the 2nd element so that we can compare with previous element.
    while (i < arr.size) {
        // We skip the equal case, because it's not turbulent
        if (arr[i - 1] == arr[i]) {
            i++
            continue
        }

        // Start of the current group
        // We check the "edge", [i - 1, i]
        val start = i - 1
        var isIncreasing = arr[i - 1] < arr[i]
        // Move to the next position
        i++
        while (i < arr.size) {
            if (isIncreasing && arr[i - 1] > arr[i]) {
                isIncreasing = false
            } else if (isIncreasing.not() && arr[i - 1] < arr[i]) {
                isIncreasing = true
            } else {
                break
            }
            i++
        }
        // After the loop, i will be at the next position of the current group. (the start of the next group)
        ans = maxOf(ans, i - start)
    }
    return ans
}

// Forward
fun maxTurbulenceSize(arr: IntArray): Int {
    var i = 0
    val n = arr.size
    var ans = 1 // Single element has 1 length
    while (i + 1 < n) { // Check if we have the next element
        if (arr[i] == arr[i + 1]) {
            i++
            continue
        }
        var isIncreasing = arr[i] < arr[i + 1]
        val start = i
        i++
        while (i + 1 < n) {
            if (isIncreasing && arr[i] > arr[i + 1]) {
                isIncreasing = false
            } else if (!isIncreasing && arr[i] < arr[i + 1]) {
                isIncreasing = true
            } else {
                break
            }
            i++
        }
        // After the loop, i will be at the last position of the current group.
        ans = maxOf(ans, i - start + 1)
    }
    return ans
}

There is another implementation using a.compareTo(b) to check the adjacent elements:

• -1 means a < b
• 0 means a == b
• 1 means a > b

Then if the adjacent elements are alternate, then prev * next will be -1, where prev = arr[i - 1].compareTo(arr[i]) and next = arr[i].compareTo(arr[i + 1]).

• a < b: -1 * b > c = 1 (turbulent)
• Or a > b: 1 * b < c = -1 (turbulent)

fun maxTurbulenceSize(arr: IntArray): Int {
    val n = arr.size
    var ans = 1
    var start = 0
    for (i in 1 until n) {
        val prev = arr[i - 1].compareTo(arr[i])
        // Skip the equal case
        if (prev == 0) {
            start = i // We just reset the start
        } else { // Not equal
            // Check if the next element is the opposite of the current element
            if (i + 1 < n && arr[i].compareTo(arr[i + 1]) * prev == -1) {
                continue
            }
            // End of the current group or the last element, update the answer and reset the start
            ans = maxOf(ans, i - start + 1)
            start = i
        }
    }
    return ans
}

Dynamic Programming

Or equivalent, it's more popular from the discussions This solution uses dynamic programming to track the length of turbulent subarrays.

For each position i, we maintain two counters:

• inc: length of turbulent subarray ending at i where arr[i-1] < arr[i]
• dec: length of turbulent subarray ending at i where arr[i-1] > arr[i]

1. When we see arr[i-1] < arr[i]:
   • The current increasing pair can extend the previous decreasing sequence
   • So inc = dec + 1
   • And dec must reset to 1 since we can't extend a decreasing sequence
2. When we see arr[i-1] > arr[i]:
   • The current decreasing pair can extend the previous increasing sequence
   • So dec = inc + 1
   • And inc must reset to 1 since we can't extend an increasing sequence
3. When arr[i-1] == arr[i]:
   • Both sequences must reset to 1 since equal elements break turbulence

fun maxTurbulenceSize(arr: IntArray): Int {
    var ans = 1
    var inc = 1
    var dec = 1
    for (i in 1 until arr.size) {
        if (arr[i - 1] < arr[i]) {
            inc = dec + 1
            dec = 1
        } else if (arr[i - 1] > arr[i]) {
            dec = inc + 1
            inc = 1         
        } else {
            inc = 1
            dec = 1
        }
        ans = maxOf(ans, inc, dec)
    }
    return ans
}

• Time Complexity: O(N) where N is the length of arr.
• Space Complexity: O(1).

Edge Cases

• All elements are equal: answer is 1.
• Array of length 1: answer is 1.
• No turbulence (strictly increasing or decreasing): answer is 2.
• Multiple equal elements in a row: must reset the window.

Pitfalls

• Forgetting to skip the equal case.

Similar or Follow-up Problems

• 128. Longest Consecutive Sequence
• 376. Wiggle Subsequence