Mark As Completed Discussion

Good morning! Here's our prompt for today.

Suppose we're given an array of numbers like the following:

[4, 2, 4]

Could you find the majority element? A majority is defined as "the greater part, or more than half, of the total. It is a subset of a set consisting of more than half of the set's elements."

Let's assume that the array length is always at least one, and that there's always a majority element.

In the example above, the majority element would be 4.

Description

Constraints

  • Length of the array <= 100000
  • The array will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

We'll now take you through what you need to know.

How do I use this guide?

A lot of folks get tripped up by the majority part of this problem. The majority element is not the number with the most occurrences, but rather, it's the number value with >= 50% of "occurrences".

Step Two

The brute force solution would be manually iterate through and count the appearances of each number in a nested for-loop, like such: given an array [4, 2, 4]:

  1. iterate through for 4s, find 2 counts of 4
  2. iterate through for 2s, find 1 count of 2
  3. Realize that 2 > 3/2 (over half), so return 4

This is an O(n^2) solution because it would require passing through each number, and then at each number scanning for a count.

A better way to do this is to take advantage of the property of a majority element that it consists of more than half of the set's elements.

What do I mean by this? Let's take another example, [4, 2, 2, 3, 2].

2 is obviously the majority element in the example from a visual scan, but how can we tip the algorithm off to this? Well, suppose we sorted the array:

Solutions

[2, 2, 2, 3, 4]

Notice that if we hone in on index 2, that we see another 2. This is expected-- if we sort an array of numbers, the majority element will represent at least 50% of the elements, so it will always end up at the Math.floor(nums.length / 2)th index.

Depending on the sorting algorithm, this technique is usually O(n * log n) and requires either O(1) space if the sort is in-place, or O(n) space if not.

Another Method

Yet another way to solve this is to use the speed of a hash map! Hash maps allow access/look-ups in constant time, and its keys are guaranteed to be unique.

Solutions

Thus, we can iterate through [2, 2, 2, 3, 4], and store each unique value as a key, and its attached value being the count. Each time we pass it, we increment its count, and use that information to relay we've got a current majority candidate.

1function majorityElement(nums) {
2  const hash = {};
3  // we keep a local max variable to track what
4  // element is in the majority
5  let max = 0,
6    val;
7
8  // iterate through
9  for (let i = 0; i < nums.length; i++) {
10    // increment or initialize the num as a key
11    if (hash[nums[i]]) {
12      hash[nums[i]]++;
13    } else {
14      hash[nums[i]] = 1;
15    }
16
17    if (hash[nums[i]] > max) {
18      max = hash[nums[i]];
19      val = nums[i];
20    }
21  }
22
23  return val;
24}

The time complexity of this solution is O(n) as it requires just one pass through the array, but has a space complexity of O(n) since it needs to maintain an auxiliary hash table.

One Pager Cheat Sheet

  • The majority element of an array of length 100000, containing integer values between -1000000000 and 1000000000, can be found in O(n) time and O(n) space.
  • The majority element is not the number with the most occurrences, but rather the one with more than 50% of the total "occurrences".
  • By using a hash map to store unique values and their count, it is possible to find the majority element with an O(n) time complexity and O(n) space complexity.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.