Last updated on January 13th, 2025 at 03:12 am

Here, we see a Majority Element II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array

Companies

Zenefits

Level of Question

Medium

Majority Element II LeetCode Solution

1. Problem Statement

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

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

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

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Boyer-Moore Voting Algorithm”. This is a specialized algorithm for finding elements that appear more than n/k times in an array, where k is a constant (in this case, k = 3).

3. Code Implementation in Different Languages

3.1 Majority Element II C++

class Solution {
public:
  vector<int> majorityElement(vector<int>& nums) 
  {
	  int y(-1), z(-1), cy(0), cz(0);
	  for (const auto & x: nums) 
	  {
		  if (x == y) cy++;
		  else if (x == z) cz++;
		  else if (! cy) y = x, cy = 1;
		  else if (! cz) z = x, cz = 1;
		  else cy--, cz--;
     }
     cy = cz = 0;
     for (const auto & x: nums)
		 if (x == y) cy++;
			 else if (x == z) cz++;
	  vector<int> r;
	  if (cy > size(nums)/3) r.push_back(y);
	  if (cz > size(nums)/3) r.push_back(z);
	  return r;
  }
};

3.2 Majority Element II Java

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Map<Integer, Integer> elementCountMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            elementCountMap.put(nums[i], elementCountMap.getOrDefault(nums[i], 0) + 1);
        }
        
        List<Integer> majorityElements = new ArrayList<>();
        int threshold = nums.length / 3;
        for (Map.Entry<Integer, Integer> entry : elementCountMap.entrySet()) {
            int element = entry.getKey();
            int count = entry.getValue();
            if (count > threshold) {
                majorityElements.add(element);
            }
        }
        return majorityElements;
    }
}

3.3 Majority Element II JavaScript

var majorityElement = function(nums) {
    let candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;
    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        } else if (count1 === 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    let result = [];
    if (nums.filter(n => n === candidate1).length > nums.length / 3) result.push(candidate1);
    if (nums.filter(n => n === candidate2).length > nums.length / 3) result.push(candidate2);
    return result;
};

3.4 Majority Element II Python

class Solution(object):
    def majorityElement(self, nums):
        element_count = Counter(nums)
        majority_elements = []
        threshold = len(nums) // 3
        for element, count in element_count.items():
            if count > threshold:
                majority_elements.append(element)
        return majority_elements

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

• The C++ and JavaScript implementations use the Boyer-Moore Voting Algorithm, which is more space-efficient (O(1) space for C++).
• The Java and Python implementations use a counting-based approach, which is simpler to implement but requires O(n) space.
• All implementations have a time complexity of O(n).