> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/divide-and-conquer/169.-majority-element.md).

# 169. Majority Element

<https://leetcode.com/problems/majority-element/>

use

Boyer-Moore Majority Vote Algorithm

[http://www.cs.utexas.edu/\~moore/best-ideas/mjrty/example.html](http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html#step13)

```java
/*
    time complexity: O(n), space complexity: O(1)
*/
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int majority = 0;
        
        for (int num : nums) {
            if (count == 0) {
                majority = num;
                count++;
            } else if (num != majority) {
                count--;
            } else {
                count++;
            }
        }
        return majority;
    }
}
```