Moore's Voting Algorithm

Agenda:

  1. What is Moore's Voting Algorithm?
  2. Analogy
  3. Logic
  4. Why it works?
  5. Code

[1] What is Moore's Voting Algorithm?

Moore's Voting Algorithm, also known as the Boyer–Moore majority vote algorithm, is an efficient algorithm for finding the majority element in an array. 

It operates in linear time complexity O(N) and constant space complexity O(1), making it highly efficient for large datasets.

TC: O(N)

SC: O(1)

[2] Analogy

Consider an election scenario where different political parties receive votes from voters. The party with more than 50% of the votes can form the government. 

Similarly, in our array, we aim to identify the element that appears more than half of the time, analogous to the winning political party.

Think of this array as a collection of votes from the voters for different political parties.

Now as we know the party which has >50% votes can form the government.

So, our above question is analogous to this situation.

[3] Logic

In simple and easy terms:

We increment a count variable every time we see the vote from the majority party and decrement it whenever a vote from some other party is occurred, we can guarantee that, count>0.

Detailed Logic:

  1. Initialize a count variable and a majority variable to track the current majority element.
  2. Traverse the array, incrementing the count if the current element matches the majority element and decrementing otherwise.
  3. If the count becomes zero, update the majority element to the current element.
  4. By the end of the traversal, the majority variable holds the majority element.

[4] Why it works?

  • Moore's Voting Algorithm works because the majority element appears more than half of the time in the array. 
  • As we traverse the array, if the count becomes zero, it indicates that the previous majority element's frequency is equal to or less than the sum of the frequencies of the other elements encountered so far. 
  • Therefore, the next element becomes the majority element. Eventually, the final answer will always be the majority element.

[5] Code

Problem: https://leetcode.com/problems/majority-element/

Solution:

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        int majority,count=0;

        for(int i=0;i<nums.size();i++)

        {

            if(count)

            {

                count+=(nums[i]==majority ? 1 : -1);

            }

            else

            {

                majority=nums[i];

                count=1;

            }

        }

        return majority;

    }

};

Comments

Post a Comment

Popular posts from this blog

KMP Algorithm: Pattern Searching in Text

Agenda: Quick Intro Input Output Complexity Algo Logic Code Real-Life Use Cases Conclusion Sources for further reading 1. Quick Intro The Knuth-Morris-Pratt (KMP) algorithm is a classic string-searching algorithm used to find occurrences of a "pattern" string within a "text" string.  It was devised by Donald Knuth , James H. Morris , and Vaughan Pratt , hence the name KMP .  The key feature of the KMP algorithm is its ability to perform the search efficiently by avoiding unnecessary comparisons . 2. Input The KMP algorithm takes two inputs: Text (T) : The string in which we are searching for a pattern. Pattern (P) : The string we are searching for within the text. 3. Output Indices (I): Starting indices of all occurrences of the pattern in the text. If the pattern is not found, it returns an empty list. 4. Complexity Time Complexity :  O(n + m)   n ---> Length of the text. m ---> Length of the pattern. Sp...
Read more

Z-Function Algorithm: Substring Search

Agenda: Quick Intro Input Output Complexity Algo Logic C++ Code Real-Life use cases Practice Problem Conclusion Sources for further reading Quick Intro The Z-function is a powerful string-matching algorithm used for pattern matching and searching within a given string. Its primary purpose is to find all occurrences of a specified pattern in the text. Definition: Given a string s of length n, the Z-function produces an array Z where Z[i] represents the length of the longest substring starting from s[i] that is also a prefix of s. Input Text(T): The input to the Z-function algorithm is a single string T of length n . Output Z-Array(z): The output of the Z-function algorithm is an array Z of length n where each element Z[i] represents the length of the longest substring starting from the position i in T that matches a prefix of T . Complexity Time: O(n) Space: O(n) Where, n ---> length of input Text....
Read more

Back of the envelope estimations

# Agenda: Overview Common inputs in a requests-per-second (RPS) calculation Example of RPS / QPS calculation Techniques to simplify the calculations Handy conversion Table Capacity or Storage Planning Conclusion # Overview: Back-of-the-envelope math is a very  useful tool in our system design toolbox. In this article, we will go over how and when to use  it, and share some tips on using it effectively. Let’s dive right in. Experienced developers use back-of-the-envelope  math to quickly sanity-check a design. In these cases, absolute accuracy is not that important . Usually, it is good enough to get  within an order of magnitude or two of the actual numbers we are looking for. For example, if the math says at our scale our web  service needs to handle 1M requests per second, and each web server could only handle about 10K  requests per second, we learn two things quickly:     1) W e learn that we will need to cluster of web  servers, with a l...
Read more