Majority Element Moore's Voting Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Majority Element in an array?

The Majority Element is the element that appears more than half the times in the array (more than n/2 times).

intermediate

What is the main idea behind Moore's Voting Algorithm?

Moore's Voting Algorithm finds the majority element by maintaining a candidate and a count. It increases the count when the same element appears and decreases it when a different element appears. The candidate at the end is the majority element if it exists.

intermediate

Why does Moore's Voting Algorithm work for finding the majority element?

Because the majority element appears more than half the times, it will remain as the candidate after canceling out all other elements with different values.

beginner

What is the time complexity of Moore's Voting Algorithm?

The time complexity is O(n), where n is the number of elements in the array, because it scans the array only once.

intermediate

What should you do after finding the candidate with Moore's Voting Algorithm?

You should verify if the candidate is actually the majority element by counting its occurrences in the array, because the algorithm assumes a majority element exists but it might not.

What does Moore's Voting Algorithm maintain while scanning the array?

A A hash map of element frequencies

B A sorted list of elements

C A candidate element and a count

D A stack of elements

Moore's Voting Algorithm keeps track of a candidate and a count to find the majority element efficiently.

What happens to the count when the current element is different from the candidate?

A Count decreases by 1

B Count resets to zero

C Count increases by 1

D Count doubles

The count decreases by 1 when the current element differs from the candidate.

If the count reaches zero, what does Moore's Voting Algorithm do next?

A Stops the algorithm

B Resets the candidate to the current element and count to 1

C Ignores the current element

D Returns no majority element

When count is zero, the algorithm picks the current element as the new candidate and resets count to 1.

What is the worst-case time complexity of Moore's Voting Algorithm?

A O(1)

B O(n log n)

C O(n^2)

D O(n)

The algorithm runs in linear time O(n) because it scans the array twice at most.

Why do we need to verify the candidate after running Moore's Voting Algorithm?

A Because the candidate might not be the majority element if none exists

B Because the algorithm always returns the wrong element

C Because the candidate is always the smallest element

D Because the algorithm sorts the array

Verification is needed because the algorithm assumes a majority element exists, but if it doesn't, the candidate might not be valid.

Explain how Moore's Voting Algorithm finds the majority element step-by-step.

Think about how the algorithm cancels out different elements.

Describe why Moore's Voting Algorithm is efficient compared to counting frequencies with a hash map.

Focus on time and space complexity differences.

Practice

1. What is the main purpose of Moore's Voting Algorithm in arrays?

easy

A. To find the element that appears more than half the time

B. To sort the array in ascending order

C. To find the smallest element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand the problem Moore's Voting Algorithm solves

   It is designed to find the majority element, which is the element that appears more than half the times in the array.

2. Step 2: Compare with other options

   Sorting, finding smallest, or reversing are unrelated to majority element detection.

3. Final Answer:

   To find the element that appears more than half the time -> Option A

4. Quick Check:

   Majority element = element appearing > n/2 times [OK]

Hint: Majority element appears more than half the array length [OK]

Common Mistakes:

• Confusing majority element with most frequent element
• Thinking it sorts the array
• Assuming it finds smallest or largest element

2. Which of the following is the correct initialization step in Moore's Voting Algorithm in JavaScript?

easy

A. let count = 1, candidate = 0;

B. let count = 0, candidate = null;

C. let candidate = 0, count = null;

D. let count = null, candidate = 1;

Solution

1. Step 1: Identify correct variable initialization

   Moore's Voting Algorithm starts with count = 0 and candidate = null (or undefined) to indicate no candidate chosen yet.

2. Step 2: Check other options for correctness

   Options A, C, and D initialize count or candidate incorrectly, which can cause logic errors.

3. Final Answer:

   let count = 0, candidate = null; -> Option B

4. Quick Check:

   Initialize count=0 and candidate=null [OK]

Hint: Start count at 0 and candidate as null before loop [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Assigning candidate a number before selection
• Swapping count and candidate initialization

3. What will be the output of the following JavaScript code?

function majorityElement(nums) {
  let count = 0, candidate = null;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate) ? 1 : -1;
  }
  return candidate;
}
console.log(majorityElement([2,2,1,1,1,2,2]));

medium

A. Error

B. 1

C. null

D. 2

Solution

1. Step 1: Trace the loop and candidate updates

   Initial count=0, candidate=null. Iteration updates candidate and count as follows:
   - num=2: count=0, candidate=2, count=1
   - num=2: count=1, same candidate, count=2
   - num=1: count=2, different candidate, count=1
   - num=1: count=1, different candidate, count=0
   - num=1: count=0, candidate=1, count=1
   - num=2: count=1, different candidate, count=0
   - num=2: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   The candidate is 2 after the loop ends, which is the majority element.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Majority element found = 2 [OK]

Hint: Track count changes; candidate updates when count hits zero [OK]

Common Mistakes:

• Assuming candidate never changes
• Confusing count increments and decrements
• Returning count instead of candidate

4. Identify the bug in this Moore's Voting Algorithm implementation:

function majorityElement(nums) {
  let count = 1, candidate = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === candidate) {
      count++;
    } else {
      count--;
      if (count === 0) {
        candidate = nums[i];
        count = 1;
      }
    }
  }
  return candidate;
}

medium

A. Initialization of count should be 0, not 1

B. Candidate should be initialized to null, not nums[0]

C. No bug, code is correct

D. Loop should start from i = 0, not i = 1

Solution

1. Step 1: Analyze initialization and loop

   Starting count at 1 and candidate as nums[0] is a valid approach. Loop starts at i=1 to compare remaining elements.

2. Step 2: Check logic inside loop

   Count increments if current equals candidate, else decrements. When count hits zero, candidate updates and count resets to 1. This matches Moore's Voting Algorithm logic.

3. Final Answer:

   No bug, code is correct -> Option C

4. Quick Check:

   Initialization and loop logic correct [OK]

Hint: Starting count=1 with first element candidate is valid [OK]

Common Mistakes:

• Thinking count must start at 0
• Assuming candidate must be null initially
• Starting loop at wrong index

5. Given an array where no element appears more than half the time, what will Moore's Voting Algorithm return?
Example: [1, 2, 3, 4]

hard

A. An incorrect majority element

B. null or undefined (no majority element)

C. The first element of the array

D. The element with the highest frequency

Solution

1. Step 1: Understand Moore's Voting Algorithm assumption

   The algorithm assumes a majority element exists (appears more than half the time). If none exists, it still returns a candidate but it may not be a true majority.

2. Step 2: Analyze example array [1, 2, 3, 4]

   No element appears more than 2 times (half of 4). The algorithm will return a candidate but it is not a valid majority element.

3. Final Answer:

   An incorrect majority element -> Option A

4. Quick Check:

   No majority means algorithm returns wrong candidate [OK]

Hint: Algorithm assumes majority exists; else result may be wrong [OK]

Common Mistakes:

• Assuming algorithm returns null if no majority
• Thinking it returns highest frequency element always
• Believing it returns first element by default