SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The majority element in an array of size n is the element that appears more than ⌊n / 2⌋ times. Given that the majority element always exists, it is guaranteed to be the most frequent element in the array. This problem can be solved efficiently by using a frequency count or a more optimal algorithm like the Boyer-Moore Voting Algorithm.

Approach

1. Initialize a dictionary to count the frequency of each element in the array.
2. Iterate through the array and populate the frequency dictionary.
3. Iterate through the frequency dictionary to find the element with the highest count.
4. Return the element with the highest count as the majority element.

Alternatively, the Boyer-Moore Voting Algorithm can be used for a more optimal approach:

1. Initialize two variables: count and candidate.
2. Iterate through the array:
   • If count is 0, set candidate to the current element and count to 1.
   • If the current element is the same as candidate, increment count.
   • Otherwise, decrement count.
3. After the loop, candidate will be the majority element.
4. Return candidate.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) for the Boyer-Moore Voting Algorithm since it only uses a few variables. The space complexity is O(n) if using a frequency dictionary.

Code

C++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> frequency;
        for (int num : nums) {
            frequency[num]++;}
        int majorityElement = nums[0];
        int maxCount = frequency[nums[0]];
        for (const auto& pair : frequency) {
            if (pair.second > maxCount) {
                majorityElement = pair.first;
                maxCount = pair.second;
            }
            }
        return majorityElement;
    }
    };

Python

class Solution(object):
    def majorityElement(self, nums):
        frequency = {}
        for num in nums:
            if num in frequency:
                frequency[num] += 1
            else:
                frequency[num] = 1
        majority_element = nums[0]
        max_count = frequency[nums[0]]
        for num, count in frequency.items():
            if count > max_count:
                majority_element = num
                max_count = count
        
        return majority_element

Java

class Solution {
    public void swap(int []arr,int i ,int j){
        int temp =arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public int majorityElement(int[] arr) {
     for (int i = 1; i <arr.length ; i++) {
            int j=i;
           while(j >=1 && arr[j]<arr[j-1]){
               swap(arr,j,j-1);
               j--;
           }
        }
     return arr[arr.length/2];   
    }
}

JavaScript

var majorityElement = function (nums) {
    const f= {}
    for(let num of nums){
        if(f[num]) f[num]++
        else f[num]=1
    }
    const fArr = Object.entries(f)
    const ans = fArr.reduce((acc,curr)=>{
        if(curr[1]> acc[1]) return curr
        else return acc
    })
    return ans[0]   
};