grid47 Exploring patterns and algorithms
Oct 21, 2024
4 min read
Solution to LeetCode 169: Majority Element Problem
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.
Problem
Approach
Steps
Complexity
Input: The input consists of an array nums of integers of size n, where 1 <= n <= 50,000 and -10^9 <= nums[i] <= 10^9.
Example: nums = [4, 4, 2, 2, 2, 4, 4]
Constraints:
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
Output: The output should be the majority element in the input array.
Example: Output: 4
Constraints:
• The output will always be a valid majority element, as per the problem assumption.
Goal: The goal is to find the majority element in the given array.
Steps:
• Initialize a variable to store the current majority element and its count.
• Iterate through the array and update the current majority element whenever necessary.
• Return the element that appears more than n // 2 times.
Goal: The size of the array is within a manageable range for typical algorithms. The majority element always exists in the array, and no element should appear less than n // 2 times.
Steps:
• 1 <= n <= 50,000
• -10^9 <= nums[i] <= 10^9
Assumptions:
• The majority element always exists in the array.
• Input: nums = [5, 3, 5]
• Explanation: In this example, the element 5 appears twice, which is more than half of the array's length (3 // 2). Therefore, 5 is the majority element.
Approach: The approach involves iterating through the array and keeping track of the current majority element using a counter.
Observations:
• This is a problem that can be solved efficiently using a linear pass through the array, keeping track of the counts of elements.
• We can use a counter to track the frequency of the current majority element.
Steps:
• Initialize a counter and a variable for the majority element.
• Loop through the array and update the counter for each element.
• If the counter reaches the threshold (n // 2), return the current element as the majority element.
Empty Inputs:
• The problem guarantees that there is always a majority element, so we do not need to handle the empty array case.
Large Inputs:
• For larger inputs (up to 50,000 elements), the solution should work efficiently in linear time.
Special Values:
• The majority element will always appear more than n // 2 times, so no need to handle cases where no majority exists.
Constraints:
• The solution should work in linear time and handle the maximum input size.
Define the function 'majorityElement' that takes a vector of integers as input and returns the majority element, which appears more than half the time in the array.
2 : Variable Initialization
int e = nums[0], cnt =1;
Initialize two variables: 'e' (to store the majority element) and 'cnt' (to store the count of occurrences of the current majority element). Initially, set 'e' to the first element of the array and 'cnt' to 1.
3 : Data Structure Declaration
map<int, int> mp;
Declare a map 'mp' to keep track of the frequency count of each element in the array.
4 : For Loop
for(intx: nums) {
Iterate through each element 'x' in the array 'nums'.
5 : Frequency Update
mp[x]++;
Increment the frequency count of element 'x' in the map.
6 : Frequency Comparison
if(mp[x] > cnt) {
Check if the frequency of the current element 'x' is greater than the current maximum count 'cnt'.
7 : Count Update
cnt = mp[x];
If the frequency of 'x' exceeds the current count, update 'cnt' to the new frequency of 'x'.
8 : Element Update
e = x;
Update the majority element 'e' to the current element 'x' as it has the highest frequency so far.
9 : Return Statement
return e;
Return the majority element 'e' that has been identified by the loop.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only iterate through the array once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only use a few extra variables to store the current majority element and counter.
