Task 1: Consecutive Sequence
You are given an unsorted array of integers. Write a script to return the length of the longest consecutive elements sequence. Return -1 if there is no sequence of length greater than 1.
Method Explanation
A naive sorting approach takes $O(N \log N)$ time. However, we can solve this problem in optimal $O(N)$ linear time using a Hash Set:
- Store all elements in a set (or hash table in Perl) for $O(1)$ average-time lookups.
- Iterate through each number in the array:
- Check if
num - 1exists in the set. If it does,numis not the start of a consecutive sequence, so we skip it to prevent redundant checks. - If
num - 1does not exist,numis the starting boundary of a consecutive sequence. We iteratecurrent_num + 1as long as consecutive numbers exist in the set, counting the length of the sequence.
- Check if
- Track the maximum sequence length found. Return that length if it is greater than 1, otherwise return
-1.
Perl Implementation
sub longest_consecutive_sequence ($ints) {
($ints) = $INTS_CHECK->($ints);
my %nums = map { $_ => 1 } @$ints;
my $max_length = 0;
for my $num (@$ints) {
if ( !exists $nums{ $num - 1 } ) {
my $current_num = $num;
my $current_length = 1;
while ( exists $nums{ $current_num + 1 } ) {
$current_num++;
$current_length++;
}
$max_length = $current_length if $current_length > $max_length;
}
}
return $max_length > 1 ? $max_length : -1;
}
Python Implementation
def longest_consecutive_sequence(ints: Sequence[int]) -> int:
"""Find the length of the longest consecutive sequence; return -1 if <= 1."""
nums = set(ints)
max_length = 0
for num in ints:
if num - 1 not in nums:
current_num = num
current_length = 1
while current_num + 1 in nums:
current_num += 1
current_length += 1
if current_length > max_length:
max_length = current_length
return max_length if max_length > 1 else -1
Task 2: Next Permutation
You are given an array of integers. Write a script to rearrange the numbers into the lexicographically next greater permutation. If no greater permutation is possible, rearrange them into the lowest possible order (sorted ascending).
Method Explanation
The standard algorithm (originating from Narayana Pandita in the 14th century) generates the lexicographically next permutation in $O(N)$ time and $O(1)$ extra space:
- Find the pivot: Scan backwards from the right to find the largest index $i$ such that $a[i] < a[i + 1]$. If no such index exists (the whole array is descending), the permutation is already the last one, so reverse / sort the whole array ascending and return.
- Find the successor: Scan backwards from the right to find the largest index $j > i$ such that $a[j] > a[i]$.
- Swap: Swap elements at index $i$ and $j$.
- Reverse suffix: Reverse the sub-array from index $i + 1$ to the end of the array to obtain the smallest possible ordering for the remaining suffix.
Perl Implementation
sub next_permutation ($ints_ref) {
($ints_ref) = $INTS_CHECK->($ints_ref);
my @ints = @$ints_ref;
my $n = scalar @ints;
return \@ints if $n <= 1;
my $i = $n - 2;
while ( $i >= 0 && $ints[$i] >= $ints[ $i + 1 ] ) {
$i--;
}
if ( $i < 0 ) {
@ints = sort { $a <=> $b } @ints;
return \@ints;
}
my $j = $n - 1;
while ( $ints[$j] <= $ints[$i] ) {
$j--;
}
( $ints[$i], $ints[$j] ) = ( $ints[$j], $ints[$i] );
my @suffix = reverse @ints[ $i + 1 .. $n - 1 ];
splice @ints, $i + 1, $n - ( $i + 1 ), @suffix;
return \@ints;
}
Python Implementation
def next_permutation(ints: list[int]) -> list[int]:
"""Rearrange numbers into lexicographically next greater permutation in place."""
n = len(ints)
if n <= 1:
return ints
i = n - 2
while i >= 0 and ints[i] >= ints[i + 1]:
i -= 1
if i < 0:
return sorted(ints)
j = n - 1
while ints[j] <= ints[i]:
j -= 1
ints[i], ints[j] = ints[j], ints[i]
ints[i + 1 :] = reversed(ints[i + 1 :])
return ints