| 31 October 2025 | Challenge 345 |
The Last Peak
Task 1: Peak Positions
Submitted by: Mohammad Sajid Anwar
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 1
Input: @ints = (1, 3, 2)
Output: (1)
Example 2
Input: @ints = (2, 4, 6, 5, 3)
Output: (2)
Example 3
Input: @ints = (1, 2, 3, 2, 4, 1)
Output: (2, 4)
Example 4
Input: @ints = (5, 3, 1)
Output: (0)
Example 5
Input: @ints = (1, 5, 1, 5, 1, 5, 1)
Output: (1, 3, 5)
Solution
Surrounding the given numbers with \(-\infty\) turns the first and the last element into inner elements that have a smaller border neighbor.
Allowing floating point numbers using a precision of 1e-6.
For all inner elements \(x_i\) find the signs \(s_i^- = \operatorname{sgn}(x_i - x_{i-1})\) and \(s^+_i = \operatorname{sgn}(x_{i+1} - x_i)\) of the differences between the element and its predecessor and successor. There is a peak at a position \(i\) if and only if \(s^-_i = 1\) and \(s^+_i = -1\), which is equivalent to \(s^-_i - s^+_i = 2\).
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub peak_positions {
my $i = pdl -inf, @_, -inf;
my $s = ($i(1:-1) - $i(0:-2))->mult(1e6)->clip(-1, 1);
which $s(0:-2) - $s(1:-1) == 2;
}
See the full solution to task 1.
Task 2: Last Visitor
Submitted by: Mohammad Sajid Anwar
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 the 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.
Example 1
Input: @ints = (5, -1, -1)
Output: (5, -1)
@seen = (5)
First -1: @ans = (5)
Second -1: @ans = (5, -1)
Example 2
Input: @ints = (3, 7, -1, -1, -1)
Output: (7, 3, -1)
@seen = (3, 7)
First -1: @ans = (7)
Second -1: @ans = (7, 3)
Third -1: @ans = (7, 3, -1)
Example 3
Input: @ints = (2, -1, 4, -1, -1)
Output: (2, 4, 2)
Example 4
Input: @ints = (10, 20, -1, 30, -1, -1)
Output: (20, 30, 20)
Example 5
Input: @ints = (-1, -1, 5, -1)
Output: (-1, -1, 5)
Solution
- Let the list of given integers be \((I_0,\ldots,I_{n - 1})\).
- Define an indicator \(p_k\) for positive values in \(I_k\) as
-
Build the final seen array \(s_k\) by splitting the reversed integer list into sub-lists of non-negative and negative values and re-joining these.
-
Find the actual length \(l_k\) of the seen array at position \(k\) as
- Enumerate immediately succeeding equal values from \(p_k\) according to:
- Find the number \(o_k\) of positive integers following position \(k\) as
-
As the seen array was build in its final state, the index \(x_k\) needs to be shifted by the offset \(o_k\) to an effective index \(y_k = x_k + o_k\).
-
Let \(m_i\) be the index of the \((i+1)\)-th \(-1\) in \(I_k\), i.e. \(m_0\) is the index of the first \(-1\) etc.
-
Pick the values at indices \(y_{m_i}\) from the seen array to find the answer array \(a_i\). For indices \(k\) having \(x_k \ge l_k\) the index \(y_k\) will point to an \(s_{y_k} = -1\) at the list’s tail. Therefore the check \(x_k < l_k\) may be omitted and the index \(y_k\) may be used unconditionally to access \(s_{y_k}\).
Putting everything together results in the formula:
\[a_i = s_{y_{m_i}}\]Translated to PDL this could be written as:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub last_visitor {
my $ints = long @_;
my $p = $ints >= 0;
my $seen = append $ints(-1:0)->where_both($p(-1:0));
my $len = $p->cumusumover;
$seen($p(*1)->enumvec + $len(-1) - $len)->(!$p;?);
}
Note that all non-negative numbers including zero are inserted into the seen array. Negative numbers other than \(-1\) may be used, too. These will then be appended to the answer array instead of \(-1\) according to their reversed position in the list.
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.