Last updated on July 15th, 2024 at 03:54 am

Here, We see Majority Element problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Array, Bit Manipulation, Divide and Conquer

Companies

Adobe, Zenefits

Level of Question

Easy

Majority Element LeetCode Solution

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than [n / 2] times. You may assume that the majority element always exists in the array.

Example 1:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

1. Majority Element Leetcode Solution C++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size(), candidate, counter;
        srand(unsigned(time(NULL)));
        while (true) {
            candidate = nums[rand() % n], counter = 0;
            for (int num : nums) {
                if (num == candidate) {
                    counter++;
                }
            }
            if (counter > n / 2) {
                break;
            }
        }
        return candidate;
    }
};

1.1 Explanation

1. Random Selection: The code randomly selects an element (candidate) from the array.
2. Count Occurrences: It counts how many times this candidate appears in the array (counter).
3. Majority Check: If the candidate count exceeds n / 2, it returns the candidate. Otherwise, it repeats the process.

1.2 Time Complexity

• O(n), where n is the size of the array. The expected number of iterations is constant, as the probability of selecting the majority element increases with each iteration.

1.3 Space Complexity

• O(1), only a few additional variables are used.

2. Majority Element Leetcode Solution Java

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

2.1 Explanation

1. Sort the Array: The code sorts the array.
2. Return Middle Element: It returns the middle element of the sorted array. The majority element will always be at the middle if it appears more than n / 2 times.

2.2 Time Complexity

• O(n log n), where n is the size of the array.

2.3 Space Complexity

• O(1), if the sorting algorithm is in-place; otherwise, it can be O(n) depending on the sorting implementation.

3. Majority Element Leetcode Solution JavaScript

var majorityElement = function(nums) {
    var obj = {};
    
    for(var i = 0; i < nums.length; i++){
        obj[nums[i]] = obj[nums[i]] + 1 || 1;
        if(obj[nums[i]] > nums.length / 2)  return nums[i];
    }
};

3.1 Explanation

1. Count Elements: The code uses an object (obj) to count occurrences of each element.
2. Check Majority: If an element’s count exceeds n / 2, it returns the element immediately.

3.2 Time Complexity

• O(n), where n is the size of the array, as each element is processed once.

3.3 Space Complexity

• O(n), due to the storage of element counts in the object.

4. Majority Element Python Solution

class Solution(object):
    def majorityElement(self, nums):
        return sorted(nums)[len(nums)/2]

4.1 Explanation

1. Sort the Array: The code sorts the array.
2. Return Middle Element: It returns the middle element of the sorted array. The majority element will always be at the middle if it appears more than n / 2 times.

4.2 Time Complexity

• O(n log n), where n is the size of the array.

4.3 Space Complexity

• O(n), depending on the sorting algorithm implementation.