HomeLeetcode229. Majority Element II - Leetcode Solutions
Leetcode

229. Majority Element II – Leetcode Solutions

Declan Clarke

Description

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

Examples:

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]

Solution in Python

To solve the problem of finding all elements that appear more than ⌊n/3⌋ times in an integer array, we can leverage the Boyer-Moore Voting Algorithm. This algorithm allows us to efficiently find potential majority elements with linear time complexity and constant space.

Explanation

  1. Why only two candidates?:
    • The problem asks to find elements that appear more than ⌊n/3⌋ times. There can be at most two elements that satisfy this condition. If there were three or more such elements, their combined count would exceed the total number of elements in the array, which is impossible.
  2. Two pass approach:
    • First pass: We need to identify at most two potential candidates that could appear more than ⌊n/3⌋ times.
    • Second pass: We verify if the identified candidates actually appear more than ⌊n/3⌋ times.

Detailed Steps

  1. First Pass (Candidate Selection):
    • We maintain two potential candidates (candidate1 and candidate2) along with their respective counts (count1 and count2).
    • As we iterate through the array:
      • If the current number matches candidate1, increment count1.
      • Else if it matches candidate2, increment count2.
      • If count1 is zero, assign candidate1 to the current number and set count1 to 1.
      • Else if count2 is zero, assign candidate2 to the current number and set count2 to 1.
      • If the current number doesn’t match either candidate and both counts are non-zero, decrement both count1 and count2.
  2. Second Pass (Validation):
    • After the first pass, we are left with two potential candidates. In the second pass, we count the occurrences of each candidate to confirm if they appear more than ⌊n/3⌋ times.
  3. Edge Cases:
    • Handle small arrays, like arrays of length 1 or 2, separately.
Python
from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # First step: Identify potential candidates
        candidate1, candidate2 = None, None
        count1, count2 = 0, 0
        
        # First pass: Finding the potential majority elements
        for num in nums:
            if candidate1 == num:
                count1 += 1
            elif candidate2 == num:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 = 1
            elif count2 == 0:
                candidate2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        # Second step: Validate candidates by counting their actual occurrences
        result = []
        n = len(nums)
        
        # Count occurrences of candidate1 and candidate2
        count1 = sum(1 for num in nums if num == candidate1)
        count2 = sum(1 for num in nums if num == candidate2)
        
        # Check if candidate1 appears more than n/3 times
        if count1 > n // 3:
            result.append(candidate1)
        
        # Check if candidate2 appears more than n/3 times (and is not the same as candidate1)
        if candidate2 != candidate1 and count2 > n // 3:
            result.append(candidate2)
        
        return result

Explanation of the Code

  1. Initialization:
    • We initialize two candidates (candidate1 and candidate2) and their counts (count1 and count2) to None and 0 respectively.
  2. First Pass (Finding Potential Candidates):
    • For each number in nums, we check if it matches candidate1 or candidate2. If it doesn’t and one of the counts is zero, we set that candidate to the current number and reset the count to 1. If neither candidate matches and both counts are non-zero, we decrement both counts.
  3. Second Pass (Validating Candidates):
    • After identifying potential candidates, we count their actual occurrences in the array.
    • If a candidate appears more than ⌊n/3⌋ times, we add it to the result list.
  4. Edge Case Handling:
    • If the array contains less than 3 elements, the algorithm automatically handles this by setting the candidates based on the counts and verifying their occurrences.

Time Complexity

  • O(n): We iterate through the array twice — once for identifying potential candidates and once for validating them.

Space Complexity

  • O(1): We only use a constant amount of extra space for storing candidates and their counts.

This solution efficiently finds all elements that appear more than ⌊n/3⌋ times with linear time and constant space, making it optimal for large input sizes.

Solution in Javascript

JavaScript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    // First step: Identify the two potential candidates
    let candidate1 = null, candidate2 = null;
    let count1 = 0, count2 = 0;
    
    // First pass: Find the potential majority elements
    for (let num of nums) {
        if (candidate1 === num) {
            // If the current number is equal to candidate1, increment count1
            count1++;
        } else if (candidate2 === num) {
            // If the current number is equal to candidate2, increment count2
            count2++;
        } else if (count1 === 0) {
            // If count1 is zero, assign the current number as candidate1 and reset count1
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            // If count2 is zero, assign the current number as candidate2 and reset count2
            candidate2 = num;
            count2 = 1;
        } else {
            // If the current number matches neither candidate and both counts are non-zero, decrement both counts
            count1--;
            count2--;
        }
    }
    
    // Second step: Validate the candidates by counting their actual occurrences
    let result = [];
    let n = nums.length;
    count1 = 0;
    count2 = 0;
    
    // Count occurrences of candidate1 and candidate2
    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        }
    }
    
    // Check if candidate1 occurs more than n/3 times
    if (count1 > Math.floor(n / 3)) {
        result.push(candidate1);
    }
    
    // Check if candidate2 occurs more than n/3 times (and candidate1 !== candidate2)
    if (count2 > Math.floor(n / 3)) {
        result.push(candidate2);
    }
    
    return result;
};

Solution in Java

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

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        // Initialize two potential candidates and their respective counts
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // First pass: find potential candidates for majority elements
        for (int num : nums) {
            if (num == candidate1) {
                // If current number matches candidate1, increment count1
                count1++;
            } else if (num == candidate2) {
                // If current number matches candidate2, increment count2
                count2++;
            } else if (count1 == 0) {
                // If count1 is zero, assign current number as candidate1 and set count1 to 1
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                // If count2 is zero, assign current number as candidate2 and set count2 to 1
                candidate2 = num;
                count2 = 1;
            } else {
                // If current number matches neither candidate and both counts are non-zero, decrement both counts
                count1--;
                count2--;
            }
        }
        
        // Second pass: validate the potential candidates by counting their actual occurrences
        List<Integer> result = new ArrayList<>();
        count1 = 0;
        count2 = 0;
        
        // Count the occurrences of candidate1 and candidate2 in the array
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        // Check if candidate1 appears more than n/3 times
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        
        // Check if candidate2 appears more than n/3 times (and candidate1 != candidate2)
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }
        
        // Return the result list containing the majority elements
        return result;
    }
}

Solution in C#

C#
using System.Collections.Generic;

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        // Initialize two potential candidates and their respective counts
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // First pass: Find the two potential candidates for majority elements
        foreach (int num in nums) {
            if (num == candidate1) {
                // Increment count1 if the current number matches candidate1
                count1++;
            } else if (num == candidate2) {
                // Increment count2 if the current number matches candidate2
                count2++;
            } else if (count1 == 0) {
                // If count1 is zero, assign the current number to candidate1 and set count1 to 1
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                // If count2 is zero, assign the current number to candidate2 and set count2 to 1
                candidate2 = num;
                count2 = 1;
            } else {
                // If neither candidate matches the current number and both counts are non-zero, decrement both counts
                count1--;
                count2--;
            }
        }
        
        // Second pass: Validate the two potential candidates by counting their actual occurrences
        count1 = 0;
        count2 = 0;
        foreach (int num in nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        // Prepare the result list
        IList<int> result = new List<int>();
        
        // Add candidate1 to the result if it appears more than n/3 times
        if (count1 > nums.Length / 3) {
            result.Add(candidate1);
        }
        
        // Add candidate2 to the result if it appears more than n/3 times
        if (count2 > nums.Length / 3) {
            result.Add(candidate2);
        }
        
        // Return the list of majority elements
        return result;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com