. Day 7 - Challenge 1 - Find Most Common Number Skip to main content

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

 

Labels:

Comments

Post a Comment

Popular posts from this blog

Day 9 - Challenge 1 - Product of Array Except Self

Solving the "Product of Array Except Self" Problem in JavaScript Are you ready to dive into a common coding challenge that not only tests your programming skills but also sharpens your problem-solving mindset? If you're up for the challenge, let's tackle the "Product of Array Except Self" problem together using JavaScript. This problem requires us to return an array where each element at index i is the product of all the elements in the original array except the one at index i . Understanding the Problem:   Imagine you're given an array of integers, let's call it nums . Your task is to create a new array where the value at index i in this new array is the product of all the elements in nums , except the one at index i . In other words, you're calculating the product of all the elements to the left of nums[i] and the product of all the elements to the right of nums[i] , and then multiplying these two products to get the final value at index i ...
Post a Comment
Read more

Day 9 - Challenge 2 - Reverse Linked List

Reversing a Singly Linked List in JavaScript: An In-Place Approach Introduction:   Singly linked lists are fundamental data structures in computer science that consist of a sequence of nodes, each containing data and a reference to the next node in the list. Reversing a singly linked list is a classic problem that challenges programmers to manipulate pointers effectively to achieve the desired outcome. In this blog post, we'll explore the problem of reversing a singly linked list using an in-place approach and provide a step-by-step solution in JavaScript. Problem Statement:   Given the head of a singly linked list, our task is to reverse the list in-place and return its new head. In other words, we need to modify the pointers of the nodes in such a way that the direction of the linked list is reversed. Solution Approach:   To solve this problem, we will iterate through the linked list while maintaining three pointers: previous , current , and next . The previous pointer...
Post a Comment
Read more

Day 8 - Challenge 2 - Move Zeroes to the End

Moving Zeroes to the End: A JavaScript Solution Introduction:   When working with arrays, there are often times when we need to manipulate their elements to achieve a specific goal. One common problem is moving all zeroes to the end of an array while keeping the order of non-zero elements unchanged. In this blog post, we will explore an elegant solution to this problem using JavaScript. We'll discuss the problem statement, the approach we'll take, and provide a step-by-step guide to implementing the solution. The Problem:   Given an array of integers, the task is to move all zeroes to the end of the array while maintaining the relative order of the non-zero elements. This means that after rearranging the array, all the zeroes should be at the end, and the order of the non-zero elements should remain the same. The Approach:   To solve this problem, we can utilize a two-pointer approach. We'll maintain two pointers, one for iterating through the array and another for keepin...
Post a Comment
Read more