The Weekly Challenge #396 - Finishing Order and Trionic Array

Task 1: Finishing Order

You are given two arrays of integers, @order and @friends. The @order array of size $N$ contains every integer from 1 to $N$ exactly once representing the race finishing order. The @friends contains friend IDs sorted in strictly increasing order. Write a script to return the array containing friend IDs in finishing order.

Method Explanation

To preserve the relative order in which friends crossed the finish line:

Convert @friends into a lookup set (or hash table in Perl) for $O(1)$ membership testing.
Iterate through @order sequentially from first place to last place.
Whenever a participant's ID is found in the friend set, append it to the result array.

This approach operates in optimal $O(N + M)$ time and $O(M)$ auxiliary space, where $N$ is the total number of participants and $M$ is the number of friends.

Perl Implementation

sub finishing_order ( $order, $friends ) {
    ( $order, $friends ) = $ARGS_CHECK->( $order, $friends );

    my %is_friend = map { $_ => 1 } @$friends;
    my @result;

    for my $id (@$order) {
        if ( exists $is_friend{$id} ) {
            push @result, $id;
        }
    }

    return \@result;
}

Python Implementation

def finishing_order(order: Sequence[int], friends: Sequence[int]) -> list[int]:
    """Return the list of friend IDs in race finishing order."""
    friends_set = set(friends)
    return [participant for participant in order if participant in friends_set]

Task 2: Trionic Array

You are given an array of integers. Write a script to return true if the given array is Trionic, otherwise return false.

An array is trionic if there exist indices 0 < p < q < n − 1 such that arr[0...p] is strictly increasing, arr[p...q] is strictly decreasing, and arr[q...n − 1] is strictly increasing.

Method Explanation

A trionic array must have at least 4 elements and transitions through exactly three consecutive strictly monotonic phases:

Phase 1 (Strictly Increasing): Start at index 0 and advance $i$ as long as $arr[i] < arr[i + 1]$. The stopping point is the first peak $p$. We must verify that $p > 0$ (there is at least one increasing step) and $p < n - 2$ (leaving room for at least one decreasing step and one subsequent increasing step).
Phase 2 (Strictly Decreasing): From peak $p$, advance $i$ as long as $arr[i] > arr[i + 1]$. The stopping point is the valley $q$. We must ensure $q > p$ (at least one decreasing step) and $q < n - 1$ (leaving room for the final increasing phase).
Phase 3 (Strictly Increasing): From valley $q$, advance $i$ as long as $arr[i] < arr[i + 1]$.
Finally, check whether the pointer $i$ reaches the end of the array ($i == n - 1$). If it does without encountering any plateau (equal values) or incorrect slopes, the array is trionic.

This scans the array in a single pass taking $O(N)$ time and $O(1)$ space.

Perl Implementation

sub is_trionic ($arr) {
    ($arr) = $INTS_CHECK->($arr);
    my $n = scalar @$arr;
    return 'false' if $n < 4;

    my $i = 0;

    # Phase 1: Strictly increasing up to peak p
    while ( $i + 1 < $n && $arr->[$i] < $arr->[ $i + 1 ] ) {
        $i++;
    }

    my $p = $i;
    return 'false' if $p == 0 || $p >= $n - 2;

    # Phase 2: Strictly decreasing down to valley q
    while ( $i + 1 < $n && $arr->[$i] > $arr->[ $i + 1 ] ) {
        $i++;
    }

    my $q = $i;
    return 'false' if $q == $p || $q >= $n - 1;

    # Phase 3: Strictly increasing to the end
    while ( $i + 1 < $n && $arr->[$i] < $arr->[ $i + 1 ] ) {
        $i++;
    }

    return $i == $n - 1 ? 'true' : 'false';
}

Python Implementation

def is_trionic(arr: Sequence[int]) -> bool:
    """Return True if array follows strictly increasing-decreasing-increasing pattern."""
    n = len(arr)
    if n < 4:
        return False

    i = 0

    # Phase 1: Strictly increasing to peak p
    while i + 1 < n and arr[i] < arr[i + 1]:
        i += 1

    p = i
    if p == 0 or p >= n - 2:
        return False

    # Phase 2: Strictly decreasing to valley q
    while i + 1 < n and arr[i] > arr[i + 1]:
        i += 1

    q = i
    if q == p or q >= n - 1:
        return False

    # Phase 3: Strictly increasing to end
    while i + 1 < n and arr[i] < arr[i + 1]:
        i += 1

    return i == n - 1