NUHMAN.com

Introduction

LeetCode 169 asks to find the majority element in an array. The majority element is the element that appears more than ⌊ n / 2 ⌋ times, where n is the size of the array. The problem guarantees that a majority element always exists.

Problem Statement

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n / 2 ⌋ times.

Function Signature:

go

func majorityElement(nums []int) int

• Input:
• nums: A slice of integers nums with n elements where 1 <= n <= 10^5.
• Output:
• The majority element in the array, which appears more than n / 2 times.

Approach

Boyle-Moore Voting Algorithm

To solve this problem efficiently, we can use the Boyer-Moore Voting Algorithm, which allows us to find the majority element in O(n) time and O(1) space.

Key Steps:

1. Initialize a candidate and a count:

• We assume that the first element is the candidate for the majority element.
• Set the count to 1.

1. Iterate through the array:

• If the current element matches the candidate, increase the count.
• If the current element does not match the candidate, decrease the count.
• If the count becomes zero, set the current element as the new candidate and reset the count to 1.

1. Final Candidate:

• By the end of the iteration, the candidate will be the majority element, as the algorithm guarantees it will be the most frequent element.

Time Complexity:

• O(n), where n is the number of elements in the array. We are iterating over the array only once.

Space Complexity:

• O(1), as we only use a few variables to store the candidate and count.

Go Implementation

go

func majorityElement(nums []int) int {
    candidate, count := nums[0], 1

    for i := 1; i < len(nums); i++ {
        if nums[i] == candidate {
            count++
        } else {
            count--
        }

        if count == 0 {
            candidate = nums[i]
            count = 1
        }
    }

    return candidate
}

Explanation of the Code:

1. Initial Setup:

• candidate is initialized to the first element of the array, and count is initialized to 1.

1. Iteration Over the Array:

• For each element nums[i] in the array starting from index 1:
• If nums[i] is equal to the candidate, increment the count.
• If nums[i] is not equal to the candidate, decrement the count.
• If the count reaches zero, it means the previous candidate is no longer valid. Thus, the new candidate is set to the current element, and the count is reset to 1.

1. Return the Majority Element:

• After iterating through the array, the value in candidate will be the majority element, as the Boyer-Moore Voting Algorithm guarantees that the majority element will always remain as the final candidate.

Example

Example 1:

go

nums := []int{3, 2, 3}
result := majorityElement(nums)
fmt.Println(result) // Output: 3

Explanation:

• The majority element is 3, as it appears more than ⌊ 3 / 2 ⌋ = 1 time.

Example 2:

go

nums := []int{2, 2, 1, 1, 1, 2, 2}
result := majorityElement(nums)
fmt.Println(result) // Output: 2

Explanation:

• The majority element is 2, as it appears more than ⌊ 7 / 2 ⌋ = 3 times.

Example 3:

go

nums := []int{8, 8, 7, 7, 7}
result := majorityElement(nums)
fmt.Println(result) // Output: 7

Explanation:

• The majority element is 7, as it appears more than ⌊ 5 / 2 ⌋ = 2 times.

Conclusion

LeetCode 169: Majority Element can be efficiently solved using the Boyer-Moore Voting Algorithm in O(n) time and O(1) space. This solution is optimal for large input sizes, as it processes the array in linear time and uses constant space.