easy Majority Element

Problem Statement

Given an array nums having an n elements, identify the element that appears the majority of the time, meaning more than n/2 times.

Examples

1. Example 1:

   • Input: [1, 2, 2, 3, 2]
   • Expected Output: 2
   • Justification: Here, '2' appears 3 times in a 5-element array, making it the majority element.

2. Example 2:

   • Input: [4, 4, 4, 4, 7, 4, 4]
   • Expected Output: 4
   • Justification: '4' is the majority element as it appears 5 out of 7 times.

3. Example 3:

   • Input: [9, 9, 1, 1, 9, 1, 9, 9]
   • Expected Output: 9
   • Justification: '9' is the majority element, appearing 5 times in an 8-element array.

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

Solution

The divide and conquer algorithm can be used to find the majority element in an array efficiently. The strategy involves recursively dividing the array into two halves until each segment contains a single element. At this base level, a single element is trivially the majority of its one-element segment. As we merge these segments back together, we determine the majority element of each merged segment by comparing the counts of the majority elements from the two halves. The majority element of the entire array is the one that remains the majority as segments are progressively merged.

Step-by-Step Algorithm

1. Base Case: In the recursive function, check if the current segment of the array has only one element. If so, return this element as it is trivially the majority element of this single-element segment.

2. Divide Step:

   • Calculate the middle index of the current segment of the array.
   • Recursively call the function for the left half of the array (start to middle) and the right half (middle + 1 to end).
   • Store the returned values from both halves, which are potential majority elements for each half.

3. Conquer Step:

   • If the majority element found in the left half is the same as the one in the right half, return this element as the majority element for the current segment.
   • If they are different, count the occurrences of each within the current segment.

4. Combine Step:

   • Compare the counts of these two elements.
   • Return the element that has a higher count within the current segment. If the counts are equal, either can be returned as the majority element for this segment.

5. End Function: Return the majority element of the array.

This logic is based on the principle that the majority element of the entire array must be the majority element in at least one of the two halves. By recursively breaking down and then combining the array, we are able to zero in on the majority element efficiently.

Algorithm Walkthrough

1. Initial Array: [4, 4, 4, 4, 7, 4, 4]
2. Divide: Split into [4, 4, 4, 4] and [7, 4, 4].
   • For [4, 4, 4, 4], split further into [4, 4] and [4, 4].
     • [4, 4] splits into [4] and [4], both trivially 4.
     • Merge [4] and [4] to get 4 as the majority.
     • Merge [4, 4] and [4, 4] to get 4 as the majority.
   • For [7, 4, 4], split into [7] and [4, 4].
     • [7] is trivially their own majority.
     • Merge [4] and [7], neither is a majority, so no majority for this segment.
     • [4, 4] splits into [4] and [4], both trivially 4.
     • Merge [4] and [4] to get 4 as the majority.
     • Merge [7] and [4, 4], 4 is the majority.
3. Combine: Merge [4, 4, 4, 4] and [7, 4, 4].
   • Count occurrences of 4 in the entire array (5 times).
   • Since 5 is more than half of occurences of 7, 4 is the majority of the whole array.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

public class Solution {

  // Function to initiate the divide and conquer algorithm
  public int findMajority(int[] arr) {
    return majorityRec(arr, 0, arr.length - 1);
  }

  // Recursive function to find the majority element in a given segment
  private static int majorityRec(int[] arr, int start, int end) {
    // Base case: if the segment contains only one element
    if (start == end) {
      return arr[start];
    }

    // Find the middle index of the current segment
    int mid = start + (end - start) / 2;

    // Recursively find the majority element in the left and right halves
    int leftMajority = majorityRec(arr, start, mid);
    int rightMajority = majorityRec(arr, mid + 1, end);

    // If both halves agree on the majority element, return it
    if (leftMajority == rightMajority) {
      return leftMajority;
    }

    // Count the occurrences of the left and right majority elements in the current segment
    int leftCount = countOccurrences(arr, leftMajority, start, end);
    int rightCount = countOccurrences(arr, rightMajority, start, end);

    // Return the element with the higher count in the current segment
    return leftCount > rightCount ? leftMajority : rightMajority;
  }

  // Helper function to count the occurrences of a number in a specified range
  private static int countOccurrences(int[] arr, int num, int start, int end) {
    int count = 0;
    for (int i = start; i <= end; i++) {
      if (arr[i] == num) {
        count++;
      }
    }
    return count;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.findMajority(new int[] { 1, 2, 2, 3, 2 })); // Expect 2
    System.out.println(sol.findMajority(new int[] { 4, 4, 4, 4, 7, 4, 4 })); // Expect 4
    System.out.println(sol.findMajority(new int[] { 9, 9, 1, 1, 9, 1, 9, 9 })); // Expect 9
  }
}

Time and Space Complexity Analysis

• Time Complexity: The array is recursively divided, and at each level of recursion, counting occurrences takes O(n) time. It takes O(log n) time to divide arrays in the subarray, and the total time complexity is O(n log n).

• Space Complexity: Due to the recursive calls, the space complexity is determined by the depth of the recursion tree, which is O(log n). No additional significant space is used outside of the recursion stack.

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

import java.util.Map;
import java.util.HashMap;

public class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); // Create a map to store counts of each number
        for (int num : nums) { // Iterate over each number in the array
            if (!counts.containsKey(num)) { // If the number is not already in the map
                counts.put(num, 1); // Add the number to the map with a count of 1
            } else {
                counts.put(num, counts.get(num) + 1); // Increment the count for the number
            }
        }
        return counts; 
    }

    
    public int findMajority(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums); // Get the count of each number using countNums method

        Map.Entry<Integer, Integer> majorityEntry = null; 
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { // Iterate over all entries in the map
            if (entry.getValue() > nums.length / 2) // Check if the count of the current number is more than half the array size
                return entry.getKey(); // If yes, return the current number as the majority element
        }

        return majorityEntry.getKey(); 
}

  
    public static void main(String[] args) {
        Solution sol = new Solution(); 
        System.out.println(sol.findMajority(new int[]{1, 2, 2, 3, 2})); 
        System.out.println(sol.findMajority(new int[]{4, 4, 4, 4, 7, 4, 4})); 
        System.out.println(sol.findMajority(new int[]{9, 9, 1, 1, 9, 1, 9, 9})); /
    }
}

Complexity Analysis

Time Complexity

• Counting Phase:

  • Operation: Iterating through the array to count occurrences.
  • Complexity: , 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: 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:

  • 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: 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:

• Overall Space Complexity:

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