Notes

Haskell Dominator

dominator :: [Int] -> Int
dominator a
  | count > length a `div` 2 = index
  | otherwise                = -1
  where
    (size, value, index) = foldl step (0, 0, 0) (zip [0 ..] a)
    step (sz, val, idx) (k, v)
      | sz == 0   = (1, v, k)
      | val /= v  = (sz - 1, val, idx)
      | otherwise = (sz + 1, val, idx)

    candidate = if size > 0 then value else -1
    count     = length (filter (== candidate) a)

This finds a value that appears in more than half of the array, then returns one valid index for it.

Java Dominator

public class Solution {
    public static int dominator(int[] a) {
        int size = 0;
        int value = 0;
        int index = 0;

        for (int k = 0; k < a.length; k++) {
            int v = a[k];
            if (size == 0) {
                size++;
                value = v;
                index = k;
            } else if (value != v) {
                size--;
            } else {
                size++;
            }
        }
        int candidate = size > 0 ? value : -1;

        int count = 0;
        for (int v : a) {
            if (v == candidate) {
                count++;
            }
        }
        if (count <= a.length / 2.0) {
            index = -1;
        }

        return index;
    }
}

This finds a value that appears in more than half of the array, then returns one valid index for it.

Lisp Dominator

(defun dominator (a)
  (let ((vec (coerce a 'vector))
        (size 0) (value 0) (index 0))
    (loop for k from 0 below (length vec)
          for v = (aref vec k)
          do (cond
               ((zerop size) (incf size) (setf value v) (setf index k))
               ((/= value v) (decf size))
               (t (incf size))))
    (let ((candidate (if (> size 0) value -1))
          (count 0))
      (loop for v across vec do (when (= v candidate) (incf count)))
      (when (<= count (/ (length vec) 2))
        (setf index -1))
      index)))

This finds a value that appears in more than half of the array, then returns one valid index for it.

PHP Dominator

function dominator(array $a): int
{
    $size  = $value = $count = 0;
    $index = 0;
    foreach ($a as $k => $v) {
        if ($size === 0) {
            $size++;
            $value = $v;
            $index = $k;
        } elseif ($value !== $v) {
            $size--;
        } else {
            $size++;
        }
    }
    $candidate = $size > 0 ? $value : -1;

    foreach ($a as $v) {
        if ($v === $candidate) {
            $count++;
        }
    }
    if ($count <= count($a) / 2) {
        $index = -1;
    }

    return $index;
}

This finds a value that appears in more than half of the array, then returns one valid index for it.

Python Dominator

def dominator(a: list[int]) -> int:
    size = value = index = 0
    for k, v in enumerate(a):
        if size == 0:
            size += 1
            value = v
            index = k
        elif value != v:
            size -= 1
        else:
            size += 1
    candidate = value if size > 0 else -1

    count = sum(1 for v in a if v == candidate)
    if count <= len(a) / 2:
        index = -1

    return index

This finds a value that appears in more than half of the array, then returns one valid index for it.

Rust Dominator

fn dominator(a: &[i64]) -> i64 {
    let mut size = 0i64;
    let mut value = 0;
    let mut index: i64 = 0;

    for (k, &v) in a.iter().enumerate() {
        if size == 0 {
            size += 1;
            value = v;
            index = k as i64;
        } else if value != v {
            size -= 1;
        } else {
            size += 1;
        }
    }

    let candidate = if size > 0 { value } else { -1 };

    let count = a.iter().filter(|&&v| v == candidate).count() as i64;
    if count <= a.len() as i64 / 2 {
        index = -1;
    }

    index
}

This finds a value that appears in more than half of the array, then returns one valid index for it.

TypeScript Dominator

function dominator(a: number[]): number {
  let size = 0;
  let value = 0;
  let index = 0;

  a.forEach((v, k) => {
    if (size === 0) {
      size++;
      value = v;
      index = k;
    } else if (value !== v) {
      size--;
    } else {
      size++;
    }
  });

  const candidate = size > 0 ? value : -1;

  let count = 0;
  for (const v of a) {
    if (v === candidate) {
      count++;
    }
  }

  if (count <= a.length / 2) {
    index = -1;
  }

  return index;
}

This finds a value that appears in more than half of the array, then returns one valid index for it.

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.

C++ Equi Leader

#include <vector>

int equiLeader(const std::vector<int>& a)
{
    int leaderSize = 0;
    int value = 0;
    for (int v : a) {
        if (leaderSize == 0) {
            ++leaderSize;
            value = v;
        } else if (value != v) {
            --leaderSize;
        } else {
            ++leaderSize;
        }
    }
    int candidate = leaderSize > 0 ? value : -1;

    int leaderCount = 0;
    for (int v : a) {
        if (v == candidate) {
            ++leaderCount;
        }
    }

    int count = static_cast<int>(a.size());
    int leader = -1;
    if (leaderCount > count / 2) {
        leader = candidate;
    }

    int lLeaderCount = 0;
    int equiLeaders = 0;

    for (int k = 0; k < count; ++k) {
        int v = a[k];
        int leftHalf = (k + 1) / 2;
        int rightHalf = (count - k - 1) / 2;
        if (v == leader) {
            ++lLeaderCount;
        }

        int rLeaderCount = leaderCount - lLeaderCount;
        if (lLeaderCount > leftHalf && rLeaderCount > rightHalf) {
            ++equiLeaders;
        }
    }

    return equiLeaders;
}

This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.

C# Equi Leader

static int EquiLeader(int[] a)
{
    var leaderSize = 0;
    var value = 0;

    foreach (var v in a)
    {
        if (leaderSize == 0)
        {
            leaderSize++;
            value = v;
        }
        else if (value != v)
        {
            leaderSize--;
        }
        else
        {
            leaderSize++;
        }
    }

    var candidate = leaderSize > 0 ? value : -1;
    var leaderCount = 0;
    foreach (var v in a)
    {
        if (v == candidate)
        {
            leaderCount++;
        }
    }

    var leader = -1;
    if (leaderCount > a.Length / 2.0)
    {
        leader = candidate;
    }

    var count = a.Length;
    var lLeaderCount = 0;
    var equiLeaders = 0;

    for (int k = 0; k < count; k++)
    {
        var v = a[k];
        var leftHalf = (k + 1) / 2;
        var rightHalf = (count - k - 1) / 2;
        if (v == leader)
        {
            lLeaderCount++;
        }

        var rLeaderCount = leaderCount - lLeaderCount;
        if (lLeaderCount > leftHalf && rLeaderCount > rightHalf)
        {
            equiLeaders++;
        }
    }

    return equiLeaders;
}

This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.