Longest Turbulent Subarray

NeetCode: Longest Turbulent Subarray · LeetCode: 978. Longest Turbulent Subarray · Difficulty: Medium

A subarray is turbulent if the comparison sign between adjacent elements alternates: a[0] < a[1] > a[2] < ... or a[0] > a[1] < a[2] > .... Return the length of the longest turbulent subarray of arr.

Example

Text

Input:  arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]    Output: 5   ([4, 2, 10, 7, 8])
Input:  arr = [4, 8, 12, 16]                  Output: 2
Input:  arr = [100]                           Output: 1

Brute force: extend from every start

From each start, keep extending while the sign of the comparison between arr[j] and arr[j-1] is non-zero and differs from the previous sign, and record the longest run. Each start may scan to the end, so the worst case is quadratic, for example on a perfect zig-zag array. Integer.compare(a, b) returns a negative number, zero, or a positive number, and Integer.signum turns that into -1, 0, or 1. The code compares with Integer.compare and never subtracts, because arr[j] - arr[j-1] can overflow int.

Java

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int best = 0;
        for (int start = 0; start < n; start++) {
            int len = 1;
            int prevSign = 0; // sign of the previous comparison
            for (int j = start + 1; j < n; j++) {
                int sign = Integer.signum(Integer.compare(arr[j], arr[j - 1]));
                if (sign == 0 || sign == prevSign) {
                    break;
                }
                len++;
                prevSign = sign;
            }
            best = Math.max(best, len);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxTurbulenceSize(new int[]{9, 4, 2, 10, 7, 8, 8, 1, 9}));
        System.out.println(s.maxTurbulenceSize(new int[]{4, 8, 12, 16}));
        System.out.println(s.maxTurbulenceSize(new int[]{100}));
        System.out.println(s.maxTurbulenceSize(new int[]{}));
    }
}

Output

Time: O(n^2). Space: O(1).

Java

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        int up = 1;
        int down = 1;
        int best = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                up = down + 1;
                down = 1;
            } else if (arr[i] < arr[i - 1]) {
                down = up + 1;
                up = 1;
            } else {
                up = 1;
                down = 1;
            }
            best = Math.max(best, Math.max(up, down));
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxTurbulenceSize(new int[]{9, 4, 2, 10, 7, 8, 8, 1, 9}));
        System.out.println(s.maxTurbulenceSize(new int[]{4, 8, 12, 16}));
        System.out.println(s.maxTurbulenceSize(new int[]{100}));
        System.out.println(s.maxTurbulenceSize(new int[]{}));
    }
}

Output

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