Day 7 - Challenge 1 - Find Most Common Number

Finding the Most Common Number: Moore's Voting Algorithm in JavaScript

Introduction

In the realm of algorithmic problem-solving, the Majority Element problem holds a significant place. It involves finding an element in an array that appears more than half of the time. With a guaranteed existence of such an element, solving this problem requires efficient techniques. In this blog post, we'll explore the Majority Element problem, understand its importance, and implement a JavaScript program to solve it.

Understanding the Problem

The Majority Element problem can be formally stated as follows: Given an array of integers, find the element that appears more than n/2 times, where n is the length of the array. The problem can be approached in various ways, and one of the crucial aspects is to find a solution with a time complexity better than O(n^2).

Boyer-Moore Voting Algorithm

One of the most efficient ways to solve the Majority Element problem is by using the Boyer-Moore Voting Algorithm. The algorithm is based on the observation that if you cancel out each occurrence of a majority element with an occurrence of any other element, the majority element will still remain as the majority.

Algorithm Steps:

1. Initialize two variables: majority and count, where majority stores the potential majority element, and count keeps track of its frequency.
2. Iterate through the array:
   • If count is 0, set the current element as majority and increment count.
   • If the current element is equal to majority, increment count.
   • If the current element is not equal to majority, decrement count.
3. After iterating, majority will hold the potential majority element.
4. Iterate through the array again to count the occurrences of majority and ensure it is indeed the majority element.

JavaScript Implementation

Here's a JavaScript program that implements the Boyer-Moore Voting Algorithm to solve the Majority Element problem:

 

function findMajorityElement(nums) {
    let majority = nums[0];
    let count = 1;

    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            majority = nums[i];
            count = 1;
        } else if (nums[i] === majority) {
            count++;
        } else {
            count--;
        }
    }

    // Verify if majority is indeed the majority element
    count = 0;
    for (let num of nums) {
        if (num === majority) {
            count++;
        }
    }

    if (count > nums.length / 2) {
        return majority;
    } else {
        return -1; // No majority element (this should not happen according to the problem statement)
    }
}

// Example usage
const nums = [2, 2, 3, 2, 4, 2, 2];
const majorityElement = findMajorityElement(nums);
console.log("Majority Element:", majorityElement);

Demo

Majority Element Detection

Conclusion

The Majority Element problem demonstrates the importance of efficient algorithms in solving real-world challenges. With the Boyer-Moore Voting Algorithm and a concise JavaScript implementation, we can efficiently identify the majority element in an array. This problem not only enhances algorithmic thinking but also showcases how to optimize solutions for large datasets.

Other Challenges:

1. Day 4 Challenges
2. Day 5 Challenges
3. Day 6 Challenges