229. Majority Element II #

Problem #

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

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Problem Summary #

Given an array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. Note: The algorithm is required to have a time complexity of O(n) and a space complexity of O(1).

Solution Ideas #

This problem is an enhanced version of Problem 169. It is an extended version of the Boyer-Moore Majority Vote algorithm.
The problem requires finding numbers in the array that appear more than ⌊ n/3 ⌋ times. The space complexity is required to be O(1). Easy problem.
This article is well written and can be used as a reference: https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

Code #


package leetcode

// Solution 1 Time complexity O(n) Space complexity O(1)
func majorityElement229(nums []int) []int {
	// since we are checking if a num appears more than 1/3 of the time
	// it is only possible to have at most 2 nums (>1/3 + >1/3 = >2/3)
	count1, count2, candidate1, candidate2 := 0, 0, 0, 1
	// Select Candidates
	for _, num := range nums {
		if num == candidate1 {
			count1++
		} else if num == candidate2 {
			count2++
		} else if count1 <= 0 {
			// We have a bad first candidate, replace!
			candidate1, count1 = num, 1
		} else if count2 <= 0 {
			// We have a bad second candidate, replace!
			candidate2, count2 = num, 1
		} else {
			// Both candidates suck, boo!
			count1--
			count2--
		}
	}
	// Recount!
	count1, count2 = 0, 0
	for _, num := range nums {
		if num == candidate1 {
			count1++
		} else if num == candidate2 {
			count2++
		}
	}
	length := len(nums)
	if count1 > length/3 && count2 > length/3 {
		return []int{candidate1, candidate2}
	}
	if count1 > length/3 {
		return []int{candidate1}
	}
	if count2 > length/3 {
		return []int{candidate2}
	}
	return []int{}
}

// Solution 2 Time complexity O(n) Space complexity O(n)
func majorityElement229_1(nums []int) []int {
	result, m := make([]int, 0), make(map[int]int)
	for _, val := range nums {
		if v, ok := m[val]; ok {
			m[val] = v + 1
		} else {
			m[val] = 1
		}
	}
	for k, v := range m {
		if v > len(nums)/3 {
			result = append(result, k)
		}
	}
	return result
}