[FEATURE REQUEST] Add Moore's Voting Algorithm #5636

[PriyamUttam-Dev]

What would you like to Propose?

Moore's Voting Algorithm

Moore's Voting Algorithm is an efficient algorithm for finding the majority element in an array, where the majority element is defined as an element that appears more than half the time.

Key Idea:

The algorithm maintains two variables: candidate and count.
candidate stores the current candidate for the majority element.
count keeps track of the count of the current candidate.
Iterate through the array:
If count is 0, set candidate to the current element and increment count.
If the current element is equal to candidate, increment count.
Otherwise, decrement count.
After iterating through the array, check if candidate appears more than half the time. If so, it's the majority element; otherwise, there is no majority element.
Implementation in Java:

Java
import java.util.Arrays;

public class MajorityElement {
public static int findMajorityElement(int[] nums) {
int candidate = nums[0];
int count = 1;

    for (int i = 1; i < nums.length;   

i++) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] == candidate) {
count++;
} else {
count--;  

        }
    }

    // Verify if candidate is the majority element
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }

    if (count > nums.length / 2) {
        return candidate;
    } else {
        return   

-1; // No majority element found
}
}

public static void main(String[] args) {
    int[] nums   

= {2, 1, 2, 1, 2, 2, 1};
int majorityElement = findMajorityElement(nums);

    if (majorityElement != -1) {
        System.out.println("Majority element: " + majorityElement);
    } else {
        System.out.println("No majority element   

found");  

    }
}

}

Explanation:

The findMajorityElement method takes an integer array nums as input and returns the majority element or -1 if no majority element exists.
The algorithm follows the steps described above, maintaining candidate and count.
After iterating through the array, a second pass is performed to verify if candidate is indeed the majority element by counting its occurrences.
If count is greater than half the size of the array, candidate is the majority element.
Time Complexity:

The algorithm has a time complexity of O(n), where n is the size of the input array. This is because it involves two passes through the array.
Key Points:

Moore's Voting Algorithm is efficient and easy to implement.
It's applicable to finding the majority element in an array where the majority element appears more than half the time.
The algorithm can be adapted to other scenarios where a dominant element needs to be identified.

Issue details

The algorithm maintains two variables: candidate and count.
candidate stores the current candidate for the majority element.
count keeps track of the count of the current candidate.
Iterate through the array:
If count is 0, set candidate to the current element and increment count.
If the current element is equal to candidate, increment count.
Otherwise, decrement count.
After iterating through the array, check if candidate appears more than half the time. If so, it's the majority element; otherwise, there is no majority element.
Implementation in Java:

Java
import java.util.Arrays;

public class MajorityElement {
public static int findMajorityElement(int[] nums) {
int candidate = nums[0];
int count = 1;

    for (int i = 1; i < nums.length;   

i++) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] == candidate) {
count++;
} else {
count--;  

        }
    }

    // Verify if candidate is the majority element
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }

    if (count > nums.length / 2) {
        return candidate;
    } else {
        return   

-1; // No majority element found
}
}

public static void main(String[] args) {
    int[] nums   

= {2, 1, 2, 1, 2, 2, 1};
int majorityElement = findMajorityElement(nums);

    if (majorityElement != -1) {
        System.out.println("Majority element: " + majorityElement);
    } else {
        System.out.println("No majority element   

found");  

    }
}

}

Explanation:

The findMajorityElement method takes an integer array nums as input and returns the majority element or -1 if no majority element exists.
The algorithm follows the steps described above, maintaining candidate and count.
After iterating through the array, a second pass is performed to verify if candidate is indeed the majority element by counting its occurrences.
If count is greater than half the size of the array, candidate is the majority element.
Time Complexity:

The algorithm has a time complexity of O(n), where n is the size of the input array. This is because it involves two passes through the array.
Key Points:

Moore's Voting Algorithm is efficient and easy to implement.
It's applicable to finding the majority element in an array where the majority element appears more than half the time.
The algorithm can be adapted to other scenarios where a dominant element needs to be identified.

Additional Information

No response

[arpit5220]

Hi @PriyamUttam-Dev could you assign me this issue.

[leochirinos10]

Hi @PriyamUttam-Dev , could I get this issue assigned to me?

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!