In the realm of array manipulation problems, the Majority Element problem on LeetCode stands out as a fundamental challenge that tests one’s ability to understand and implement efficient algorithms. This extensive article dissects the Majority Element problem, delves into various strategies to solve it, and implements these solutions in Python.
The Majority Element problem is listed as problem number 169 on LeetCode. Here’s the problem statement:
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n/2⌋ times. You may assume that the majority element always exists in the array.
Input: nums = [3,2,3]
Input: nums = [2,2,1,1,1,2,2]
Understanding the Problem
We are given an array of size
n, and we need to find the element that occurs more than
n/2 times. It’s given that there is always a majority element. The challenge is to find this majority element efficiently.
Approach 1: Hash Map
One straightforward approach is to keep a count of each element using a hash map. We can then iterate through the hash map to find the element that occurs more than
def majorityElement(nums): from collections import defaultdict counts = defaultdict(int) for num in nums: counts[num] += 1 for num, count in counts.items(): if count > len(nums) // 2: return num
This approach has a time complexity of O(n) as it requires two iterations through the array. The space complexity is also O(n) because, in the worst case, the hash map stores all distinct elements.
Approach 2: Sorting
Another approach is to sort the array. Once the array is sorted, the majority element must be at the middle index (n/2) because it occurs more than half the time.
def majorityElement(nums): nums.sort() return nums[len(nums)//2]
This approach has a time complexity of O(n log n) due to sorting. The space complexity is O(1) if the sort is done in-place.
Approach 3: Moore’s Voting Algorithm
Moore’s Voting Algorithm is an optimal solution to this problem. The idea is to maintain a count of the majority element and keep a running candidate for the majority element. As we iterate through the array, if the current element is the same as the candidate, we increment the count. If the current element is different, we decrement the count. If the count becomes 0, we set the current element as the new candidate and reset the count to 1.
def majorityElement(nums): count = 0 candidate = None for num in nums: if count == 0: candidate = num count += 1 if num == candidate else -1 return candidate
This algorithm runs in O(n) time complexity and O(1) space complexity, making it the most efficient solution to this problem.
Approach 4: Randomization
Given that more than half the elements are the majority element, we can randomly select an element and check if it’s the majority element.
import random def majorityElement(nums): majority_count = len(nums) // 2 while True: candidate = random.choice(nums) if sum(1 for num in nums if num == candidate) > majority_count: return candidate
This approach has an average time complexity of O(n), but in the worst case, it could take an unbounded amount of time. The space complexity is O(1).
Approach 5: Divide and Conquer
We can also solve this problem using a divide and conquer strategy. If a majority element exists in the array, then it must be the majority element in either the first half, the second half, or both. We can split the array into two halves and solve the problem recursively for each half.
def majorityElement(nums): def majority_element_rec(start, end): if start == end: return nums[start] mid = (start + end) // 2 left = majority_element_rec(start, mid) right = majority_element_rec(mid + 1, end) if left == right: return left left_count = sum(1 for i in range(start, end + 1) if nums[i] == left) right_count = sum(1 for i in range(start, end + 1) if nums[i] == right) return left if left_count > right_count else right return majority_element_rec(0, len(nums) - 1)
This approach has a time complexity of O(n log n) and a space complexity of O(log n) due to the recursive stack.
The Majority Element problem serves as an excellent example to illustrate various algorithms and strategies for array manipulation. We explored five different approaches, including hash maps, sorting, Moore’s Voting Algorithm, randomization, and divide and conquer. Each of these approaches has its trade-offs in terms of time and space complexity. For this particular problem, Moore’s Voting Algorithm stands out due to its linear time complexity and constant space usage, showcasing the power of clever algorithms in solving seemingly simple problems efficiently. Understanding these diverse strategies is essential in developing problem-solving skills for algorithmic challenges.