A Solution to LeetCode Problem 169. Majority Element in JavaScript

 

The majority element is the element that appears more than half of the time in a given array. For example, in the array [3, 2, 3], the majority element is 3 as it appears 2 out of 3 times, which is more than half. In this post, we will be discussing a solution to the LeetCode problem #169: Majority Element, using JavaScript.

Solution:

One way to solve this problem is to use a brute force approach, where we can iterate through the array and count the number of occurrences of each element. If the count of an element is greater than n/2, then we return that element as the majority element.

 

However, this solution has a time complexity of O(n^2), which is not very efficient.

 

A better solution would be to use a hash table to store the count of each element as we iterate through the array. This way, we can find the majority element in one pass, with a time complexity of O(n).

 

Here is the implementation of this solution in JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function(nums) {
    let hash = {};
    for (let i = 0; i < nums.length; i++) {
        if (hash[nums[i]]) {
            hash[nums[i]]++;
        } else {
            hash[nums[i]] = 1;
        }
    }
    for (let key in hash) {
        if (hash[key] > nums.length/2) {
            return key;
        }
    }
};

 

We first create an empty hash table called hash. Then, we iterate through the nums array and store the count of each element in the hash table. Finally, we iterate through the hash table and return the key (i.e., the element) if its count is greater than n/2.

 

This solution has a time complexity of O(n) and a space complexity of O(n), as we are using a hash table to store the counts of each element.

 

Conclusion:

 

In this post, we discussed a solution to the LeetCode problem #169: Majority Element, using JavaScript. We used a hash table to store the count of each element and found the majority element in one pass, with a time complexity of O(n).

 

I hope this post was helpful in explaining the solution to this problem. If you have any questions or suggestions, please leave a comment below.