// Boyer–Moore majority vote algorithm
// time O(n), space O(1)
int majorityElement(int* nums, int numsSize) {
    int count = 0;
    int majority = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (count == 0)
        {
            majority = nums[i];
            count = 1;
        }
        else if (nums[i] == majority)
        {
            count++;
        }
        else
        {
            count--;
        }
    }

    return majority;
}

public class Solution {
    // Boyer–Moore majority vote algorithm
    // time O(n), space O(1)
    public int MajorityElement(int[] nums) {
        int count = 0;
        int majority = 0;

        for (int i = 1; i < nums.Length; i++)
        {
            if (count == 0) {
                majority = nums[i];
                count = 1;
            }
            else if (nums[i] == majority)
            {
                count++;
            }
            else
            {
                count--;
            }
        }

        return majority;
    }
}