The Weekly Challenge 263

Target Index & Merge Items: Sorted Element Indexing and Key-Value Aggregation in Perl & Python

Lubos Kolouch March 31, 2024 Challenge Details GitHub Solutions

Task 1: Target Index

You are given an array of integers, @ints, and a target element $k.

Write a script to return the list of indices in the sorted array where the element is the same as the given target element.

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

Example 2: Input: @ints = (1, 2, 4, 3, 5), $k = 6 → Output: ()

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

Method Explanation

To find the 0-based indices where the target integer $k appears in the sorted version of @ints:

  1. Sort the input array in ascending numerical order.
  2. Filter the indices 0 .. N-1 to retain only those positions where the sorted value equals $k.

Sorting takes $O(N \log N)$ time and scanning for matching indices takes $O(N)$ time, giving an overall $O(N \log N)$ time complexity and $O(N)$ auxiliary space.

Perl Solution

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

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

sub find_target_indices ( $ints, $k ) {
    my @sorted = sort { $a <=> $b } @$ints;
    my @target_indices = grep { $sorted[$_] == $k } 0 .. $#sorted;
    return \@target_indices;
}

Python Solution

def find_target_indices(ints: list[int], k: int) -> list[int]:
    """Return the indices in the sorted array where the element equals k."""
    sorted_ints = sorted(ints)
    return [i for i, val in enumerate(sorted_ints) if val == k]

Task 2: Merge Items

You are given two 2-D arrays of positive integers, $items1 and $items2, where each element is a pair of (item_id, item_quantity).

Write a script to return the merged items.

Example 1: Input: $items1 = [ [1,1], [2,1], [3,2] ], $items2 = [ [2,2], [1,3] ] → Output: [ [1,4], [2,3], [3,2] ]

Example 2: Input: $items1 = [ [1,2], [2,3], [1,3], [3,2] ], $items2 = [ [3,1], [1,3] ] → Output: [ [1,8], [2,3], [3,3] ]

Example 3: Input: $items1 = [ [1,1], [2,2], [3,3] ], $items2 = [ [2,3], [2,4] ] → Output: [ [1,1], [2,9], [3,3] ]

Method Explanation

Each 2-D array contains pairs of [item_id, quantity], and note from Example 2 and Example 3 that the same item_id can appear multiple times even within a single input list.

  1. Iterate over all pairs across both $items1 and $items2, accumulating the sum of quantities for each item_id in a hash map / dictionary.
  2. Sort the unique item_id keys numerically in ascending order and construct the resulting list of [item_id, total_quantity] pairs.

This takes $O((N + M) + U \log U)$ time where $N, M$ are the lengths of the input lists and $U$ is the number of unique item IDs.

Perl Solution

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

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

sub merge_items ( $items1, $items2 ) {
    my %merged;
    for my $item ( @$items1, @$items2 ) {
        my ( $item_id, $quantity ) = @$item;
        $merged{$item_id} += $quantity;
    }
    return [ map { [ int($_), $merged{$_} ] } sort { $a <=> $b } keys %merged ];
}

Python Solution

def merge_items(
    items1: list[list[int]], items2: list[list[int]]
) -> list[list[int]]:
    """Merge two 2-D arrays of [item_id, quantity] pairs sorted by item_id."""
    merged: dict[int, int] = {}
    for item_id, quantity in items1 + items2:
        merged[item_id] = merged.get(item_id, 0) + quantity
    return [[item_id, quantity] for item_id, quantity in sorted(merged.items())]