Perl Weekly Challenge: 345

Both challenges provided this week (Challenge-345) an excellent opportunity to practice array manipulation and dynamic state tracking in Perl, using simple constructs like for loops, unshift, and effective boundary/state checks.

Challenge 1: Peak Positions

You are given an array of integers, @ints.

Find all the peaks in the array, a peak is an element that is strictly greater than its left and right neighbours. Return the indices of all such peak positions.

Example:

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

My Solution:
The core challenge is handling the boundary conditions—the first and last elements—which only have one neighbor.
My strategy was to process the array from index 0 to N-1 and define the "neighbors" for any given element $ints[i] as follows:

1. Left Neighbor ($left):
   • If $i is 0 (the first element), the left neighbor is non-existent. To ensure the condition $ints[i] > $left is always true, I set $left = -1.
   • Otherwise, $left = $ints[$i-1].
2. Right Neighbor ($right):
   • If $i is N-1 (the last element), the right neighbor is non-existent. Again, I set $right = -1.
   • Otherwise, $right = $ints[$i+1].

The final check is simply: $ints[$i] > $left && $ints[$i] > $right.

The solution uses a clean for loop to iterate over the indices and the Perl range operator 0..$#ints for concise code.

sub find_peaks {
    my @ints = @_;
    my @peaks;

    # Iterate through all indices
    for my $i (0..$#ints) {
        # Define the left neighbor, using -1 for the first element
        my $left  = ($i == 0 ) ? -1 : $ints[$i-1];

        # Define the right neighbor, using -1 for the last element
        my $right = ($i == $#ints) ? -1 : $ints[$i+1];

        # A peak is strictly greater than both its effective neighbors
        if ($ints[$i] > $left && $ints[$i] > $right) {
            push @peaks, $i;
        }
    }
    return @peaks;
}

# Example: [2, 4, 6, 5, 3] -> Peak is 6 at index 2
# Output: (2)

---

Challenge 2: Last Visitor

You are given an integer array @ints where each element is either a positive integer or -1.
We process the array from left to right while maintaining two lists:

@seen (stores previously seen positive integers, newest at the front)
@ans (stores answers for each -1).

Rules:

If $ints[i] is a positive number -> insert it at the front of @seen.
If $ints[i] is -1: 
    Let $x be how many -1s in a row we’ve seen before this one.
    If $x < len(@seen) -> append seen[x] to @ans
    Else -> append -1 to @ans
    At the end, return @ans.

The Logic and State Management:

This problem is all about maintaining and querying state.

1. State Management with @seen: The requirement "newest at the front" is key. When a positive number comes in, we use unshift to put it at the start of @seen. This makes it behave like a stack, but with array-based indexing (index 0 is newest, index 1 is next newest, and so on).
2. The -1 Rule: When we hit a -1, we must look backward to count the consecutive -1s ($x).
   • I used a small while loop within the main loop to handle this lookback, starting from the element immediately before the current index $i-1. The loop increments $x as long as it finds -1s.
   • Once we have $x, we check if it's a valid index: $x < @seen.
     • If it is, we retrieve the x-th newest element: $seen[x].
     • If it's not (meaning we haven't seen enough positive numbers to satisfy the lookup), we append -1.

The use of unshift and direct array indexing in Perl makes the solution quite easy.

sub process_ints {
    my @ints = @_;
    my @seen;  # Newest seen numbers are at the front (index 0)
    my @ans;

    for (my $i = 0; $i < @ints; $i++) {
        if ($ints[$i] == -1) {
            # 1. Calculate x: count of consecutive -1s before this one
            my $x = 0;
            my $j = $i - 1;
            while ($j >= 0 && $ints[$j] == -1) {
                $x++;
                $j--;
            }

            # 2. Apply the lookup rule
            if ($x < @seen) {
                # $seen[0] is the newest (x=0)
                # $seen[1] is the next newest (x=1), etc.
                push @ans, $seen[$x]; 
            } else {
                push @ans, -1;
            }
        } else {
            # If positive number, insert at the front (newest)
            unshift @seen, $ints[$i];
        }
    }
    return @ans;
}

# Example: [2, -1, 4, -1, -1] 
# i=0: 2 -> @seen=(2)
# i=1: -1, x=0. x < @seen (0 < 1). @ans=(2).
# i=2: 4 -> @seen=(4, 2)
# i=3: -1, x=0. x < @seen (0 < 2). @ans=(2, 4).
# i=4: -1, x=1. x < @seen (1 < 2). @ans=(2, 4, 2).
# Output: (2, 4, 2)