You are given an array of integer nums[] where each number represents a vote to a candidate. Return the candidates that have votes greater than one-third of the total votes, If there’s not a majority vote, return -1.
Note: The answer should be returned in an increasing format.
Examples:
Input: nums = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6] Output: [5, 6] Explanation: 5 and 6 occur more n/3 times.
Input: nums = [1, 2, 3, 4, 5] Output: [-1]
Explanation: no candidate occur more than n/3 times.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraint:
1 <= nums.size() <= 106
0 <= nums[i] <= 109
Approach 01:
-
C++
-
Python
class Solution {
public:
// Function to find the majority elements in the array
vector<int> findMajority(vector<int>& nums) {
vector<int> result;
unordered_map<int, int> countMap;
for (auto& num : nums) {
countMap[num]++;
}
for (auto& entry : countMap) {
if (entry.second > (nums.size() / 3)) {
result.push_back(entry.first);
}
}
sort(result.begin(), result.end());
if (result.empty()) {
return {-1};
}
return result;
}
};
Time Complexity
- Building the count map:We iterate through the entire array
numsto populate thecountMap. Since each insertion and update in an unordered map takes \(O(1)\) on average, this step takes \(O(n)\), where \(n\) is the size of the input array. - Iterating over the count map:We iterate over the entries of
countMap, which contains at most \(m\) unique elements, where \(m \leq n\). In the worst case, this step takes \(O(n)\). - Sorting the result:Sorting the result array takes \(O(k \log k)\), where \(k\) is the number of majority elements found. In the worst case, \(k = m\), so this step can take \(O(n \log n)\).
- Overall Time Complexity:The overall time complexity is \(O(n \log n)\), dominated by the sorting step in the worst case.
Space Complexity
- Auxiliary Space:The function uses a
countMapto store the frequencies of elements, which takes \(O(m)\) space, where \(m\) is the number of unique elements in the array. In the worst case, this could be \(O(n)\). Additionally, the result vector stores the majority elements, which takes \(O(k)\) space, and at worst, \(k = O(n)\). - Overall Space Complexity:The overall space complexity is \(O(n)\), where \(n\) is the size of the input array.
from collections import defaultdict
class Solution:
def findMajority(self, nums):
result = []
countMap = defaultdict(int)
for num in nums:
countMap[num] += 1
for key, value in countMap.items():
if value > len(nums) // 3:
result.append(key)
result.sort()
if not result:
return [-1]
return result
Time Complexity
- Building the count map:
We iterate through the entire array
numsonce to populate thecountMap, which takes \(O(n)\), where \(n\) is the size of the input array. - Iterating over the count map:
After building the count map, we iterate over its items to find keys with counts greater than \(\frac{n}{3}\), which takes \(O(m)\), where \(m\) is the number of unique elements in the array. In the worst case, \(m\) is \(O(n)\), so this step can take \(O(n)\).
- Sorting the result:
Sorting the result list takes \(O(k \log k)\), where \(k\) is the number of majority elements found. In the worst case, \(k = m\), and this step could take \(O(n \log n)\), but typically \(k\) will be much smaller.
- Overall Time Complexity:
The overall time complexity is \(O(n \log n)\), dominated by the sorting step in the worst case.
Space Complexity
- Auxiliary Space:
The function uses a
countMapto store frequencies of elements, which takes \(O(m)\) space, where \(m\) is the number of unique elements. In the worst case, this could be \(O(n)\). Additionally, theresultlist stores the majority elements, which takes \(O(k)\) space, where \(k\) is the number of majority elements, and at worst, \(k = O(n)\). - Overall Space Complexity:
The overall space complexity is \(O(n)\), where \(n\) is the size of the input array.