Majority Element Moore's Voting Algorithm in DSA Javascript - Execution Trace

Concept Flow - Majority Element Moore's Voting Algorithm

Initialize candidate and count

↓

For each element in array

↓

Is count zero?

Yes→Set candidate to current element

↓

Compare current element with candidate

↓

Increment count

↓

Decrement count

↓

End of array

↓

Return candidate as majority element

The algorithm scans the array once, keeping track of a candidate and a count. When count is zero, it picks a new candidate. It increments count if the current element matches the candidate, otherwise decrements count. At the end, the candidate is the majority element.

Execution Sample

DSA Javascript

function majorityElement(nums) {
  let candidate = null;
  let count = 0;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate) ? 1 : -1;
  }
  return candidate;
}

This code finds the majority element in the array using Moore's Voting Algorithm.

Execution Table

Step	Operation	Current Element	Candidate Before	Count Before	Candidate After	Count After	Visual State
1	Initialize	N/A	null	0	null	0	[]
2	Process element	3	null	0	3	1	[3]
3	Process element	3	3	1	3	2	[3,3]
4	Process element	4	3	2	3	1	[3,3,4]
5	Process element	2	3	1	3	0	[3,3,4,2]
6	Process element	4	3	0	4	1	[3,3,4,2,4]
7	Process element	4	4	1	4	2	[3,3,4,2,4,4]
8	Process element	4	4	2	4	3	[3,3,4,2,4,4,4]
9	End	N/A	4	3	4	3	[3,3,4,2,4,4,4]

💡 Reached end of array; candidate 4 with count 3 is returned as majority element

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
candidate	null	3	3	3	3	4	4	4	4
count	0	1	2	1	0	1	2	3	3

Key Moments - 3 Insights

Why do we reset the candidate when count becomes zero?

When count is zero (see step 5), it means the previous candidate lost majority support. We pick the current element as a new candidate to check if it can be the majority. This is shown in execution_table row 6.

Why do we increment count when the current element matches the candidate?

Incrementing count (steps 2,3,7,8) means the candidate is supported by the current element. This helps track if the candidate remains majority. See execution_table rows 2,3,7,8 where count increases.

What happens if no majority element exists?

Moore's Voting Algorithm assumes a majority element exists. If none exists, the candidate at the end may not be a true majority. Verification requires a second pass. This example assumes majority exists.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the candidate and count after processing element 2?

A Candidate: 3, Count: 1

B Candidate: 2, Count: 1

C Candidate: 3, Count: 0

D Candidate: null, Count: 0

💡 Hint

Check execution_table row 5 columns 'Candidate After' and 'Count After'

At which step does the candidate change from 3 to 4?

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look at 'Candidate After' column in execution_table rows 5 and 6

If the array started with [4,4,4,...] instead of [3,3,4,...], what would be the candidate after step 3?

A 4

B 3

C null

D 2

💡 Hint

Refer to variable_tracker for candidate changes after each step

Concept Snapshot

Moore's Voting Algorithm finds majority element in O(n) time.
Initialize candidate = null, count = 0.
For each element:
  If count == 0, set candidate = element.
  If element == candidate, count++ else count--.
Return candidate at end.

Full Transcript

This visualization shows Moore's Voting Algorithm step-by-step. We start with no candidate and count zero. As we scan the array, if count is zero, we pick the current element as candidate. If the current element matches candidate, we increase count; otherwise, we decrease count. When count reaches zero, the candidate is reset. At the end, the candidate is the majority element. The execution table tracks candidate and count changes for each element. Key moments explain why candidate resets and count increments. The quiz tests understanding of candidate and count changes during execution.

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