Majority Element

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.

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)

```js
/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
  return nums;
};
```

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".

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:

[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.

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.

function majorityElement(nums) {
  const hash = {};
  // we keep a local max variable to track what
  // element is in the majority
  let max = 0,
    val;

  // iterate through
  for (let i = 0; i < nums.length; i++) {
    // increment or initialize the num as a key
    if (hash[nums[i]]) {
      hash[nums[i]]++;
    } else {
      hash[nums[i]] = 1;
    }

    if (hash[nums[i]] > max) {
      max = hash[nums[i]];
      val = nums[i];
    }
  }

  return val;
}

def majority_element(nums):
  hash = {}
  # we keep a local max variable to track what
  # element is in the majority
  max, val = 0, None

  for i in range(0, len(nums)):
    # increment or initialize the num as a key
    if nums[i] in hash:
      hash[nums[i]] += 1
    else:
      hash[nums[i]] = 1

    if hash[nums[i]] > max:
      max = hash[nums[i]]
      val = nums[i]

  return val

print(majority_element([4, 2, 2, 3, 2]))

public class Main { 
  public static void main(String[] args) { 
    int[] nums = {4, 2, 2, 3, 2};
    System.out.println(majorityElement(nums));
  }

  public static int majorityElement(int[] nums) {
    HashMap<Integer, Integer> hash = new HashMap<>();
    int max = 0;
    int val = 0;

    for (int i = 0; i < nums.length; i++) {
      if (hash.containsKey(nums[i])) {
        hash.put(nums[i], hash.get(nums[i]) + 1);
      } else {
        hash.put(nums[i], 1);
      }

      if (hash.get(nums[i]) > max) {
        max = hash.get(nums[i]);
        val = nums[i];
      }
    }
    return val;
  }
}

def majority_element(nums)
  hash = {}
  # we keep a local max variable to track what
  # element is in the majority
  max, val = 0, nil

  nums.each do |i|
    # increment or initialize the num as a key
    if hash.has_key?(i)
      hash[i] += 1
    else
      hash[i] = 1
    end

    if hash[i] > max
      max = hash[i]
      val = i
    end
  end

  return val
end

puts majority_element([4, 2, 2, 3, 2])

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.