The Weekly Challenge #297

Contiguous Array • Semi-Ordered Permutation
Official Challenge • My Solutions on GitHub

Task 1: Contiguous Array

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

Method Explanation

A naive check of every subarray takes $O(N^2)$ time. We can achieve linear $O(N)$ time by transforming the problem into a prefix sum search:

  • Treat every 0 as -1 and every 1 as +1.
  • An equal number of 0s and 1s in a subarray means the sum of that subarray is 0.
  • Track the running cumulative sum. If a cumulative sum repeats at indices $i$ and $j$ ($i < j$), the subarray between $i+1$ and $j$ has a net sum of 0 (equal zeros and ones).
  • Using a hash map to record the first time each cumulative sum is encountered allows us to immediately calculate the maximum span for each recurring sum.

Perl Implementation

sub find_max_length ($binary) {
    ($binary) = $ARRAY_CHECK->($binary);
    return 0 if !@$binary;

    my %sum_indices;
    my $max_length     = 0;
    my $cumulative_sum = 0;

    for my $i ( 0 .. $#$binary ) {
        my $val = $binary->[$i];
        die 'Binary array must contain only 0 and 1' if $val != 0 && $val != 1;
        $cumulative_sum += ( $val == 0 ? -1 : 1 );

        if ( $cumulative_sum == 0 ) {
            $max_length = $i + 1;
        }
        elsif ( exists $sum_indices{$cumulative_sum} ) {
            my $length = $i - $sum_indices{$cumulative_sum};
            $max_length = $length if $length > $max_length;
        }
        else {
            $sum_indices{$cumulative_sum} = $i;
        }
    }

    return $max_length;
}

Python Implementation

def find_max_length(binary: Sequence[int]) -> int:
    """Find the maximum length of a contiguous subarray with equal numbers of 0 and 1."""
    sum_indices: dict[int, int] = {}
    max_length = 0
    cumulative_sum = 0

    for i, val in enumerate(binary):
        if val not in (0, 1):
            raise ValueError("Binary array must contain only 0 and 1")
        cumulative_sum += -1 if val == 0 else 1

        if cumulative_sum == 0:
            max_length = i + 1
        elif cumulative_sum in sum_indices:
            length = i - sum_indices[cumulative_sum]
            if length > max_length:
                max_length = length
        else:
            sum_indices[cumulative_sum] = i

    return max_length

Task 2: Semi-Ordered Permutation

You are given a 0-indexed permutation of n integers nums. A permutation is called semi-ordered if the first number equals 1 and the last number equals n. You can make the permutation semi-ordered using adjacent swaps. Return the minimum number of adjacent swaps.

Method Explanation

To move 1 to index 0 using only adjacent swaps, it takes exactly pos1 swaps, where pos1 is the current index of 1.

Similarly, to move n to index n - 1, it takes (n - 1) - posn swaps.

If pos1 < posn, the paths of moving 1 to the left and n to the right never cross each other, so the total moves are simply:

pos1 + (n - 1 - posn)
If pos1 > posn, their paths cross, meaning one swap will simultaneously move 1 one step left and n one step right. Thus, we save 1 swap:
pos1 + (n - 1 - posn) - 1

Perl Implementation

sub minimum_swaps ($ints) {
    ($ints) = $INTS_CHECK->($ints);
    my $n = scalar @$ints;
    return 0 if $n <= 1;

    my ( $pos1, $posn );
    for my $i ( 0 .. $#$ints ) {
        $pos1 = $i if $ints->[$i] == 1;
        $posn = $i if $ints->[$i] == $n;
    }

    die 'Permutation must contain 1 and n' if !defined $pos1 || !defined $posn;

    if ( $pos1 < $posn ) {
        return $pos1 + ( $n - 1 - $posn );
    }
    else {
        return $pos1 + ( $n - 1 - $posn ) - 1;
    }
}

Python Implementation

def minimum_swaps(ints: Sequence[int]) -> int:
    """Calculate the minimum number of adjacent swaps to make the permutation semi-ordered."""
    n = len(ints)
    if n <= 1:
        return 0

    pos1 = ints.index(1)
    posn = ints.index(n)

    if pos1 < posn:
        return pos1 + (n - 1 - posn)
    return pos1 + (n - 1 - posn) - 1