Concept wise, the problem here is similar to the find the majority element 1 problem. However, there is a caveat. In this case, we need to find the element that occurs times in the array n being the number of elements in the array).
Once again we are given a challenge, the space complexity of this algorithm must be no more than O(1), so just like before we need to achieve constant time.
Solution Explanation
For this solution, it is similar to what we did in the first problem (Majority Element I), however here we want to utilize a HashMap. So, if we were to brute force our way through this we could create a recursive loop that populates the HashMap with each occurrence of an element and then we find out which elements occur more that of the time.
However, to minimize the time complexity from O(n) to O(1) we can introduce a limitation. Given that we may find 2 or 1 elements that meet the criteria, we can introduce a limit to the HashMap so that it does not exceed 2 elements.
What we mean here is that, only 2 elements can be in the HashMap at a time and it must in no way be exceeded. Refer to the diagram below for an explanation of how this works:
Implementation
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
count = defaultdict(int)
for n in nums:
count[n] += 1 # increment each occurence by one
if len(count) <= 2: # as long as values < 2 we don't worry
continue
new_count = defaultdict(int) # init a new dict to copy into
for n, c in count.items():
if c > 1:
# if the value of a count is greater than 1 we add to
# the new count, other wise we don't since it equals
# zero, which we don't add
new_count[n] = c - 1
count = new_count
res = []
for n in count:
if nums.count(n) > len(nums) // 3: # check if it meets condit
res.append(n) # appent to output array
return res
So to summarize the solution to this problem. You are to initialize a HashMap that is limited to only holding no more than 2 elements at a time given that there may at most only be two majority elements. On top of that the approach has you maintain a count per each occurrence and when you come across a new element and add it to the HashMap, you check to see if the num count surpasses 2 and if it does, decrement everything by 1. If there is a count that becomes 0, then you remove that. In the implementations case we haven't removed it rather we don't add it in at all given it was 0.
