The Weekly Challenge #294

Consecutive Sequence • Next Permutation
Official Challenge • My Solutions on GitHub

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 - 1 exists in the set. If it does, num is not the start of a consecutive sequence, so we skip it to prevent redundant checks.
    • If num - 1 does not exist, num is the starting boundary of a consecutive sequence. We iterate current_num + 1 as long as consecutive numbers exist in the set, counting the length of the sequence.
  • 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:

  1. 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.
  2. Find the successor: Scan backwards from the right to find the largest index $j > i$ such that $a[j] > a[i]$.
  3. Swap: Swap elements at index $i$ and $j$.
  4. 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