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
0as-1and every1as+1. - An equal number of
0s and1s in a subarray means the sum of that subarray is0. - 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