Majority Element: Two Algorithms Compared for Efficiency

Algorithms often balance trade-offs between speed, memory, and simplicity. When tasked with finding the majority element in an array, developers can choose between a straightforward approach or a highly optimized one that minimizes resource usage. Both methods guarantee accuracy, but their efficiency varies significantly depending on the scenario.

The Majority Element Problem Explained

The majority element in an array is defined as the value that appears more than half the time. For example, in the array [2, 4, 2, 2, 4, 4, 4], the element 4 qualifies because it appears four times out of seven total elements. This problem, commonly found in coding interviews, tests a programmer’s ability to analyze data efficiently.

Approach 1: Counting Frequencies with a Hash Map

The first solution uses a hash map to track how often each element appears in the array. This method is intuitive and works well for small datasets or when clarity is prioritized over optimization.

The process involves two main steps:

• Step 1: Count occurrences

Iterate through the array, updating a frequency map where each key is an element and its value is the count of appearances.

• Step 2: Identify the majority element

After counting, scan the map to find the element whose frequency exceeds half the array’s length.

Here’s how the frequency map is implemented:

function majorityElement(nums) {
  const counts = new Map();
  for (const num of nums) {
    counts.set(num, (counts.get(num) ?? 0) + 1);
  }
  for (const [num, count] of counts) {
    if (count > nums.length / 2) return num;
  }
}

For the example array [2, 4, 2, 2, 4, 4, 4], the map would store 2: 3 and 4: 4. Since 4 appears more than 7 / 2 times, it is returned as the majority element.

Time and Space Complexity Analysis

• Time complexity: O(n)

The solution requires two passes through the array—one for counting and another for checking frequencies—resulting in linear time.

• Space complexity: O(n)

The hash map grows with the number of unique elements, consuming additional memory proportional to the input size.

Approach 2: Boyer-Moore Algorithm for Linear Time and Constant Space

Developed in 1981 by Robert S. Boyer and J Strother Moore, the Boyer-Moore Majority Vote Algorithm optimizes space usage while maintaining linear time complexity. This method is ideal for large datasets where memory efficiency is critical.

The algorithm relies on two key variables:

• `candidate`: Tracks the current potential majority element.
• `count`: Represents confidence in the candidate, incremented for matches and decremented for mismatches.

The logic follows these steps:

1. Initialize candidate as null and count as 0.
2. Iterate through the array:

• If count is 0, set candidate to the current element.
• Adjust count based on whether the current element matches the candidate.

Here’s the implementation:

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;
}

For the array [2, 4, 2, 2, 4, 4, 4], the algorithm processes elements as follows:

| Element | count === 0? | candidate | count | |---------|----------------|-------------|---------| | 2 | Yes | 2 | 1 | | 4 | No | 2 | 0 | | 2 | Yes | 2 | 1 | | 2 | No | 2 | 2 | | 4 | No | 2 | 1 | | 4 | No | 2 | 0 | | 4 | Yes | 4 | 1 |

The final candidate is 4, which is returned as the majority element.

Time and Space Complexity Analysis

• Time complexity: O(n)

The algorithm processes the array in a single pass.

• Space complexity: O(1)

Only two variables are used, regardless of input size, making it highly memory-efficient.

Choosing the Right Approach

Both methods effectively solve the problem, but their suitability depends on the context:

• Frequency map: Best for small datasets or when readability is prioritized over performance.
• Boyer-Moore algorithm: Ideal for large-scale applications where memory usage must be minimized.

As algorithms continue to evolve, understanding these trade-offs empowers developers to select the most appropriate solution for their specific needs.