Your hashmap approach is linear time, but a couple of nits:

• Sorting is O(n log n), not O(n). The dict build is O(n) time and O(m) space (m ≤ n), and the second pass is O(m), so overall O(n).
• In Python 3, use integer division for the threshold. Also, you can early-exit during counting.

Example:

def majority_element(nums):
    half = len(nums) // 2
    counts = {}
    for x in nums:
        c = counts.get(x, 0) + 1
        counts[x] = c
        if c > half:
            return x
    return None  # if not guaranteed to exist

If you want O(1) extra space, use Boyer–Moore:

def majority_element(nums):
    cand, cnt = None, 0
    for x in nums:
        if cnt == 0:
            cand, cnt = x, 1
        elif x == cand:
            cnt += 1
        else:
            cnt -= 1
    return cand  # verify with a second pass if majority isn't guaranteed

collections.Counter also makes the dict approach concise:

from collections import Counter

def majority_element(nums):
    half = len(nums) // 2
    val, freq = Counter(nums).most_common(1)[0]
    return val if freq > half else None

Side note: if the values are only 0/1/2 and you’re sorting them, that’s where the Dutch National Flag problem applies for O(n) time and O(1) space, but that’s a different task than finding a majority.

Good discussion. A couple clarifications and why the editorial shows sort:

• Sorting is O(n log n), not O(n). After sort, the majority element sits at index n//2, which makes for a short, in-place solution (low extra space), hence why it’s often shown first.
• Your hashmap version is indeed O(n) time, O(m) space (m ≤ n). In Python 3, use integer division for the threshold and you can early-exit during counting, as Jun showed.
• On AlgoDaily’s Majority Element, a majority is guaranteed. That means you can return the Boyer–Moore candidate without a second pass. If the problem didn’t guarantee it, verify in a second pass.

If you want O(1) extra space, Boyer–Moore is the go-to:

def majority_element(nums):
    cand, cnt = None, 0
    for x in nums:
        if cnt == 0:
            cand, cnt = x, 1
        elif x == cand:
            cnt += 1
        else:
            cnt -= 1
    return cand

We often list multiple approaches (similar to Trapping Rain Water) to highlight time/space trade-offs: sort for simplicity/space, hashmap for linear time, Boyer–Moore for linear time and constant space.

abrar, a few tighten-ups based on the thread:

• Sorting is O(n log n), not O(n). The reason it shows up in editorials is it’s dead simple and, in Python, Timsort runs in C so it’s often surprisingly fast. After sort, the majority is at nums[len(nums)//2].
• Your hashmap approach is O(n) time, O(m) space. In Python 3 use integer division and early-exit while counting:

def majority_element(nums):
      half = len(nums) // 2
      counts = {}
      for x in nums:
          c = counts.get(x, 0) + 1
          counts[x] = c
          if c > half:
              return x

• collections.Counter(...).most_common(1) is concise but builds all counts anyway—good for readability, not for minimal overhead.
• If a majority is guaranteed (AlgoDaily says yes), Boyer–Moore gives O(n) time and O(1) space and you can return the candidate without a second pass. Without that guarantee, verify with nums.count(cand) > len(nums)//2.
• Practical tip: for huge inputs or tight memory, prefer Boyer–Moore; for small to medium inputs in Python, sorted(nums)[n//2] can be faster in practice despite worse big-O.
• Tiny domain (e.g., only 0/1/2)? Use a small fixed-size count array—no dict or sort needed.