DEV Community

Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on

Leetcode - 169. Majority Element

Is it possible to do in O(1) time complexity ?

There are multiple ways to solve this problem

One way is to sort the elements and return the middle element in array

Since the question says the majority element is more than n/2 times
the mid element has to be the majority element after sort

but the time complexity of this approach is O(nlogn) since we are sorting

Another way is to create a hashmap where key is the element and value is the times it is present in array

but the time complexity of this approach as well won't be O(1)

Now let's go into the solution with O(1) complexity

Boyer–Moore majority vote algorithm

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {

    let count = 1 ;
    let res = nums[0] ;
    for(let i = 1 ; i<nums.length ;i++){

        if(count==0){
            res = nums[i] 
        }
        if(nums[i] == res){
            count++ 
        }else{
            count--;  
        }
    }

    return res;

};
Enter fullscreen mode Exit fullscreen mode

Result

Image description

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more