[LeetCode] 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Thought process:

Brute force solution is trivial.

Iterate through the array. Keep track of a majority element candidate and its count. Increment count if current number == majority and decrement count otherwise. Reset majority element and count if count == 0.

At the end, if there's a majority element, count > 0. count is essentially count of majority elements - count of other numbers.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public int majorityElement(int[] num) { int majority = num[0]; int count = 1; for (int i = 1; i < num.length; i++){ if (count == 0) { count++; majority = num[i]; } else if (majority == num[i]) { count++; } else { count--; } } return majority; } }

Time complexity: O(n).
Space complexity: O(1).