Leetcode 169 asks us to identify the majority element in a given array. The majority element is defined as the element that appears more than n / 2 times. We are told that we can assume such an element always exists.

For both approaches we will use the following value:

• nums = [2, 4, 2, 2, 4, 4, 4]

Approach 1: Naive (Frequency Map)

This approach uses a Map to count the frequency of each element in the array.

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

Our first step is to create the Map which will serve as our frequency map.

const counts = new Map();

The next step will require the use of a for loop. We will loop through the input array nums and count the number of occurrences of each value, writing that as a key/value pair to our frequency map, counts. The key will be the element from nums, and the value will be the frequency of times it appears.

for (const num of nums) {
  counts.set(num, (counts.get(num) ?? 0) + 1);
}

This for loop works by looking at each element in nums and calling .set() to store a value. The value that ends up being set depends on what .get() returns. Here's how .get() works:

• We attempt to get the current count for this number from counts. There are only two possible outcomes - either we have seen this number before, or we haven't:
  • If we have seen it before, .get() returns its current count and we increment by 1.
  • If we haven't seen it before, .get() returns undefined. The ?? operator (nullish coalescing) catches that and defaults it to 0, then we increment by 1 to initialize the count.

The next step involves another for loop. Because this loop is separate from the first rather than nested inside it, we are still O(n) overall - two sequential O(n) loops add up to O(n), not O(n²).

for (const [num, count] of counts) {
  if (count > nums.length / 2) return num;
}

In this for loop we iterate over our frequency map's key/value pairs one by one and compare each frequency to nums.length / 2.

Using our example array:

nums = [2, 4, 2, 2, 4, 4, 4]

counts would look like this:

counts = [[2, 3], [4, 4]]

We compare the value in the first key/value pair, which is 3, to nums.length / 2:

3 > (7 / 2) ->
3 > 3.5 = FALSE

We then perform the same operation on the next key/value pair:

4 > 7 / 2 ->
4 > 3.5 = TRUE

Once we find a value that returns true we know this is our majority element, and we return num.

Time complexity: O(n)

Two sequential loops, each O(n). Two separate O(n) loops add up to O(n), not O(n²).

Space complexity: O(n)

The Map grows proportionally to the number of unique elements in the array.

Approach 2: Optimized (Boyer-Moore Majority Vote Algorithm)

The Boyer-Moore Majority Vote Algorithm, developed by Robert S. Boyer and J Strother Moore in 1981, finds the majority element in a sequence using linear time and constant memory - making it a natural fit for this problem.

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

Step 1

We begin by initializing a variable candidate - this is our current best guess for the majority element, and we initialize it to null.

let candidate = null;

We initialize a second variable count. This variable acts as a confidence meter for our current candidate.

let count = 0;

Step 2

We initialize a for loop to iterate through each element of the nums array.

for (const num of nums) {
}

Step 3

The logic that goes inside the for loop:

if (count === 0) candidate = num;
count += num === candidate ? 1 : -1;

If count equals 0, we reassign candidate to the current value of num. This is because a count of 0 means we have zero confidence in our current candidate, so we replace it with the number we're looking at right now.

Then we update our confidence meter. If the current number matches our candidate, count goes up by 1. If it doesn't match, count drops by 1. Every time we see our candidate again we grow more confident. Every time we see something different, that confidence takes a hit.

This took a moment for me to understand. Here is a quick explanation and a table that should help make the concept more concrete.

Using our example array from earlier:

nums = [2, 4, 2, 2, 4, 4, 4]

The easiest way to explain how we always end up with the correct answer is to think of the elements - 2 and 4 - as opposing teams. For every element 2, there is an element 4 to cancel it out. Since 4 is our majority element, there are not enough 2s to cancel out all of the 4s.

Since each pair of elements cancels each other out, and we are guaranteed that a majority element exists, it will always be the value that has no pair that will be our majority element.

Here is a step by step breakdown:

Return 4. Correct.

Time complexity: O(n)

One pass through the array.

Space complexity: O(1)

Just two variables regardless of input size. No additional data structures needed.

Conclusion

Both approaches work fine, are pretty straightforward, and have a time complexity of O(n). However, the second approach has a space complexity of O(1). The reason for this is that this approach doesn't need a Map to determine the majority element - it can do everything using just two variables. So while Approach 1 will work fine in most cases, Approach 2 will scale significantly better.

...Day 5 coming soon