Majority Element in C#

Programming C#
1

To find the majority element in an array (an element that appears more than ⌊n/2⌋ times), you can use several approaches. One of the most efficient methods is the Boyer-Moore Voting Algorithm, which runs in O(n) time complexity and O(1) space complexity. Here’s a breakdown of how it works and a sample implementation in C#.

Explanation of the Boyer-Moore Voting Algorithm:

  1. Initialization: Start with two variables: one for the candidate element (candidate) and one for its count (count).

  2. Candidate Selection:

    • Traverse the array and for each element:
      • If count is 0, set the candidate to the current element and set count to 1.
      • If the current element is the same as the candidate, increment the count.
      • If it’s different, decrement the count.
    • This process effectively cancels out pairs of different elements, and by the end of the traversal, if a majority element exists, it will be stored in candidate.

  3. Verification: After finding the candidate, you should verify that it is indeed the majority element by counting its occurrences in the array.

Sample Code:

using System;

class MajorityElementFinder
{
    public static int FindMajorityElement(int[] nums)
    {
        int candidate = 0;
        int count = 0;

        // Step 1: Find the candidate
        foreach (int num in nums)
        {
            if (count == 0)
            {
                candidate = num;
                count = 1;
            }
            else if (num == candidate)
            {
                count++;
            }
            else
            {
                count--;
            }
        }

        // Step 2: Verify that the candidate is the majority element
        count = 0;
        foreach (int num in nums)
        {
            if (num == candidate)
            {
                count++;
            }
        }

        return count > nums.Length / 2 ? candidate : -1; // Return -1 if no majority element
    }

    static void Main()
    {
        int[] nums = { 3, 2, 3 };
        int majorityElement = FindMajorityElement(nums);

        if (majorityElement != -1)
        {
            Console.WriteLine($"The majority element is: {majorityElement}");
        }
        else
        {
            Console.WriteLine("No majority element found.");
        }
    }
}

How It Works:

  1. Candidate Selection:

    • As you loop through the array, you adjust the count based on the current number compared to the candidate.
    • This process finds a potential majority candidate by the end of the first loop.

  2. Verification:

    • The second loop counts how many times the candidate appears in the array to ensure it is indeed a majority element.

  3. Output:

    • If the count of the candidate is greater than half the length of the array, it is returned; otherwise, -1 is returned to indicate no majority element exists.

Time Complexity:

  • O(n): Each loop runs through the array once.
  • O(1): Only a constant amount of space is used for variables.

This method is efficient and particularly well-suited for large datasets where space and time efficiency is crucial.