DevExCode

LeetCode 229: Majority Element II Solution

Master LeetCode problem 229 (Majority Element II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

229. Majority Element II

Medium
ArrayHash TableSortingCounting

Problem Explanation

Explanation

To solve this problem in linear time and constant space, we can use the Boyer-Moore Majority Vote algorithm. The key idea is to maintain two counters to keep track of the potential majority elements. We iterate through the array and update these counters based on certain conditions. After the first pass, we need to verify if the elements found are actually majority elements by counting their occurrences again.

The algorithm works as follows:

  1. Initialize two variables candidate1 and candidate2 to store the potential majority elements and their counts as 0.
  2. Iterate through the array:
    • If the current element is equal to candidate1 or candidate2, increment their count.
    • Else if the counts are 0, update the candidates.
    • Else decrement both counts.
  3. Perform a second pass through the array to count the occurrences of candidate1 and candidate2 to determine if they are majority elements.
  4. Return the elements that occur more than n/3 times.

The time complexity of this algorithm is O(n) as we perform two passes through the array. The space complexity is O(1) since we are using only a constant amount of extra space.

Solution Code

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        int candidate1 = 0, count1 = 0;
        int candidate2 = 0, count2 = 0;
        
        for (int num : 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--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 229 (Majority Element II)?

This page provides optimized solutions for LeetCode problem 229 (Majority Element II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 229 (Majority Element II)?

The time complexity for LeetCode 229 (Majority Element II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 229 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 229 in Java, C++, or Python.

Back to LeetCode Solutions