[FEATURE REQUEST] Add Moore's Voting Algorithm

[SubhradeepBasu18]

What would you like to Propose?

The problem is to find the majority element in an array using Moore's Voting Algorithm. A majority element is an element that appears more than n/2 times in the array, where n is the total number of elements. Moore's Voting Algorithm efficiently solves this problem in O(n) time and O(1) space.

Example: Input: [2, 2, 1, 1, 1, 2, 2] Output: 2

Explanation:

• In the first phase, the algorithm selects 2 as the majority candidate.
• In the second phase, the algorithm checks if 2 appears more than 3 times (7/2 = 3.5), which it does (appears 4 times), making it the majority element.

Issue details

The algorithm works by:

• Selecting a candidate element using a voting process.
• Verifying whether the candidate is the actual majority element by counting its occurrences.

Additional Information

No response

[PriyamUttam-Dev]

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.