Bash Equi Leader
equi_leader() {
local -n _a="$1"
local _leaderSize=0 _value=0 _leaderCount=0
local _k _v
for _k in "${!_a[@]}"; do
_v=${_a[$_k]}
if (( _leaderSize == 0 )); then
((_leaderSize++))
_value=$_v
elif (( _value != _v )); then
((_leaderSize--))
else
((_leaderSize++))
fi
done
local _candidate
if (( _leaderSize > 0 )); then _candidate=$_value; else _candidate=-1; fi
_leaderCount=0
for _v in "${_a[@]}"; do
if (( _v == _candidate )); then ((_leaderCount++)); fi
done
local _leader=-1
local _count=${#_a[@]}
if (( 2 * _leaderCount > _count )); then
_leader=$_candidate
fi
local _lLeaderCount=0 _equiLeaders=0
for _k in "${!_a[@]}"; do
_v=${_a[$_k]}
local _leftHalf=$(( (_k + 1) / 2 ))
local _rightHalf=$(( (_count - _k - 1) / 2 ))
if (( _v == _leader )); then
((_lLeaderCount++))
fi
local _rLeaderCount=$(( _leaderCount - _lLeaderCount ))
if (( _lLeaderCount > _leftHalf && _rLeaderCount > _rightHalf )); then
((_equiLeaders++))
fi
done
echo "$_equiLeaders"
}
This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.