Majority Element Moore's Voting Algorithm in DSA Javascript

Mental Model

Find the number that appears more than half the time by pairing off different numbers and canceling them out.

Analogy: Imagine a room where people form pairs of different opinions and leave together. The opinion left alone at the end is the majority opinion.

Array: [2, 2, 1, 1, 1, 2, 2]
Index:  0  1  2  3  4  5  6
Candidate: ↑ at start
Count: 1

Dry Run Walkthrough

Input: array: [2, 2, 1, 1, 1, 2, 2]

Goal: Find the majority element that appears more than half the time in the array

Step 1: Start with candidate = 2 (first element), count = 1

candidate=2, count=1, array=[2, 2, 1, 1, 1, 2, 2]

Why: We pick the first element as a starting candidate

Step 2: Look at next element 2, same as candidate, increment count to 2

candidate=2, count=2, array=[2, 2, 1, 1, 1, 2, 2]

Why: Same number increases confidence in candidate

Step 3: Next element 1 differs, decrement count to 1

candidate=2, count=1, array=[2, 2, 1, 1, 1, 2, 2]

Why: Different number cancels one occurrence of candidate

Step 4: Next element 1 differs, decrement count to 0

candidate=2, count=0, array=[2, 2, 1, 1, 1, 2, 2]

Why: Count zero means candidate lost support, need new candidate

Step 5: Count is zero, pick new candidate = 1, count = 1

candidate=1, count=1, array=[2, 2, 1, 1, 1, 2, 2]

Why: Reset candidate to current element

Step 6: Next element 1 same as candidate, increment count to 2

candidate=1, count=2, array=[2, 2, 1, 1, 1, 2, 2]

Why: Same number increases count

Step 7: Next element 2 differs, decrement count to 1

candidate=1, count=1, array=[2, 2, 1, 1, 1, 2, 2]

Why: Different number cancels one occurrence of candidate

Step 8: Next element 2 differs, decrement count to 0

candidate=1, count=0, array=[2, 2, 1, 1, 1, 2, 2]

Why: Count zero means candidate lost support, need new candidate

Step 9: Count is zero, pick new candidate = 2, count = 1

candidate=2, count=1, array=[2, 2, 1, 1, 1, 2, 2]

Why: Reset candidate to current element

Result:

Final candidate=2 with count>0, majority element is 2

Annotated Code

DSA Javascript

class MajorityElement {
  static findMajority(arr) {
    let candidate = null;
    let count = 0;
    for (const num of arr) {
      if (count === 0) {
        candidate = num; // reset candidate when count is zero
        count = 1;
      } else if (num === candidate) {
        count++; // same number increases count
      } else {
        count--; // different number decreases count
      }
    }
    return candidate;
  }
}

// Driver code
const arr = [2, 2, 1, 1, 1, 2, 2];
const majority = MajorityElement.findMajority(arr);
console.log(majority);

if (count === 0) { candidate = num; // reset candidate when count is zero count = 1; }

Reset candidate to current element when count drops to zero

else if (num === candidate) { count++; // same number increases count }

Increment count if current number matches candidate

else { count--; // different number decreases count }

Decrement count if current number differs from candidate

Output

2

Complexity Analysis

Time: O(n) because we scan the array once to find the candidate

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to counting frequencies with a map (O(n) time and O(n) space), Moore's Voting uses less memory and is faster in practice

Edge Cases

Array with one element

Returns that single element as majority

DSA Javascript

if (count === 0) {
  candidate = num; // reset candidate when count is zero
  count = 1;
}

Array where no element appears more than half

Algorithm still returns a candidate but it may not be a true majority; verification needed if required

DSA Javascript

return candidate;

Array with all elements the same

Returns that element as majority immediately

DSA Javascript

else if (num === candidate) {
  count++; // same number increases count
}

When to Use This Pattern

When you need to find an element that appears more than half the time without extra space, use Moore's Voting Algorithm because it efficiently cancels out minority elements.

Common Mistakes

Mistake: Not resetting the candidate when count reaches zero
Fix: Add a condition to reset candidate and count when count is zero

Mistake: Assuming the candidate is always the majority without verification
Fix: If problem requires, verify candidate count in a second pass

Summary

Finds the element that appears more than half the time by canceling out different elements.

Use when you want to find the majority element in linear time and constant space.

The key insight is pairing off different elements to leave the majority element as candidate.

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