0% completed
Problem Statement
Given an array nums
having an n
elements, identify the element that appears the majority of the time, meaning more than n/2 times.
Examples
-
Example 1:
- Input:
[1, 2, 2, 3, 2]
- Expected Output:
2
- Justification: Here, '2' appears 3 times in a 5-element array, making it the majority element.
- Input:
-
Example 2:
- Input:
[4, 4, 4, 4, 7, 4, 4]
- Expected Output:
4
- Justification: '4' is the majority element as it appears 5 out of 7 times.
- Input:
-
Example 3:
- Input:
[9, 9, 1, 1, 9, 1, 9, 9]
- Expected Output:
9
- Justification: '9' is the majority element, appearing 5 times in an 8-element array.
- Input:
Constraints:
n == nums.length
- 1 <= n <= 5 * 10<sup>4</sup>
- -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
Solution
The divide and conquer algorithm can be used to find the majority element in an array efficiently. The strategy involves recursively dividing the array into two halves until each segment contains a single element. At this base level, a single element is trivially the majority of its one-element segment. As we merge these segments back together, we determine the majority element of each merged segment by comparing the counts of the majority elements from the two halves. The majority element of the entire array is the one that remains the majority as segments are progressively merged.
Step-by-Step Algorithm
-
Base Case: In the recursive function, check if the current segment of the array has only one element. If so, return this element as it is trivially the majority element of this single-element segment.
-
Divide Step:
- Calculate the middle index of the current segment of the array.
- Recursively call the function for the left half of the array (
start
tomiddle
) and the right half (middle + 1
toend
). - Store the returned values from both halves, which are potential majority elements for each half.
-
Conquer Step:
- If the majority element found in the left half is the same as the one in the right half, return this element as the majority element for the current segment.
- If they are different, count the occurrences of each within the current segment.
-
Combine Step:
- Compare the counts of these two elements.
- Return the element that has a higher count within the current segment. If the counts are equal, either can be returned as the majority element for this segment.
-
End Function: Return the majority element of the array.
This logic is based on the principle that the majority element of the entire array must be the majority element in at least one of the two halves. By recursively breaking down and then combining the array, we are able to zero in on the majority element efficiently.
Algorithm Walkthrough
- Initial Array:
[4, 4, 4, 4, 7, 4, 4]
- Divide: Split into
[4, 4, 4, 4]
and[7, 4, 4]
.- For
[4, 4, 4, 4]
, split further into[4, 4]
and[4, 4]
.[4, 4]
splits into[4]
and[4]
, both trivially4
.- Merge
[4]
and[4]
to get4
as the majority. - Merge
[4, 4]
and[4, 4]
to get4
as the majority.
- For
[7, 4, 4]
, split into[7]
and[4, 4]
.[7]
is trivially their own majority.- Merge
[4]
and[7]
, neither is a majority, so no majority for this segment. [4, 4]
splits into[4]
and[4]
, both trivially4
.- Merge
[4]
and[4]
to get4
as the majority. - Merge
[7]
and[4, 4]
,4
is the majority.
- For
- Combine: Merge
[4, 4, 4, 4]
and[7, 4, 4]
.- Count occurrences of
4
in the entire array (5 times). - Since 5 is more than half of occurences of 7,
4
is the majority of the whole array.
- Count occurrences of
Here is the visual representation of the algorithm:
Code
Here is the code for this algorithm:
Time and Space Complexity Analysis
-
Time Complexity: The array is recursively divided, and at each level of recursion, counting occurrences takes O(n) time. It takes O(log n) time to divide arrays in the subarray, and the total time complexity is
O(n log n)
. -
Space Complexity: Due to the recursive calls, the space complexity is determined by the depth of the recursion tree, which is
O(log n)
. No additional significant space is used outside of the recursion stack.
AN Alternate Approach: O(n) Solution
To solve the Majority Element problem, we employ a Hash Map approach to efficiently track the frequency of each element in the array. The core idea is to iterate through the array once, counting the occurrences of each number using a hash map. By maintaining these counts, we can easily identify the element that appears more than half the time (n/2
), which qualifies it as the majority element.
This method is effective because it leverages the constant-time lookup and insertion properties of hash maps, ensuring that each element is processed in linear time relative to the size of the array.
Step-by-Step Algorithm
-
Initialize a Hash Map:
- Create an empty hash map
counts
where the key is an integer from the array, and the value is its corresponding count. - It enables quick tracking and updating of each number's frequency as we iterate through the array.
- Create an empty hash map
-
Iterate Through the Array:
- For each element
num
in the arraynums
:- Check Presence in Hash Map:
- If
num
is not already a key incounts
:- Add to Hash Map: Insert
num
with an initial count of1
, as it is the first occurrence ofnum
in the array.
- Add to Hash Map: Insert
- Else:
- Increment Count: Update the count of
num
by adding1
, as it is Subsequent occurrence ofnum
increase its frequency.
- Increment Count: Update the count of
- If
- Check Presence in Hash Map:
- For each element
-
Identify the Majority Element:
- Iterate Through Hash Map Entries:
- For each key-value pair
(number, count)
incounts
:- Check Majority Condition:
- If
count
is greater thann/2
(wheren
is the length ofnums
):- Return Majority Element:
number
is the majority element, as tt satisfies the condition of appearing more than half the time.
- Return Majority Element:
- If
- Check Majority Condition:
- For each key-value pair
- Iterate Through Hash Map Entries:
-
Handle Edge Cases:
- If no element in the hash map satisfies the majority condition after the iteration:
- Return Result: Depending on problem constraints, return a default value or handle as per requirements.
- If no element in the hash map satisfies the majority condition after the iteration:
Algorithm Walkthrough
Let's walk through the algorithm using the input nums = [4, 4, 4, 4, 7, 4, 4]
.
-
Initialization:
- Hash Map:
counts = {}
- Array Length:
n = 7
(since there are 7 elements in the array)
- Hash Map:
-
First Iteration (
num = 4
):- Check Hash Map:
4
is not incounts
. - Add to Hash Map:
counts = {4: 1}
- Reason: First occurrence of
4
.
- Check Hash Map:
-
Second Iteration (
num = 4
):- Check Hash Map:
4
is already incounts
with a count of1
. - Increment Count:
counts = {4: 2}
- Reason: Second occurrence of
4
.
- Check Hash Map:
-
Third Iteration (
num = 4
):- Check Hash Map:
4
is already incounts
with a count of2
. - Increment Count:
counts = {4: 3}
- Reason: Third occurrence of
4
.
- Check Hash Map:
-
Fourth Iteration (
num = 4
):- Check Hash Map:
4
is already incounts
with a count of3
. - Increment Count:
counts = {4: 4}
- Reason: Fourth occurrence of
4
.
- Check Hash Map:
-
Fifth Iteration (
num = 7
):- Check Hash Map:
7
is not incounts
. - Add to Hash Map:
counts = {4: 4, 7: 1}
- Reason: First occurrence of
7
.
- Check Hash Map:
-
Sixth Iteration (
num = 4
):- Check Hash Map:
4
is already incounts
with a count of4
. - Increment Count:
counts = {4: 5, 7: 1}
- Reason: Fifth occurrence of
4
.
- Check Hash Map:
-
Seventh Iteration (
num = 4
):- Check Hash Map:
4
is already incounts
with a count of5
. - Increment Count:
counts = {4: 6, 7: 1}
- Reason: Sixth occurrence of
4
.
- Check Hash Map:
-
Identify the Majority Element:
- Iterate Through Hash Map:
- First Entry:
(4, 6)
- Check Majority Condition:
6 > 7/2
→6 > 3.5
→ True - Result:
4
is the majority element. - Reason: It appears
6
times in a7
-element array, satisfying the majority condition.
- Check Majority Condition:
- First Entry:
- Iterate Through Hash Map:
-
Final Result:
- Majority Element:
4
- Majority Element:
Code
Complexity Analysis
Time Complexity
-
Counting Phase:
- Operation: Iterating through the array to count occurrences.
- Complexity: O(n), where
n
is the number of elements in the array. - Reason: Each element is processed exactly once to update its count in the hash map.
-
Identification Phase:
- Operation: Iterating through the hash map entries to find the majority element.
- Complexity: O(n) in the worst case, where all elements are unique.
- Reason: In scenarios where every element is unique, the hash map contains
n
entries, requiringn
iterations to check for the majority condition.
-
Overall Time Complexity: O(n)
- The two phases are sequential, and both are linear, so the combined time complexity remains linear.
Space Complexity
-
Hash Map Storage:
- Operation: Storing counts of each unique number.
- Space: O(n) in the worst case, where all elements are unique.
- Reason: Each unique element requires additional space in the hash map.
-
Auxiliary Space:
- Variables: A constant amount of extra space is used for variables like
totalCount
,product
, and pointers. - Space: O(1)
- Variables: A constant amount of extra space is used for variables like
-
Overall Space Complexity: O(n)
- Dominated by the space required to store the hash map, especially when all elements are unique.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible