The Weekly Challenge 284

Lucky Integer & Relative Sort: Frequency Counting and Custom Ordering in Perl & Python

Lubos Kolouch August 25, 2024 Challenge Details GitHub Solutions

Task 1: Lucky Integer

You are given an array of integers, @ints.

Write a script to find the lucky integer if found, otherwise return -1. If there are more than one then return the largest.

A lucky integer is an integer that has a frequency in the array equal to its value.

Example 1: Input: @ints = (2, 2, 3, 4) → Output: 2

Example 2: Input: @ints = (1, 2, 2, 3, 3, 3) → Output: 3

Example 3: Input: @ints = (1, 1, 1, 3) → Output: -1

Method Explanation

Finding the lucky integer is a classic frequency-counting problem that can be solved in $O(N)$ time and $O(U)$ space (where $U$ is the number of unique integers in the input array):

  • First, iterate through the input array and build a frequency map (hash table / dictionary) mapping each integer $x$ to its occurrence count $f(x)$.
  • Filter the distinct keys to find all integers satisfying $x = f(x)$.
  • If one or more lucky integers exist, return their maximum value; otherwise return $-1$.

Perl Solution

use v5.38;
use warnings;
use List::Util qw(max);
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for find_lucky_integer => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub find_lucky_integer ($ints_ref) {
    my %freq;

    for my $num (@$ints_ref) {
        $freq{$num}++;
    }

    my @lucky_integers;
    for my $num ( keys %freq ) {
        if ( $num == $freq{$num} ) {
            push @lucky_integers, int($num);
        }
    }

    if (@lucky_integers) {
        return max(@lucky_integers);
    }
    return -1;
}

Python Solution

from collections import Counter

def find_lucky_integer(ints: list[int]) -> int:
    """Find the lucky integer in the given list of integers."""
    freq = Counter(ints)
    lucky_integers = [num for num, count in freq.items() if num == count]
    if lucky_integers:
        return max(lucky_integers)
    return -1

Task 2: Relative Sort

You are given two lists of integers, @list1 and @list2. The elements in @list2 are distinct and also in @list1.

Write a script to sort the elements in @list1 such that the relative order of items in @list1 is the same as in @list2. Elements that are missing in @list2 should be placed at the end of @list1 in ascending order.

Example 1: Input: @list1 = (2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5), @list2 = (2, 1, 4, 3, 5, 6) → Output: (2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)

Example 2: Input: @list1 = (3, 3, 4, 6, 2, 4, 2, 1, 3), @list2 = (1, 3, 2) → Output: (1, 3, 3, 3, 2, 2, 4, 4, 6)

Example 3: Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1), @list2 = (1, 0, 3, 2) → Output: (1, 1, 1, 0, 0, 3, 2, 4, 5)

Method Explanation

To sort @list1 according to the custom priority order defined by @list2:

  • Build an index lookup hash order mapping each element $y \in \text{list2}$ to its $0$-based position index in @list2.
  • Partition the elements of @list1 into two buckets: in_list2 (elements present in order) and not_in_list2 (elements absent from order).
  • Sort in_list2 by comparing their lookup rank $\text{order}[x]$, and sort not_in_list2 in natural ascending numerical order.
  • Concatenate both sorted sublists to produce the final array.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for relative_sort => (
    method     => 0,
    positional => [ ArrayRef [Int], ArrayRef [Int] ],
);

sub relative_sort ( $list1_ref, $list2_ref ) {
    my %order;

    my $idx = 0;
    for my $num (@$list2_ref) {
        $order{$num} = $idx++;
    }

    my @in_list2;
    my @not_in_list2;

    for my $num (@$list1_ref) {
        if ( exists $order{$num} ) {
            push @in_list2, $num;
        }
        else {
            push @not_in_list2, $num;
        }
    }

    @in_list2     = sort { $order{$a} <=> $order{$b} || $a <=> $b } @in_list2;
    @not_in_list2 = sort { $a <=> $b } @not_in_list2;

    my @result = ( @in_list2, @not_in_list2 );
    return \@result;
}

Python Solution

def relative_sort(list1: list[int], list2: list[int]) -> list[int]:
    """Sort the elements of list1 based on the relative order defined in list2."""
    order: dict[int, int] = {num: idx for idx, num in enumerate(list2)}
    in_list2: list[int] = []
    not_in_list2: list[int] = []

    for num in list1:
        if num in order:
            in_list2.append(num)
        else:
            not_in_list2.append(num)

    in_list2.sort(key=lambda x: (order[x], x))
    not_in_list2.sort()

    return in_list2 + not_in_list2