Longest alternating sub-array starting from every index in a Binary Array️‍🔥

Q: What is Longest alternating sub-array starting from every index in a Binary Array?

In this article, we will learn Longest alternating sub-array starting from every index in a Binary Array,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Given an array containing only 0s and 1s. For each index ‘i‘(0 index), find length of the longest alternating sub-array starting from ‘i‘ to ‘j‘ i.e., a_i..j for i <= j < n. Alternating sub-array means that any two adjacent elements should be different.

Example:

Input: arr[] = {1, 0, 1, 0, 0, 1}
Output: 4 3 2 1 2 1 
Explanation
Length for index '0': {1 0 1 0} => 4
Length for index '1': {0 1 0}   => 3
Length for index '2': {1 0}     => 2
Length for index '3': {0}       => 1
Length for index '4': {0 1}     => 2
Length for index '5': {1}       => 1

Simple approach is to iterate for every index by using two ‘for loops’ for finding the length of each index. The outer loop picks a starting point ‘i’ and the inner loop considers all sub-arrays starting from ‘i’. Time complexity of this approach is O(n²) which is not sufficient for large value of ‘n’.

Better approach is to use Dynamic programming. First of all, let’s see how to check for alternating sub-array. To check whether two elements are alternating or not, we can simply take XOR(Ex-OR) of both of them and then compare with ‘0’ and ‘1’.

If there XOR is ‘0’, that means both numbers are not alternating(equal elements).
If there XOR is ‘1’, that means both are alternating(different elements)

Let len[i] denotes length of an alternating sub-array starting at position ‘i’. If arr[i] and arr[i+1] have different values, then len[i] will be one more than len[i+1]. Otherwise if they are same elements, len[i] will be just 1.

Below is the implementation of above approach:

C++

// C++ program to calculate longest alternating 
// sub-array for each index elements 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to calculate alternating sub- 
// array for each index of array elements 
void alternateSubarray(bool arr[], int n) 
{ 
    int len[n]; 
  
    // Initialize the base state of len[] 
    len[n - 1] = 1; 
  
    // Calculating value for each element 
    for (int i = n - 2; i >= 0; --i) { 
        // If both elements are different 
        // then add 1 to next len[i+1] 
        if (arr[i] ^ arr[i + 1] == 1) 
            len[i] = len[i + 1] + 1; 
  
        // else initialize to 1 
        else
            len[i] = 1; 
    } 
  
    // Print lengths of binary subarrays. 
    for (int i = 0; i < n; ++i) 
        cout << len[i] << " "; 
} 
  
// Driver program 
int main() 
{ 
    bool arr[] = { 1, 0, 1, 0, 0, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    alternateSubarray(arr, n); 
    return 0; 
} 

Java

// Java program to calculate longest alternating 
// sub-array for each index elements 
import java.util.*; 
import java.io.*; 
  
class GFG { 
      
// Function to calculate alternating sub- 
// array for each index of array elements 
static void alternateSubarray(boolean arr[], int n)  
{ 
    int len[] = new int[n]; 
  
    // Initialize the base state of len[] 
    len[n - 1] = 1; 
  
    // Calculating value for each element 
    for (int i = n - 2; i >= 0; --i) { 
          
    // If both elements are different 
    // then add 1 to next len[i+1] 
    if (arr[i] ^ arr[i + 1] == true) 
        len[i] = len[i + 1] + 1; 
  
    // else initialize to 1 
    else
        len[i] = 1; 
    } 
  
    // Print lengths of binary subarrays. 
    for (int i = 0; i < n; ++i) 
    System.out.print(len[i] + " "); 
} 
  
// Driver code 
public static void main(String[] args)  
{ 
    boolean arr[] = {true, false, true, false, false, true}; 
    int n = arr.length; 
    alternateSubarray(arr, n); 
} 
} 
  
// This code is contributed by Anant Agarwal. 

Python3

# Python program to calculate 
# longest alternating 
# sub-array for each index elements 
  
# Function to calculate alternating sub- 
# array for each index of array elements 
def alternateSubarray(arr,n): 
  
    len=[] 
    for i in range(n+1): 
        len.append(0) 
          
    # Initialize the base state of len[] 
    len[n - 1] = 1
   
    # Calculating value for each element 
    for i in range(n - 2,-1,-1): 
          
        # If both elements are different 
        # then add 1 to next len[i+1] 
        if (arr[i] ^ arr[i + 1] == True): 
            len[i] = len[i + 1] + 1
   
        # else initialize to 1 
        else: 
            len[i] = 1
      
   
    # Print lengths of binary subarrays. 
    for i in range(n): 
        print(len[i] , " ",end="") 
   
# Driver code 
  
arr = [ True,False, True, False, False, True ] 
n = len(arr) 
  
alternateSubarray(arr, n) 
  
# This code is contributed 
# by Anant Agarwal. 

C#

// C# program to calculate longest  
// alternating sub-array for each  
// index elements 
using System; 
  
class GFG { 
      
    // Function to calculate alternating sub- 
    // array for each index of array elements 
    static void alternateSubarray(bool []arr, 
                                        int n)  
    { 
          
        int []len = new int[n]; 
      
        // Initialize the base state of len[] 
        len[n - 1] = 1; 
      
        // Calculating value for each element 
        for (int i = n - 2; i >= 0; --i) 
        { 
              
            // If both elements are different 
            // then add 1 to next len[i+1] 
            if (arr[i] ^ arr[i + 1] == true) 
                len[i] = len[i + 1] + 1; 
          
            // else initialize to 1 
            else
                len[i] = 1; 
        } 
      
        // Print lengths of binary subarrays. 
        for (int i = 0; i < n; ++i) 
            Console.Write(len[i] + " "); 
    } 
      
    // Driver code 
    public static void Main()  
    { 
        bool []arr = {true, false, true,  
                         false, false, true}; 
        int n = arr.Length; 
          
        alternateSubarray(arr, n); 
    } 
} 
  
// This code is contributed by vt_m. 

PHP

<?php  
// PHP program to calculate longest alternating 
// sub-array for each index elements 
  
// Function to calculate alternating sub- 
// array for each index of array elements 
function alternateSubarray(&$arr, $n) 
{ 
    $len = array_fill(0, $n, NULL); 
  
    // Initialize the base state of len[] 
    $len[$n - 1] = 1; 
  
    // Calculating value for each element 
    for ($i = $n - 2; $i >= 0; --$i) 
    { 
        // If both elements are different 
        // then add 1 to next len[i+1] 
        if ($arr[$i] ^ $arr[$i + 1] == 1) 
            $len[$i] = $len[$i + 1] + 1; 
  
        // else initialize to 1 
        else
            $len[$i] = 1; 
    } 
  
    // Print lengths of binary subarrays. 
    for ($i = 0; $i < $n; ++$i) 
        echo $len[$i] . " "; 
} 
  
// Driver Code 
$arr = array(1, 0, 1, 0, 0, 1); 
$n = sizeof($arr); 
alternateSubarray($arr, $n); 
  
// This code is contributed by ita_c 
?> 

Javascript

<script> 
// JavaScript program to calculate longest alternating  
// sub-array for each index elements  
  
// Function to calculate alternating sub-  
// array for each index of array elements  
function alternateSubarray(arr, n)  
{  
    let len = new Array(n);  
  
    // Initialize the base state of len[]  
    len[n - 1] = 1;  
  
    // Calculating value for each element  
    for (let i = n - 2; i >= 0; --i)  
    { 
      
        // If both elements are different  
        // then add 1 to next len[i+1]  
        if (arr[i] ^ arr[i + 1] == 1)  
            len[i] = len[i + 1] + 1;  
  
        // else initialize to 1  
        else
            len[i] = 1;  
    }  
  
    // Print lengths of binary subarrays.  
    for (let i = 0; i < n; ++i)  
        document.write(len[i] + " ");  
}  
  
// Driver program  
    let arr = [ 1, 0, 1, 0, 0, 1 ];  
    let n = arr.length;  
    alternateSubarray(arr, n);  
  
  
// This code is contributed by Surbhi Tyagi. 
</script>

Output

4 3 2 1 2 1

Time complexity: O(n)
Auxiliary space: O(n)

Another Efficient approach is, instead of storing all the sub-array elements in len[] array, we can directly print it until mismatch(equal adjacent elements) is found. When a mismatch is found, we print count from current value to 0.

Implementation:

C++

// C++ program to calculate longest alternating 
// sub-array for each index elements 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to calculate alternating sub-array 
// for each index of array elements 
void alternateSubarray(bool arr[], int n) 
{ 
    // Initialize count variable for storing 
    // length of sub-array 
    int count = 1; 
  
    // Initialize 'prev' variable which 
    // indicates the previous element 
    // while traversing for index 'i' 
    int prev = arr[0]; 
    for (int i = 1; i < n; ++i) { 
  
        // If both elements are same 
        // print elements because alternate 
        // element is not found for current 
        // index 
        if ((arr[i] ^ prev) == 0) 
        { 
            // print count and decrement it. 
            while (count) 
                cout << count-- << " "; 
        } 
  
        // Increment count for next element 
        ++count; 
  
        // Re-initialize previous variable 
        prev = arr[i]; 
    } 
  
    // If elements are still available after 
    // traversing whole array, print it 
    while (count) 
        cout << count-- << " "; 
} 
  
// Driver program 
int main() 
{ 
    bool arr[] = { 1, 0, 1, 0, 0, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    alternateSubarray(arr, n); 
    return 0; 
} 

Java

// Java program to calculate longest alternating 
// sub-array for each index elements 
import java.io.*; 
import java.util.*; 
  
class GFG { 
  
    // Function to calculate alternating sub-array 
    // for each index of array elements 
    static void alternateSubarray(boolean arr[], int n) 
    { 
        // Initialize count variable for storing 
        // length of sub-array 
        int count = 1; 
  
        // Initialize 'prev' variable which 
        // indicates the previous element 
        // while traversing for index 'i' 
        boolean prev = arr[0]; 
        for (int i = 1; i < n; ++i) { 
  
            // If both elements are same 
            // print elements because alternate 
            // element is not found for current 
            // index 
            if ((arr[i] ^ prev) == false) { 
                // print count and decrement it. 
                while (count > 0) { 
                    System.out.print(count-- + " "); 
                } 
            } 
  
            // Increment count for next element 
            ++count; 
  
            // Re-initialize previous variable 
            prev = arr[i]; 
        } 
  
        // If elements are still available after 
        // traversing whole array, print it 
        while (count != 0) { 
            System.out.print(count-- + " "); 
        } 
    } 
  
    // Driver program 
    public static void main(String args[]) 
    { 
        boolean arr[] 
            = { true, false, true, false, false, true }; 
        int n = arr.length; 
        alternateSubarray(arr, n); 
    } 
} 
/*This code is contributed by 29AjayKumar*/

Python3

# Python 3 program to calculate longest  
# alternating sub-array for each index elements 
  
# Function to calculate alternating sub-array 
# for each index of array elements 
def alternateSubarray(arr, n): 
      
    # Initialize count variable for  
    # storing length of sub-array 
    count = 1
  
    # Initialize 'prev' variable which 
    # indicates the previous element 
    # while traversing for index 'i' 
    prev = arr[0] 
    for i in range(1, n): 
          
        # If both elements are same, print  
        # elements because alternate element  
        # is not found for current index 
        if ((arr[i] ^ prev) == 0): 
              
            # print count and decrement it. 
            while (count): 
                print(count, end = " ") 
                count -= 1
  
        # Increment count for next element 
        count += 1
  
        # Re-initialize previous variable 
        prev = arr[i] 
  
    # If elements are still available after 
    # traversing whole array, print it 
    while (count): 
        print(count, end = " ") 
        count -= 1
  
# Driver Code 
if __name__ == '__main__': 
    arr = [1, 0, 1, 0, 0, 1] 
    n = len(arr) 
    alternateSubarray(arr, n) 
  
# This code is contributed by 
# Surendra_Gangwar 

C#

// C# program to calculate longest alternating 
// sub-array for each index elements  
using System;  
   
public class Test{ 
      
// Function to calculate alternating sub-array 
// for each index of array elements 
    static void alternateSubarray(bool []arr, int n) { 
        // Initialize count variable for storing 
        // length of sub-array 
        int count = 1; 
   
        // Initialize 'prev' variable which 
        // indicates the previous element 
        // while traversing for index 'i' 
        bool prev = arr[0]; 
        for (int i = 1; i < n; ++i) { 
   
            // If both elements are same 
            // print elements because alternate 
            // element is not found for current 
            // index 
            if ((arr[i] ^ prev) == false) { 
                // print count and decrement it. 
                while (count > 0) { 
                    Console.Write(count-- + " "); 
                } 
            } 
   
            // Increment count for next element 
            ++count; 
   
            // Re-initialize previous variable 
            prev = arr[i]; 
        } 
   
        // If elements are still available after 
        // traversing whole array, print it 
        while (count != 0) { 
            Console.Write(count-- + " "); 
        } 
    } 
   
// Driver program 
    public static void Main() { 
        bool []arr = {true, false, true, false, false, true}; 
        int n = arr.Length; 
        alternateSubarray(arr, n); 
    } 
} 
/*This code is contributed by 29AjayKumar*/

PHP

<?php 
// PHP program to calculate longest alternating 
// sub-array for each index elements 
  
// Function to calculate alternating sub-array 
// for each index of array elements 
function alternateSubarray($arr, $n) 
{ 
      
    // Initialize count variable for storing 
    // length of sub-array 
    $count = 1; 
  
    // Initialize 'prev' variable which 
    // indicates the previous element 
    // while traversing for index 'i' 
    $prev = $arr[0]; 
    for ($i = 1; $i < $n; ++$i) 
    { 
  
        // If both elements are same 
        // print elements because alternate 
        // element is not found for current 
        // index 
        if (($arr[$i] ^ $prev) == 0) 
        { 
            // print count and decrement it. 
            while ($count) 
                echo $count-- , " "; 
        } 
  
        // Increment count for next element 
        ++$count; 
  
        // Re-initialize previous variable 
        $prev = $arr[$i]; 
    } 
  
    // If elements are still available after 
    // traversing whole array, print it 
    while ($count) 
        echo $count-- , " "; 
} 
  
    // Driver Code 
    $arr = array(1, 0, 1, 0, 0, 1); 
    $n = sizeof($arr) ; 
    alternateSubarray($arr, $n); 
      
// This code is contributed by jit_t. 
?> 

Javascript

<script> 
  
// Javascript program to calculate longest 
// alternating sub-array for each index elements 
  
// Function to calculate alternating sub-array 
// for each index of array elements 
function alternateSubarray(arr, n) 
{ 
      
    // Initialize count variable for storing 
    // length of sub-array 
    let count = 1; 
  
    // Initialize 'prev' variable which 
    // indicates the previous element 
    // while traversing for index 'i' 
    let prev = arr[0]; 
      
    for(let i = 1; i < n; ++i)  
    { 
          
        // If both elements are same 
        // print elements because alternate 
        // element is not found for current 
        // index 
        if ((arr[i] ^ prev) == false) 
        { 
              
            // Print count and decrement it. 
            while (count > 0)  
            { 
                document.write(count-- + " "); 
            } 
        } 
  
        // Increment count for next element 
        ++count; 
  
        // Re-initialize previous variable 
        prev = arr[i]; 
    } 
  
    // If elements are still available after 
    // traversing whole array, print it 
    while (count != 0) 
    { 
        document.write(count-- + " "); 
    } 
} 
  
// Driver code 
let arr = [ true, false, true, false, false, true ]; 
let n = arr.length; 
  
alternateSubarray(arr, n); 
  
// This code is contributed by suresh07 
  
</script>

Output

4 3 2 1 2 1

Time complexity: O(n)
Auxiliary space: O(1)