Longest Turbulent Subarray

Companies:
  • Amazon Interview Questions
  • Uber Interview Questions

A subarray A[i], A[i+1], …, A[j] of A is said to be turbulent if and only if:

  • For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
  • OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [8,5,1,7,6,8,7,1,9]

Output: 6

Explanation: (A[1] > A[2] < A[3] > A[4] < A[5] >A[6])

Note:

  1. 1 <= A.length <= 40000
  2. 0 <= A[i] <= 10^9

Solution:

To find the maximum subarray possible we will traverse the array once using a sliding window. Comparison can be made using -1,0,1 in place of (<,=,>). Since we only have to take care of the countings so using these techniques will reduce our complexity efficiently. So, the subarray with the longest [-1,1-1,1…] will be our answer.

Implementation:

bool isPosL(vector<int>&arr, int ind, int low)
    {
        bool res = true;
        if(ind-2 >= low)
        {
            return (arr[ind-1] > arr[ind] && arr[ind-1] > arr[ind-2]) ||(arr[ind-1] < arr[ind] && arr[ind-1] < arr[ind-2]);
        }
        else
        {
            return ind>low ? arr[ind] != arr[ind-1] : true;
        }
        return res;
    }
    
    int maxTurbulenceSize(vector<int>& A) {
        if(A.size() == 0 || A.size() == 1)
            return A.size();
        int i=0,j=0;
        int len = 1;
        while(j<A.size())
        {
            while(j<A.size() && isPosL(A,j,i))
            {
                len = std::max(len,j-i+1);
                j++;
            }
            if(i!=j-1)
                i = j-1;
            else
                i = j;
        }
        return len;
    }

 

public int maxTurbulenceSize(int[] A) {
        int l = 0;
        int r = 1;
        int maxLen = 1;
        long lastDiff = 0;
        while (r < A.length) {
            int newDiff = A[r] - A[r - 1];
            if (newDiff * lastDiff > 0) {
                l = r - 1;
            } else if (A[r] == A[r - 1]) {
                l = r;
            }
            maxLen = Math.max(maxLen, r - l + 1);
            lastDiff = newDiff;
            r++;
        }
        
        return maxLen;
    }
}

 

def maxTurbulenceSize(arr):
       start = 0
       max_length = 0
       for index in range(1, len(arr)):
           comp = cmp(arr[index-1], arr[index])
           if comp == 0:
               start = index
           elif index != len(arr) - 1 and comp*cmp(arr[index], arr[index + 1]) != -1:
               max_length = max(max_length, index + 1 - start)
               start = index
       return max(max_length, len(arr) - start)

 

Scroll to Top