AN Alternate Approach: O(n) Solution

To solve the Majority Element problem, we employ a Hash Map approach to efficiently track the frequency of each element in the array. The core idea is to iterate through the array once, counting the occurrences of each number using a hash map. By maintaining these counts, we can easily identify the element that appears more than half the time (n/2), which qualifies it as the majority element.

This method is effective because it leverages the constant-time lookup and insertion properties of hash maps, ensuring that each element is processed in linear time relative to the size of the array.

Step-by-Step Algorithm

1. Initialize a Hash Map:

   • Create an empty hash map counts where the key is an integer from the array, and the value is its corresponding count.
   • It enables quick tracking and updating of each number's frequency as we iterate through the array.

2. Iterate Through the Array:

   • For each element num in the array nums:
     • Check Presence in Hash Map:
       • If num is not already a key in counts:
         • Add to Hash Map: Insert num with an initial count of 1, as it is the first occurrence of num in the array.
       • Else:
         • Increment Count: Update the count of num by adding 1, as it is Subsequent occurrence of num increase its frequency.

3. Identify the Majority Element:

   • Iterate Through Hash Map Entries:
     • For each key-value pair (number, count) in counts:
       • Check Majority Condition:
         • If count is greater than n/2 (where n is the length of nums):
           • Return Majority Element: number is the majority element, as tt satisfies the condition of appearing more than half the time.

4. Handle Edge Cases:

   • If no element in the hash map satisfies the majority condition after the iteration:
     • Return Result: Depending on problem constraints, return a default value or handle as per requirements.

Algorithm Walkthrough

Let's walk through the algorithm using the input nums = [4, 4, 4, 4, 7, 4, 4].

1. Initialization:

   • Hash Map: counts = {}
   • Array Length: n = 7 (since there are 7 elements in the array)

2. First Iteration (num = 4):

   • Check Hash Map: 4 is not in counts.
   • Add to Hash Map: counts = {4: 1}
   • Reason: First occurrence of 4.

3. Second Iteration (num = 4):

   • Check Hash Map: 4 is already in counts with a count of 1.
   • Increment Count: counts = {4: 2}
   • Reason: Second occurrence of 4.

4. Third Iteration (num = 4):

   • Check Hash Map: 4 is already in counts with a count of 2.
   • Increment Count: counts = {4: 3}
   • Reason: Third occurrence of 4.

5. Fourth Iteration (num = 4):

   • Check Hash Map: 4 is already in counts with a count of 3.
   • Increment Count: counts = {4: 4}
   • Reason: Fourth occurrence of 4.

6. Fifth Iteration (num = 7):

   • Check Hash Map: 7 is not in counts.
   • Add to Hash Map: counts = {4: 4, 7: 1}
   • Reason: First occurrence of 7.

7. Sixth Iteration (num = 4):

   • Check Hash Map: 4 is already in counts with a count of 4.
   • Increment Count: counts = {4: 5, 7: 1}
   • Reason: Fifth occurrence of 4.

8. Seventh Iteration (num = 4):

   • Check Hash Map: 4 is already in counts with a count of 5.
   • Increment Count: counts = {4: 6, 7: 1}
   • Reason: Sixth occurrence of 4.

9. Identify the Majority Element:

   • Iterate Through Hash Map:
     • First Entry: (4, 6)
       • Check Majority Condition: 6 > 7/2 → 6 > 3.5 → True
       • Result: 4 is the majority element.
       • Reason: It appears 6 times in a 7-element array, satisfying the majority condition.

10. Final Result:

    • Majority Element: 4

Code

Complexity Analysis

Time Complexity

• Counting Phase:

  • Operation: Iterating through the array to count occurrences.
  • Complexity: O(n), where n is the number of elements in the array.
  • Reason: Each element is processed exactly once to update its count in the hash map.

• Identification Phase:

  • Operation: Iterating through the hash map entries to find the majority element.
  • Complexity: O(n) in the worst case, where all elements are unique.
  • Reason: In scenarios where every element is unique, the hash map contains n entries, requiring n iterations to check for the majority condition.

• Overall Time Complexity: O(n)

  • The two phases are sequential, and both are linear, so the combined time complexity remains linear.

Space Complexity

• Hash Map Storage:

  • Operation: Storing counts of each unique number.
  • Space: O(n) in the worst case, where all elements are unique.
  • Reason: Each unique element requires additional space in the hash map.

• Auxiliary Space:

  • Variables: A constant amount of extra space is used for variables like totalCount, product, and pointers.
  • Space: O(1)

• Overall Space Complexity: O(n)

  • Dominated by the space required to store the hash map, especially when all elements are unique.