Erlang Peaks
-module(peaks).
-export([peaks/1]).
peaks(A) ->
N = length(A),
case N =< 2 of
true -> 0;
false ->
{Sum0, Dist0, Last0} = build_sums(A, N),
LastVal = array:get(N - 2, Sum0),
Sum1 = array:set(N - 1, LastVal, Sum0),
case LastVal =:= 0 of
true -> 0;
false ->
Dist1 = max(Dist0, N - Last0),
case find_block_size(Dist1, N, Sum1) of
{ok, BlockSize} -> N div BlockSize;
not_found ->
FinalSize = smallest_divisor_from(Dist1, N),
N div FinalSize
end
end
end.
build_sums(A, N) ->
Arr = array:from_list(A),
Sum0 = array:new(N, {default, 0}),
{SumF, {DistF, LastF}} = lists:foldl(fun(I, {Sum, {Dist, Last}}) ->
SumPrev = array:get(I - 1, Sum),
Ai = array:get(I, Arr),
IsPeak = Ai > array:get(I - 1, Arr) andalso Ai > array:get(I + 1, Arr),
case IsPeak of
true -> {array:set(I, SumPrev + 1, Sum), {max(Dist, I - Last), I}};
false -> {array:set(I, SumPrev, Sum), {Dist, Last}}
end
end, {Sum0, {0, -1}}, lists:seq(1, N - 2)),
{SumF, DistF, LastF}.
find_block_size(Dist, N, Sum) ->
find_block_size((Dist bsr 1) + 1, Dist, N, Sum).
find_block_size(I, Dist, _N, _Sum) when I >= Dist ->
not_found;
find_block_size(I, Dist, N, Sum) ->
case N rem I =:= 0 andalso check_blocks(I, I, N, Sum, 0) of
true -> {ok, I};
false -> find_block_size(I + 1, Dist, N, Sum)
end.
check_blocks(J, _Step, N, _Sum, _Last) when J > N ->
true;
check_blocks(J, Step, N, Sum, Last) ->
SumJ = array:get(J - 1, Sum),
case SumJ =< Last of
true -> false;
false -> check_blocks(J + Step, Step, N, Sum, SumJ)
end.
smallest_divisor_from(Dist, N) ->
case N rem Dist of
0 -> Dist;
_ -> smallest_divisor_from(Dist + 1, N)
end.
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Go Peaks
func peaks(a []int) int {
n := len(a)
if n <= 2 {
return 0
}
sum := make([]int, n)
last := -1
dist := 0
for i := 1; i+1 < n; i++ {
sum[i] = sum[i-1]
if a[i] > a[i-1] && a[i] > a[i+1] {
if i-last > dist {
dist = i - last
}
last = i
sum[i]++
}
}
sum[n-1] = sum[n-2]
if sum[n-1] == 0 {
return 0
}
if n-last > dist {
dist = n - last
}
j := 0
for i := dist>>1 + 1; i < dist; i++ {
if n%i == 0 {
last = 0
for j = i; j <= n; j += i {
if sum[j-1] <= last {
break
}
last = sum[j-1]
}
if j > n {
return n / i
}
}
}
last = dist
for n%last != 0 {
last++
}
return n / last
}
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Haskell Peaks
import Data.Array (Array, listArray, (!))
peaks :: [Int] -> Int
peaks a
| n <= 2 = 0
| totalPeaks == 0 = 0
| otherwise = result
where
n = length a
arr = listArray (0, n - 1) a :: Array Int Int
isPeakAt i = i > 0 && i + 1 < n && arr ! i > arr ! (i - 1) && arr ! i > arr ! (i + 1)
-- running count of peaks seen in a[0 .. i], for i in [0 .. n-2]
sumList = scanl (\acc i -> acc + (if isPeakAt i then 1 else 0)) 0 [1 .. n - 2]
sumArr = listArray (0, n - 2) sumList :: Array Int Int
totalPeaks = sumArr ! (n - 2)
-- sum[n-1] mirrors sum[n-2] in the original algorithm
sumAt idx
| idx == n - 1 = totalPeaks
| otherwise = sumArr ! idx
peakPositions = [i | i <- [1 .. n - 2], isPeakAt i]
lastPeak = last peakPositions
dist = max (gapMax (-1) peakPositions) (n - lastPeak)
where
gapMax _ [] = 0
gapMax prev (p : ps) = max (p - prev) (gapMax p ps)
-- can every block of size i (n/i blocks) contain at least one peak?
checkGroups i = walk 0 i
where
walk lastSum j
| j > n = True
| sumAt (j - 1) <= lastSum = False
| otherwise = walk (sumAt (j - 1)) (j + i)
candidates = [i | i <- [(dist `div` 2) + 1 .. dist - 1], n `mod` i == 0, checkGroups i]
result = case candidates of
(i : _) -> n `div` i
[] -> n `div` head [l | l <- [dist ..], n `mod` l == 0]
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Java Peaks
public class Solution {
public static int peaks(int[] a) {
int n = a.length;
if (n <= 2) {
return 0;
}
int[] sum = new int[n];
int last = -1;
int dist = 0;
for (int i = 1; i + 1 < n; ++i) {
sum[i] = sum[i - 1];
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
dist = Math.max(dist, i - last);
last = i;
++sum[i];
}
}
sum[n - 1] = sum[n - 2];
if (sum[n - 1] == 0) {
return 0;
}
dist = Math.max(dist, n - last);
int j = 0;
for (int i = (dist >> 1) + 1; i < dist; ++i) {
if (n % i == 0) {
last = 0;
for (j = i; j <= n; j += i) {
if (sum[j - 1] <= last) {
break;
}
last = sum[j - 1];
}
if (j > n) {
return n / i;
}
}
}
for (last = dist; n % last != 0; ) {
++last;
}
return n / last;
}
}
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Lisp Peaks
(defun peaks (a)
(let ((n (length a)))
(if (<= n 2)
0
(let* ((vec (coerce a 'vector))
(sum (make-array n :initial-element 0))
(last -1)
(dist 0))
(loop for i from 1 below (1- n)
do (progn
(setf (aref sum i) (aref sum (1- i)))
(when (and (> (aref vec i) (aref vec (1- i)))
(> (aref vec i) (aref vec (1+ i))))
(setf dist (max dist (- i last)))
(setf last i)
(incf (aref sum i)))))
(setf (aref sum (1- n)) (aref sum (- n 2)))
(if (zerop (aref sum (1- n)))
0
(progn
(setf dist (max dist (- n last)))
(loop for i from (1+ (ash dist -1)) below dist
do (when (zerop (mod n i))
(let ((lst 0)
(j i))
(loop while (<= j n)
do (if (<= (aref sum (1- j)) lst)
(return)
(progn
(setf lst (aref sum (1- j)))
(incf j i))))
(when (> j n)
(return-from peaks (floor n i))))))
(setf last dist)
(loop while (/= 0 (mod n last))
do (incf last))
(floor n last)))))))
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
PHP Peaks
function peaks(array $a): int
{
$n = count($a);
if ($n <= 2) {
return 0;
}
$sum = array_fill(0, $n, 0);
$last = -1;
$dist = 0;
for ($i = 1; $i + 1 < $n; ++$i) {
$sum[$i] = $sum[$i - 1];
if (($a[$i] > $a[$i - 1]) && ($a[$i] > $a[$i + 1])) {
$dist = max($dist, $i - $last);
$last = $i;
++$sum[$i];
}
}
if (($sum[$n - 1] = $sum[$n - 2]) === 0) {
return 0;
}
$dist = max($dist, $n - $last);
for ($i = ($dist >> 1) + 1; $i < $dist; ++$i) {
if ($n % $i === 0) {
$last = 0;
for ($j = $i; $j <= $n; $j += $i) {
if ($sum[$j - 1] <= $last) {
break;
}
$last = $sum[$j - 1];
}
if ($j > $n) {
return $n / $i;
}
}
}
for ($last = $dist; $n % $last;) {
++$last;
}
return (int)($n / $last);
}
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Python Peaks
def peaks(a: list[int]) -> int:
n = len(a)
if n <= 2:
return 0
total = [0] * n
last = -1
dist = 0
for i in range(1, n - 1):
total[i] = total[i - 1]
if a[i] > a[i - 1] and a[i] > a[i + 1]:
dist = max(dist, i - last)
last = i
total[i] += 1
total[n - 1] = total[n - 2]
if total[n - 1] == 0:
return 0
dist = max(dist, n - last)
for i in range(dist // 2 + 1, dist):
if n % i == 0:
last = 0
j = i
while j <= n:
if total[j - 1] <= last:
break
last = total[j - 1]
j += i
if j > n:
return n // i
last = dist
while n % last:
last += 1
return n // last
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Rust Peaks
fn peaks(a: &[i64]) -> i64 {
let n = a.len();
if n <= 2 {
return 0;
}
let mut sum = vec![0i64; n];
let mut last: i64 = -1;
let mut dist: i64 = 0;
for i in 1..n - 1 {
sum[i] = sum[i - 1];
if a[i] > a[i - 1] && a[i] > a[i + 1] {
dist = dist.max(i as i64 - last);
last = i as i64;
sum[i] += 1;
}
}
sum[n - 1] = sum[n - 2];
if sum[n - 1] == 0 {
return 0;
}
dist = dist.max(n as i64 - last);
let mut i = (dist >> 1) + 1;
while i < dist {
if n as i64 % i == 0 {
let mut last_sum = 0i64;
let mut j = i;
while j <= n as i64 {
if sum[(j - 1) as usize] <= last_sum {
break;
}
last_sum = sum[(j - 1) as usize];
j += i;
}
if j > n as i64 {
return n as i64 / i;
}
}
i += 1;
}
let mut last_final = dist;
while n as i64 % last_final != 0 {
last_final += 1;
}
n as i64 / last_final
}
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
TypeScript Peaks
function peaks(a: number[]): number {
const n = a.length;
if (n <= 2) {
return 0;
}
const sum: number[] = new Array(n).fill(0);
let last = -1;
let dist = 0;
for (let i = 1; i + 1 < n; ++i) {
sum[i] = sum[i - 1];
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
dist = Math.max(dist, i - last);
last = i;
++sum[i];
}
}
sum[n - 1] = sum[n - 2];
if (sum[n - 1] === 0) {
return 0;
}
dist = Math.max(dist, n - last);
for (let i = (dist >> 1) + 1; i < dist; ++i) {
if (n % i === 0) {
last = 0;
let j = i;
for (; j <= n; j += i) {
if (sum[j - 1] <= last) {
break;
}
last = sum[j - 1];
}
if (j > n) {
return n / i;
}
}
}
for (last = dist; n % last; ) {
++last;
}
return Math.trunc(n / last);
}
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Bash Perm Check
perm_check() {
local -n _a="$1"
local -a _sorted=($(printf '%s\n' "${_a[@]}" | sort -n))
local _c=${#_sorted[@]}
local _k
for ((_k = 0; _k < _c - 1; _k++)); do
if (( _sorted[_k] != _k + 1 )); then
echo 0
return
fi
done
echo 1
}
This validates that every value from 1 to N appears exactly once.