Open Bookshelf Cover Page
Preface
Getting Started
- Prerequisites
- Introduction
The PEDAC Approach to Problem Solving
Introduction to Data Structures and Algorithms
Sorting Algorithms
Pointer-Based Mental Models
Binary Search
Linked Lists
Stacks & Queues
Conclusion
- Conclusion & Next Steps
Share on

Practice: Find a Majority Element

In this assignment, we'll practice the techniques learned so far using the "Find a Majority Element" problem. Try to solve the problem using the naive (brute-force) approach first, and then see if you can optimize the solution.

Problem Description

// Given an array of numbers, return its majority element.

// The majority element is the value in the array that appears
// as at least half of the elements in the array.

// It is guaranteed that only one majority element exists in the array.

// Test Cases:

console.log(findMajority([6, 4, 4, 6, 4]) === 4);
console.log(findMajority([4, 5, 2, 5, 5, 5, 1]) === 5);
console.log(findMajority([1, 2, 1, 2, 2, 1, 2]) === 2);
console.log(findMajority([1, 2, 3, 1, 4, 4, 1, 1]) === 1);
console.log(findMajority([5, 5, 5]) === 5);

// All test cases should log true

Walkthrough & Solution

Let's go through the example array [6, 4, 4, 6, 4] step by step.

Step 1: Create an empty Map called counts. This Map will store the elements from the array as keys and their corresponding counts as values. Set the majorityCount variable to Math.ceil(nums.length / 2), which is 3 in this case.

Step 2: The first element we encounter is 6. Since the element doesn't exist in the counts, we add it to the counts map with a count of 1. The counts map is now {6: 1}. Since the count 1 is less than 3, we continue to the next element.

Step 3: The second element is 4. Since the element doesn't exist in the counts, we add it to the counts map with a count of 1. The counts map is now {6: 1, 4: 1}. Since the count 1 is less than 3, we continue to the next element.

Step 4: The third element is 4 again. Since the element already exists in the counts, we update the count of 4 to 2 (increment by 1). The counts map is now {6: 1, 4: 2}. Since the count 2 is less than 3, continue to the next element.

Step 5: The fourth element is 6. Since the element already exists in the counts, we update the count of 6 to 2 (increment by 1). The counts map is now {6: 2, 4: 2}. Once again, since the count 2 is less than 3, we continue to the next element.

Step 6: The fifth element is 4 again. Since the element already exists in the counts, we update the count of 4 to 3 (increment by 1). The counts map is now {6: 2, 4: 3}. Since the count for 4, 3 is equal to our majorityCount, 3, we have found the majority element, which is 4.

First, the brute-force quadratic solution using two nested loops:

function findMajority(nums) {
  const n = nums.length;
  const majorityCount = Math.ceil(n / 2);

  for (let i = 0; i < n; i++) {
    let count = 0;
    for (let j = 0; j < n; j++) {
      if (nums[j] === nums[i]) {
        count++;
      }
    }
    if (count >= majorityCount) {
      return nums[i];
    }
  }
}

The optimal linear solution using a Map.

function findMajority(nums) {
  const counts = new Map();
  const majorityCount = Math.ceil(nums.length / 2);

  for (let num of nums) {
    if (counts.has(num)) {
      counts.set(num, counts.get(num) + 1);
    } else {
      counts.set(num, 1);
    }

    if (counts.get(num) >= majorityCount) {
      return num;
    }
  }
}