Problem¶

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10**4
• -10**9 <= nums[i] <= 10**9

Follow-up: Could you solve the problem in linear time and in O(1) space?

Example 1:

**Input:** nums = [3,2,3]
**Output:** 3

Solve¶

Let quickly settle this with a hash map counting cache array, ideally with built-in implementation dict() or {} in python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums_count = {}
        for n in nums:
            if n not in nums_count:
                nums_count[n] = 0
            nums_count[n] += 1
            if nums_count[n] > len(nums)//2:
                return n
        return "Some thing isn't right"

A better that using lower memory is using quicksort and return the value of middle n//2 index element

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[n//2]

Follow up madness¶

Here is the Crtl + C code:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        confident = 0
        majority_number = None
        for current_number in nums:
            if confident == 0:
                majority_number = current_number
            if current_number == majority_number:
                confident += 1 
            else:
                confident -= 1
        return majority_number

• You assuming any number to be the majority_number.
• With each loop through all available number in nums array we check our confident level
  • If it appear again: raise our confident by 1
  • Else reducing it by 1
  • When confident = 0, we try change our majority_number
• Return majority_number after

Compare?¶

Barely notice-able different, the input really easy on us. Unless we using a compiler, a interpreter language like python does not provide good enough information on which faster