Lisp Equi Leader
(defun equi-leader (a)
(let ((vec (coerce a 'vector))
(leader-size 0) (value 0))
(loop for v across vec
do (cond
((zerop leader-size) (incf leader-size) (setf value v))
((/= value v) (decf leader-size))
(t (incf leader-size))))
(let* ((candidate (if (> leader-size 0) value -1))
(leader-count 0))
(loop for v across vec do (when (= v candidate) (incf leader-count)))
(let ((leader (if (> leader-count (/ (length vec) 2)) candidate -1))
(count (length vec))
(l-leader-count 0)
(equi-leaders 0))
(loop for k from 0 below count
for v = (aref vec k)
do (let ((left-half (floor (1+ k) 2))
(right-half (floor (- count k 1) 2)))
(when (= v leader) (incf l-leader-count))
(let ((r-leader-count (- leader-count l-leader-count)))
(when (and (> l-leader-count left-half)
(> r-leader-count right-half))
(incf equi-leaders)))))
equi-leaders))))
This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.