Majority Element Moore's Voting Algorithm in DSA Typescript

Mental Model

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

Analogy: Imagine a room where people vote for their favorite color. Every time two people with different colors meet, they leave the room together. The color left at the end is the majority color.

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

Dry Run Walkthrough

Input: list: [2, 2, 1, 1, 1, 2, 2]

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

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

Candidate=2, Count=1

Why: Initialize candidate and count to start tracking majority

Step 2: Next element is 2, same as candidate, increment count

Candidate=2, Count=2

Why: Same element increases confidence in candidate

Step 3: Next element is 1, different from candidate, decrement count

Candidate=2, Count=1

Why: Different element cancels one occurrence of candidate

Step 4: Next element is 1, different from candidate, decrement count

Candidate=2, Count=0

Why: Count zero means candidate lost majority so far

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

Candidate=1, Count=1

Why: Reset candidate to current element when count hits zero

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

Candidate=1, Count=2

Why: Same element increases count

Step 7: Next element is 2, different from candidate, decrement count

Candidate=1, Count=1

Why: Different element cancels one count

Step 8: Next element is 2, different from candidate, decrement count

Candidate=1, Count=0

Why: Count zero means candidate lost majority again

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

Candidate=2, Count=1

Why: Reset candidate to current element

Result:

Candidate=2 with final count > 0, Majority element is 2

Annotated Code

DSA Typescript

class MajorityElement {
  static findMajority(nums: number[]): number | null {
    let candidate: number | null = null;
    let count = 0;

    for (const num of nums) {
      if (count === 0) {
        candidate = num; // reset candidate when count is zero
      }
      if (num === candidate) {
        count++; // increment count for same candidate
      } else {
        count--; // decrement count for different element
      }
    }

    // Verify candidate is majority
    let occurrence = 0;
    for (const num of nums) {
      if (num === candidate) {
        occurrence++;
      }
    }

    if (occurrence > Math.floor(nums.length / 2)) {
      return candidate;
    } else {
      return null; // no majority element
    }
  }
}

// Driver code
const input = [2, 2, 1, 1, 1, 2, 2];
const majority = MajorityElement.findMajority(input);
if (majority !== null) {
  console.log(`Majority element is ${majority}`);
} else {
  console.log("No majority element found");
}

if (count === 0) { candidate = num; }

Reset candidate when count drops to zero

if (num === candidate) { count++; } else { count--; }

Increase count if same element, else decrease count

for (const num of nums) { if (num === candidate) { occurrence++; } }

Count occurrences of candidate to verify majority

if (occurrence > Math.floor(nums.length / 2)) { return candidate; } else { return null; }

Return candidate if it appears more than half, else null

Output

Majority element is 2

Complexity Analysis

Time: O(n) because we scan the list twice: once to find candidate and once to verify

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

vs Alternative: Naive approach counts each element frequency using extra space O(n), Moore's algorithm uses constant space and linear time

Edge Cases

Empty array

Returns null since no elements exist

DSA Typescript

if (occurrence > Math.floor(nums.length / 2)) { return candidate; } else { return null; }

Array with one element

Returns that element as majority

DSA Typescript

if (count === 0) { candidate = num; }

No majority element present

Returns null after verification

DSA Typescript

if (occurrence > Math.floor(nums.length / 2)) { return candidate; } else { return null; }

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 verifying the candidate after the first pass
Fix: Add a second pass to count candidate occurrences and confirm it is majority

Mistake: Resetting candidate incorrectly or not resetting when count hits zero
Fix: Reset candidate exactly when count becomes zero during iteration

Summary

Finds the element that appears more than half the time in a list.

Use when you want to find majority element efficiently with O(1) space.

The key insight is canceling out pairs of different elements to isolate the majority.

Practice

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

easy

A. To find the smallest element in the array

B. To sort the array in ascending order

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

D. To reverse the array elements

Solution

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

   The algorithm is designed to find the majority element, which is the element that appears more than half the time in the array.

2. Step 2: Compare with other options

   Sorting, finding smallest element, or reversing the array are unrelated to the majority element problem.

3. Final Answer:

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

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 the most frequent element (may not be > n/2)
• Thinking it sorts the array
• Assuming it finds smallest or largest element

2. Which of the following TypeScript code snippets correctly initializes the variables for Moore's Voting Algorithm?

easy

A. let count = 1; let candidate = 0;

B. let count = null; let candidate = 1;

C. let candidate = 0; let count = null;

D. let count = 0; let candidate = null;

Solution

1. Step 1: Identify correct initial values for Moore's Voting Algorithm

   Count starts at 0 and candidate is initially null (no candidate chosen yet).

2. Step 2: Check each option's correctness

   let count = 0; let candidate = null; correctly sets count = 0 and candidate = null. Others have wrong initial values or types.

3. Final Answer:

   let count = 0; let candidate = null; -> Option D

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
• Setting candidate to 0 without context
• Using null for count which should be a number

3. What will be the output of the following TypeScript code using Moore's Voting Algorithm?

function majorityElement(nums: number[]): number {
  let count = 0;
  let 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. 2

B. null

C. 1

D. Error

Solution

1. Step 1: Trace the algorithm on input array

   Array: [2, 2, 1, 1, 1, 2, 2] - Start count=0, candidate=null - num=2: count=0, set candidate=2, count=1 - num=2: same candidate, count=2 - num=1: different, count=1 - num=1: different, count=0 - num=1: count=0, candidate=1, count=1 - num=2: different, count=0 - num=2: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   The final candidate is 2, which is the majority element appearing 4 times.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Majority element = 2 [OK]

Hint: Track count and candidate changes step-by-step [OK]

Common Mistakes:

• Returning the last element instead of candidate
• Not updating candidate when count is zero
• Confusing count increments and decrements

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

function majorityElement(nums: number[]): number {
  let count = 0;
  let candidate = 0;
  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }
    if (num === candidate) {
      count++;
    } else {
      count--;
    }
  }
  return candidate;
}

medium

A. Candidate should be initialized as null, not 0

B. No bug, code is correct

C. The if-else for count update is reversed

D. Count should start at 1, not 0

Solution

1. Step 1: Analyze the code logic

   Count=0 and candidate=0 initialization is correct. Since count starts at 0, the first iteration sets candidate to nums[0] before the count update. The initial candidate value is never used in comparisons, as it is always overwritten when count === 0.

2. Step 2: Verify other options

   A: Initializing to 0 works fine. B: Count must start at 0. C: Count update logic is correct (increment on match, decrement otherwise).

3. Final Answer:

   No bug, code is correct -> Option B

4. Quick Check:

   Initial candidate unused due to count=0 [OK]

Hint: With count=0, candidate init value is overwritten before use [OK]

Common Mistakes:

• Thinking candidate=0 causes issues if 0 not in array
• Believing count should start at 1
• Misinterpreting count update logic as reversed

5. Given an array where no element appears more than half the time, how can Moore's Voting Algorithm be adapted to confirm if a majority element exists?

hard

A. Run the algorithm to find candidate, then count its occurrences to verify majority

B. Return the candidate directly without verification

C. Sort the array and pick the middle element

D. Use a hash map to count all elements and pick the max

Solution

1. Step 1: Understand limitation of Moore's Voting Algorithm

   The algorithm finds a candidate but does not guarantee it is a majority if none exists.

2. Step 2: Verify candidate's count

   After finding candidate, count its occurrences in the array to confirm if it appears more than half the time.

3. Step 3: Compare other options

   Returning candidate directly may be wrong. Sorting or hash map are alternative methods but not adaptations of Moore's algorithm.

4. Final Answer:

   Run the algorithm to find candidate, then count its occurrences to verify majority -> Option A

5. Quick Check:

   Verify candidate count after algorithm [OK]

Hint: Verify candidate count after finding it to confirm majority [OK]

Common Mistakes:

• Assuming candidate is always majority without check
• Using sorting which is not Moore's algorithm
• Ignoring verification step