< Back




169. Majority Element

We're given an array of integers and asked to find the majority element, such that it appears more
than n // 2 times in the array.

Using the Boyer-Moore voting algorithm, we'll always pick a candidate for the majority element when
our count for the candidate is 0. Each time we see the candidate, we add 1 to the count, otherwise
we add -1. If the count resets to 0, the next element in the array will be the candidate.

Eventually, we process all numbers in the array and discover the majority element, as we'll always
eventually have an instance where the count is positive and finds the majority element.

The solution is as follows:


  class Solution:
      def majorityElement(self, nums: List[int]) -> int:
          c, candidate = 0, None

          for num in nums:
              if not c:
                  candidate = num

              c += 1 if num == candidate else -1

          return candidate


_ Time Complexity:

  O(n) - We iterate through all integers in the input.

_ Space Complexity:

  O(1) - We use constant space to store the count and candidate.