Majority Element - Leetcode Solution

The problem statement is as follows:

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 exists in the array.

To solve this problem, we will use a hash table to keep track of the count of each element. We will iterate through the array and update the count of each element in the hash table. Once the iteration is complete, we will iterate through the hash table and check if the count of any element is greater than ⌊n/2⌋. If we find such an element, we return it as the majority element.

Here is the detailed solution:

1. Create an empty hash table to keep track of the count of each element.

2. Iterate through the array and update the count of each element in the hash table.

   • If the element is already in the hash table, increment its count by 1.
   • If the element is not in the hash table, add it to the hash table with a count of 1.

3. Iterate through the hash table and check if the count of any element is greater than ⌊n/2⌋.

   • If we find such an element, return it as the majority element.
   • If we don't find such an element, the array does not have a majority element.

Here is the Python code implementing the above solution:

def majorityElement(nums):
    counts = {}
    for num in nums:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1
    
    for num, count in counts.items():
        if count > len(nums) // 2:
            return num
    
    return None

The time complexity of this solution is O(n) as we are iterating through the array and the hash table only once. The space complexity is also O(n) as we are using a hash table to store the count of each element.

1