The Weekly Challenge 073

Min Sliding Window and Smallest Neighbour

Solutions on GitHub

Task 1: Min Sliding Window

You are given an array of integers @A and sliding window size $S. Write a script to create an array of min from each sliding window.

Example Output

Input: @A = (1, 5, 0, 2, 9, 3, 7, 6, 4, 8), $S = 3 Output: 0, 0, 0, 2, 3, 3, 4, 4 Input: @A = (1, 2, 3), $S = 4 Output: 1

Logic

Slide a window of size $S across the array from index 0 up to length(A) - S. At each position, take the slice and find its minimum. If $S >= length(A), the result is simply the minimum of the entire array.

Perl Solution

ch-1.pl

sub min_window ( $arr, $s ) { return [] if !@$arr || $s <= 0; return [ min(@$arr) ] if $s >= scalar(@$arr); my @return_array; for my $i ( 0 .. scalar(@$arr) - $s ) { push @return_array, min( @$arr[ $i .. $i + $s - 1 ] ); } return \@return_array; }

Python Solution

ch-1.py

def min_window(arr: list[int], s: int) -> list[int]: """Calculate the minimum value for each sliding window of size s.""" if not arr or s <= 0: return [] if s >= len(arr): return [min(arr)] return [min(arr[i : i + s]) for i in range(len(arr) - s + 1)]

Task 2: Smallest Neighbour

You are given an array of integers @A. Write a script to create an array that represents the smallest element to the left of each corresponding index. If none found, then use 0.

Example Output

Input: @A = (7, 8, 3, 12, 10) Output: 0, 7, 0, 3, 3 Input: @A = (4, 6, 5) Output: 0, 4, 4

Logic

Maintain a running minimum of all elements seen so far to the left. For the first element, output 0. For each subsequent element A[i], if the running minimum is strictly less than A[i], append the running minimum; otherwise, append 0. Then update the running minimum with A[i] if A[i] is smaller.

Perl Solution

ch-2.pl

sub get_smallest ($arr) { return [] if !@$arr; my @return_array = (0); my $min = $arr->[0]; for my $i ( 1 .. $#$arr ) { if ( $min < $arr->[$i] ) { push @return_array, $min; } else { push @return_array, 0; } $min = $arr->[$i] if $arr->[$i] < $min; } return \@return_array; }

Python Solution

ch-2.py

def get_smallest(arr: list[int]) -> list[int]: """Return smallest element to the left of each index, or 0 if none is smaller.""" if not arr: return [] result: list[int] = [0] current_min = arr[0] for x in arr[1:]: if current_min < x: result.append(current_min) else: result.append(0) if x < current_min: current_min = x return result