Majority Element

Medium Arrays

Find the element that appears more than n/2 times using the Boyer-Moore voting algorithm in O(n) time and O(1) space.

Sample input

[2, 2, 1, 1, 1, 2, 2]

Sample output

Solution

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

print(majority_element([2, 2, 1, 1, 1, 2, 2]))

function majorityElement(nums) {
  let count = 0, candidate = null;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += num === candidate ? 1 : -1;
  }
  return candidate;
}

console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));

public class Main {
    static int majorityElement(int[] nums) {
        int count = 0, candidate = 0;
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }

    public static void main(String[] args) {
        System.out.println(majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
    }
}

fun majorityElement(nums: IntArray): Int {
    var count = 0
    var candidate = 0
    for (num in nums) {
        if (count == 0) candidate = num
        count += if (num == candidate) 1 else -1
    }
    return candidate
}

fun main() {
    println(majorityElement(intArrayOf(2, 2, 1, 1, 1, 2, 2)))
}

func majorityElement(_ nums: [Int]) -> Int {
    var count = 0
    var candidate = 0
    for num in nums {
        if count == 0 { candidate = num }
        count += (num == candidate) ? 1 : -1
    }
    return candidate
}

print(majorityElement([2, 2, 1, 1, 1, 2, 2]))

int majorityElement(List<int> nums) {
  int count = 0, candidate = 0;
  for (final num in nums) {
    if (count == 0) candidate = num;
    count += (num == candidate) ? 1 : -1;
  }
  return candidate;
}

void main() {
  print(majorityElement([2, 2, 1, 1, 1, 2, 2]));
}

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(const vector<int>& nums) {
    int count = 0, candidate = 0;
    for (int num : nums) {
        if (count == 0) candidate = num;
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

int main() {
    cout << majorityElement({2, 2, 1, 1, 1, 2, 2}) << endl;
    return 0;
}

#include <stdio.h>

int majorityElement(int *nums, int n) {
    int count = 0, candidate = 0;
    for (int i = 0; i < n; i++) {
        if (count == 0) candidate = nums[i];
        count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;
}

int main() {
    int nums[] = {2, 2, 1, 1, 1, 2, 2};
    printf("%d\n", majorityElement(nums, 7));
    return 0;
}