The Weekly Challenge 071

Peak Elements and Trim Linked List

Solutions on GitHub

Task 1: Peak Elements

Write a script that prints all the peak elements in the given array. A peak element is an element that is greater than its neighbours.

Example Output

Input: [18, 45, 38, 25, 10, 7, 21, 6, 28, 48] Output: [45, 21, 48] Input: [47, 11, 32, 8, 1, 9, 39, 14, 36, 23] Output: [47, 32, 39, 36]

Logic

Check the boundaries separately: the first element is a peak if it is strictly greater than the second, and the last element is a peak if it is strictly greater than the penultimate. For elements in between (indices 1 to $n-2), check if the current element is greater than both its left and right neighbours.

Perl Solution

ch-1.pl

sub find_peaks (@arr) { my $n = scalar @arr; return [] if $n == 0; return [ $arr[0] ] if $n == 1; my @peaks; push @peaks, $arr[0] if $arr[0] > $arr[1]; for my $i ( 1 .. $n - 2 ) { push @peaks, $arr[$i] if $arr[$i] > $arr[ $i - 1 ] && $arr[$i] > $arr[ $i + 1 ]; } push @peaks, $arr[-1] if $arr[-1] > $arr[-2]; return \@peaks; }

Python Solution

ch-1.py

def find_peaks(arr: list[int]) -> list[int]: """Find all peak elements in the array.""" n = len(arr) if n == 0: return [] if n == 1: return [arr[0]] peaks: list[int] = [] # First element if arr[0] > arr[1]: peaks.append(arr[0]) # Middle elements for i in range(1, n - 1): if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]: peaks.append(arr[i]) # Last element if arr[-1] > arr[-2]: peaks.append(arr[-1]) return peaks

Task 2: Trim Linked List

You are given a linked list and a positive integer $N. Write a script to remove the $Nth element from the end of the list and print the linked list.

Example Output

Input: 1 -> 2 -> 3 -> 4 -> 5, N = 2 Output: 1 -> 2 -> 3 -> 5 Input: 1 -> 2 -> 3 -> 4 -> 5, N = 1 Output: 1 -> 2 -> 3 -> 4

Logic

Traverse the linked list once to find its total length $size. If $N >= $size, advance the head to $head->next. Otherwise, traverse $size - $N - 1 steps from the head to reach the predecessor of the node to be removed, and update its next pointer to $cur->next->next.

Perl Solution

ch-2.pl

sub remove_from_end ( $self, $n ) { return if !$self->{head} || $n <= 0; my $size = 0; my $cur = $self->{head}; while ($cur) { $size++; $cur = $cur->{next}; } if ( $n >= $size ) { $self->{head} = $self->{head}->{next}; } else { $cur = $self->{head}; for ( 1 .. $size - $n - 1 ) { $cur = $cur->{next}; } $cur->{next} = $cur->{next}->{next} if $cur->{next}; } }

Python Solution

ch-2.py

def remove_from_end(self, n: int) -> None: """Remove the n-th element from the end of the list (1-indexed).""" if self.head is None or n <= 0: return size = 0 cur: Optional[Node] = self.head while cur: size += 1 cur = cur.next if n >= size: self.head = self.head.next else: cur = self.head for _ in range(size - n - 1): if cur is not None: cur = cur.next if cur is not None and cur.next is not None: cur.next = cur.next.next