Majority Element

1

class Solution {
public:
int majorityElement(vector& nums) {

   int len=nums.size();
   int ans=0,co=0,i=0;
   sort(nums.begin(),nums.end());
   for(int i=0;i<len;i++)
   {
       co=count(nums.begin(),nums.end(),nums[i]);
       if(co>(len/2))
       {
           ans=nums[i];
           break;
       }
   }
   
    return ans;
}

};

I have to return the element which appears more than floor(n/2) times.
Why I am getting TLE for the following testcase
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1…]

2

Expected Complexity may be O(n).
Time Complexity of your code:
O(n) — for loop
in each iteration for count function — It’s order of O(n) as it Compares once each element with the particular value.
Overall Complexity -> O(n*n)

3

Your code takes O(n*n) time. Implement Boyer-Moores Algorithm which takes O(n) time.

1 Like
4

The problem is expected to be solved in time complexity O(n).
You can use STL Map to store frequencies of each array element and output the maximum frequency key in the map

Edit : You can refer to the below code for Map implementation although a better approach in O(1) space does exist.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int i,n;
        n = nums.size();
        map<int,int>mp;
        for(i=0;i<n;i++)
            mp[nums[i]]++;
        int res = 0;
        for(auto x : mp)
            res = max(res,x.second);
        for(auto x : mp)
            if(res == x.second)
                return x.first;
        return 0;
    }
};
2 Likes
5

In the for loop it should break as soon as it finds the majority element.
For example in the above case
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,…]
It knows the count for the 1st one encountered then why does I get tle

6

This is my code , it might help you
class Solution {
public int majorityElement(int[] nums) {
int y=nums.length/2;
int c=1;
Arrays.sort(nums);
int i;
for( i=0;i<nums.length-1;i++)
{
if(nums[i]==nums[i+1])
c++;
else
{
if(c>y)
return nums[i];
else
c=1;
}
}
return nums[i];
}
}

Happy coding…

1 Like
7

if this is leetcode Majority Element, then use easiest way to solve it.

public int fun(int[] num){
   Arrays.sort(num);
   return num[num.length/2];
}

this has time complexity of o(nlogn) and o(1) space.
if you want to do it in o(n) time,
then use frequency array to store elements, then check whether it has the value n/2 or greater,

8

Yeah, but the count function appears before that which is of order O(n) . So the comparision is done for each value and then checks for the condition .

1 Like
9

Solved it Using Map.

10

use maps, sorting is not essential

11

You can use maps but if the the range of a[i] is less i would suggest you use arrays or vectors. Maps have one disadvantage i.e. there can be lot of miss and it can slow down the code on the other hand using arrays as a maps is fast and easier to implement.

1 Like