Task — Contiguous array

You are given an array of binary numbers, @binary. Write a script to return the maximum length of a contiguous subarray with an equal number of 0s and 1s.

Examples

Example 1
Input: @binary = (1, 0)
Output: 2
(1, 0) is the longest contiguous subarray with an equal
   number of 0 and 1.

Example 2
Input: @binary = (0, 1, 0)
Output: 2
(1, 0) or (0, 1) is the longest contiguous subarray with
   an equal number of 0 and 1.

Example 3
Input: @binary = (0, 0, 0, 0, 0)
Output: 0

Example 4
Input: @binary = (0, 1, 0, 0, 1, 0)
Output: 4

Analysis

A few minutes thought did not yield a better algorithm than something based on two nested loops such as:

for $start (0 .. $#binary - 1) {
   for $end ($start + 1 .. $#binary) {
      ... check to see if $start to $end is the 
      ... longest qualifying sub-array
   }
}

The first improvement we can make is to note that the answer must be an array with an even number of elements. So we can halve the number of iterations in the inner loop:

   for ($end = $start + 1; $end <= $#binary; $end += 2)

The next improvement is to note that while we are counting the number of 0s and 1s in the sub-array $start .. $end we can stop as soon as either count exceeds the number of array elemets we are yet to examine.

So for example, if the sub-array is 1, 1, 1, 1, 0, 0, 0, when we get to the fourth 1 we can stop, because there are only 3 more elements so there can't be 4 more 0s.

The next change I made probably does not improve the efficiency but perhaps makes the code easier to understand. It is that I don't count 1s and 0s separately, but maintain a sum to which I add 1 if I encounter a 1 and subtract 1 if it's a 0. That means that I only need to check whether $sum == 0 to determine whether we have equal numbers of 0s and 1s.

My solution runs in under a second for 1000 random 0s and 1s, and takes about 22 seconds for 10 000 (on a slowish Raspberry Pi), and I think that's probably good enough.

Try it 

Try running the script with any input:

Your @binary =

example: 1, 0, 1, 0, 1, 0, 1

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-11-25
use utf8;     # Week 297 - task 1 - Contiguous array
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

contiguous_array(1, 0, 1, 0, 0, 0, 1, 1);
contiguous_array(1, 1, 1, 0, 1, 1, 1, 0, 1);
contiguous_array(1, 1, 1, 1, 1);
contiguous_array(1, 0, 1, 0, 1, 0, 1, 0, 1);
contiguous_array(1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1);
contiguous_array(1, 0, 0);
contiguous_array(1, 1, 1, 1, 1, 0, 0, 0, 0, 0);

my @ints;
push @ints, int(rand(2)) for 0 .. 200;
contiguous_array(@ints);

sub contiguous_array {
    
    my (@binary, $longest, $start, $sum, $end, $length, $location);
    
    # initialise
    @binary = @_;
    $longest = 0;
    
    # loop over starting element
    START: for $start (0 .. $#binary - 1) {
        $sum = 0;
        
        # loop over ending element
        for ($end = $start + 1; $end <= $#binary; $end += 2) {
            $sum += ($binary[$end - 1] ? -1 : 1) + ($binary[$end] ? -1 : 1);
            
            # give up on this start if no hope
            next START if $sum > $end - $start + 1;
            
            # save result if best-so-far equal numbers of 0s and 1s
            if ($sum == 0) {
                $length = $end - $start + 1;
                if ($length > $longest) {
                    $longest = $length;
                    $location = qq[$start to $end];
                }
            }
        }
    }

    # report
    say qq[\nInput:  \@binary = (] . join(', ', @binary) . ')';
    say qq[Output: $longest] . ($location ? qq[ ($location)] : '');
}

Output

Input:  @binary = (1, 0, 1, 0, 0, 0, 1, 1)
Output: 8 (0 to 7)

Input:  @binary = (1, 1, 1, 0, 1, 1, 1, 0, 1)
Output: 2 (2 to 3)

Input:  @binary = (1, 1, 1, 1, 1)
Output: 0

Input:  @binary = (1, 0, 1, 0, 1, 0, 1, 0, 1)
Output: 8 (0 to 7)

Input:  @binary = (1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1)
Output: 10 (0 to 9)

Input:  @binary = (1, 0, 0)
Output: 2 (0 to 1)

Input:  @binary = (1, 1, 1, 1, 1, 0, 0, 0, 0, 0)
Output: 10 (0 to 9)

Input:  @binary = (1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1,
1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1,
1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0,
0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0,
0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1,
0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1,
1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,
1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1,
0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1,
1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0)
Output: 164 (13 to 176)