Length of the longest ZigZag subarray of the given array

0 0 6 minutes read

Given an array arr[] containing n numbers, the task is to find the length of the longest ZigZag subarray such that every element in the subarray should be in form

a < b > c < d > e < f

Examples:

Input: arr[] = {12, 13, 1, 5, 4, 7, 8, 10, 10, 11}
Output: 6
Explanation:
The subarray is {12, 13, 1, 5, 4, 7} whose length is 6 and is in zigzag fashion.

Input: arr[] = {1, 2, 3, 4, 5}
Output: 2
Explanation:
The subarray is {1, 2} or {2, 3} or {4, 5} whose length is 2.

Approach: To solve the problem mentioned above following steps are followed:

Initially initialize cnt, a counter as 1.
Iterate among the array elements, check if elements are in form

a < b > c < d > e < f

If true Increase the cnt by 1. If it is not in form

a < b > c < d > e < f

then re-initialize cnt by 1.

Below is the implementation of the above approach:

C++

// C++ implementation to find
// the length of longest zigzag
// subarray of the given array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// longest zigZag contiguous subarray
int lenOfLongZigZagArr(int a[], int n)
{
 
    // 'max' to store the length
    // of longest zigZag subarray
    int max = 1,
 
        // 'len' to store the lengths
        // of longest zigZag subarray
        // at different instants of time
        len = 1;
 
    // Traverse the array from the beginning
    for (int i = 0; i < n - 1; i++) {
 
        if (i % 2 == 0
            && (a[i] < a[i + 1]))
            len++;
 
        else if (i % 2 == 1
                 && (a[i] > a[i + 1]))
            len++;
 
        else {
            // Check if 'max' length
            // is less than the length
            // of the current zigzag subarray.
            // If true, then update 'max'
            if (max < len)
                max = len;
 
            // Reset 'len' to 1
            // as from this element,
            // again the length of the
            // new zigzag subarray
            // is being calculated
            len = 1;
        }
    }
 
    // comparing the length of the last
    // zigzag subarray with 'max'
    if (max < len)
        max = len;
 
    // Return required maximum length
    return max;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << lenOfLongZigZagArr(arr, n);
 
    return 0;
}

Java

// Java implementation to find 
// the length of longest zigzag 
// subarray of the given array 
import java.io.*; 
import java.util.*; 
class GFG { 
     
// Function to find the length of 
// longest zigZag contiguous subarray 
static int lenOfLongZigZagArr(int a[], int n) 
{
    // 'max' to store the length 
    // of longest zigZag subarray 
    int max = 1, 
 
    // 'len' to store the lengths 
    // of longest zigZag subarray 
    // at different instants of time 
    len = 1; 
 
    // Traverse the array from the beginning 
    for (int i = 0; i < n - 1; i++) 
    { 
        if (i % 2 == 0 && (a[i] < a[i + 1])) 
            len++; 
     
        else if (i % 2 == 1 && (a[i] > a[i + 1])) 
            len++; 
     
        else
        { 
            // Check if 'max' length 
            // is less than the length 
            // of the current zigzag subarray. 
            // If true, then update 'max' 
            if (max < len) 
                max = len; 
     
            // Reset 'len' to 1 
            // as from this element, 
            // again the length of the 
            // new zigzag subarray 
            // is being calculated 
            len = 1; 
        } 
    } 
 
    // comparing the length of the last 
    // zigzag subarray with 'max' 
    if (max < len) 
        max = len; 
     
    // Return required maximum length 
    return max; 
}
 
// Driver Code
public static void main(String[] args) 
{ 
    int arr[] = { 1, 2, 3, 4, 5 }; 
    int n = arr.length; 
 
    System.out.println(lenOfLongZigZagArr(arr, n));
} 
}
 
// This code is contributed by coder001

Python3

# Python3 implementation to find the 
# length of longest zigzag subarray 
# of the given array 
 
# Function to find the length of 
# longest zigZag contiguous subarray 
def lenOfLongZigZagArr(a, n): 
 
    # '_max' to store the length 
    # of longest zigZag subarray 
    _max = 1
 
    # '_len' to store the lengths 
    # of longest zigZag subarray 
    # at different instants of time 
    _len = 1
 
    # Traverse the array from the beginning 
    for i in range(n - 1): 
 
        if i % 2 == 0 and a[i] < a[i + 1]: 
            _len += 1
 
        elif i % 2 == 1 and a[i] > a[i + 1]: 
            _len += 1
 
        else: 
             
            # Check if '_max' length is less than 
            # the length of the current zigzag 
            # subarray. If true, then update '_max' 
            if _max < _len: 
                _max = _len 
                 
            # Reset '_len' to 1 as from this element,
            # again the length of the new zigzag 
            # subarray is being calculated 
            _len = 1
     
    # Comparing the length of the last 
    # zigzag subarray with '_max' 
    if _max < _len: 
        _max = _len
         
    # Return required maximum length 
    return _max
 
# Driver code 
arr = [ 1, 2, 3, 4, 5 ]
n = len(arr) 
 
print(lenOfLongZigZagArr(arr, n))
     
# This code is contributed by divyamohan123

C#

// C# implementation to find 
// the length of longest zigzag 
// subarray of the given array 
using System;
 
class GFG{ 
     
// Function to find the length of 
// longest zigZag contiguous subarray 
static int lenOflongZigZagArr(int []a, int n) 
{
     
    // 'max' to store the length 
    // of longest zigZag subarray 
    int max = 1, 
 
    // 'len' to store the lengths 
    // of longest zigZag subarray 
    // at different instants of time 
    len = 1; 
 
    // Traverse the array from the beginning 
    for(int i = 0; i < n - 1; i++) 
    { 
       if (i % 2 == 0 && (a[i] < a[i + 1])) 
           len++;
            
       else if (i % 2 == 1 && (a[i] > a[i + 1])) 
           len++; 
            
       else
       { 
 
           // Check if 'max' length 
           // is less than the length 
           // of the current zigzag subarray. 
           // If true, then update 'max' 
           if (max < len) 
               max = len; 
            
           // Reset 'len' to 1 
           // as from this element, 
           // again the length of the 
           // new zigzag subarray 
           // is being calculated 
           len = 1; 
       } 
    } 
 
    // Comparing the length of the last 
    // zigzag subarray with 'max' 
    if (max < len) 
        max = len; 
     
    // Return required maximum length 
    return max; 
}
 
// Driver Code
public static void Main(String[] args) 
{ 
    int []arr = { 1, 2, 3, 4, 5 }; 
    int n = arr.Length; 
 
    Console.WriteLine(lenOflongZigZagArr(arr, n));
} 
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation to find
// the length of longest zigzag
// subarray of the given array
 
// Function to find the length of
// longest zigZag contiguous subarray
function lenOfLongZigZagArr( a, n)
{
 
    // 'max' to store the length
    // of longest zigZag subarray
    var max = 1,
 
    // 'len' to store the lengths
    // of longest zigZag subarray
    // at different instants of time
    len = 1;
 
    // Traverse the array from the beginning
    for (var i = 0; i < n - 1; i++) {
 
        if (i % 2 == 0
            && (a[i] < a[i + 1]))
            len++;
 
        else if (i % 2 == 1
                 && (a[i] > a[i + 1]))
            len++;
 
        else {
            // Check if 'max' length
            // is less than the length
            // of the current zigzag subarray.
            // If true, then update 'max'
            if (max < len)
                max = len;
 
            // Reset 'len' to 1
            // as from this element,
            // again the length of the
            // new zigzag subarray
            // is being calculated
            len = 1;
        }
    }
 
    // comparing the length of the last
    // zigzag subarray with 'max'
    if (max < len)
        max = len;
 
    // Return required maximum length
    return max;
}
 
// Driver code
var arr = [ 1, 2, 3, 4, 5 ];
var n = arr.length;
document.write( lenOfLongZigZagArr(arr, n));
 
</script>

Output:

Complexity Analysis :

Time Complexity – O(n), where n is the length of the array.

Auxiliary Space – O(1), no extra space required.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!