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 subarrayint 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 codeint 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 Codepublic 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 Codepublic 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 subarrayfunction 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 codevar arr = [ 1, 2, 3, 4, 5 ];var n = arr.length;document.write( lenOfLongZigZagArr(arr, n));</script> |
Output:
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!