DevExCode

LeetCode 229: Majority Element II

ArrayHash TableSortingCounting

Problem Description

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.

View on LeetCode

Solutions

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;
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...