Problem Statement :-
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example
Input : nums = [3,2,3]
Result : 3
Solution 1
in this solution, we just need to find the two most frequent elements in the array nums
and count the frequency of the frequent elements if the count is greater than N/3
then return the elements.
let's discuss this approach step by step.
step-1 declare some variables.
firstMajNum = null
secondMajNum = null
firstMajCount = 0
secondMajCount = 0
firstMajNum
& secondMajNum
will store the currently most frequent elements.
_firstMajCount
& secondMajCount
will store the frequency of the current most frequent element._
step-2 run a loop from i=0
to n
.
1. get the
ith
element from arraynums
.
element = nums[i]
2. increase the
firstMajCount
ifelement == firstMajNum
3. increase the
secondMajCount
ifelement == secondMajNum
4. declare
firstMajCount
&firstMajNum
iffirstMajCount == 0
.
firstMajCount = 1
firstMajNum = element
5. declare
secondMajCount
&secondMajNum
ifsecondMajCount == 0
secondMajCount = 1
secondMajNum = element
6. if all the above cases not satisfy, decrease the
secondMajCount
&secondMajCount
by1
step-3 count the frequency of the most frequent elements of the array & return those elements that are >N/3
.
see the java implementation.
Java
class Solution {
public List<Integer> majorityElement(int[] nums) {
Integer firstMajNum = null;
Integer secondMajNum = null;
int firstMajCount = 0;
int secondMajCount = 0;
for(int i=0; i<nums.length; i++){
int element = nums[i];
if(firstMajNum != null && element == firstMajNum){
firstMajCount++;
}else if (secondMajNum != null && element == secondMajNum){
secondMajCount++;
}else if(firstMajCount == 0){
firstMajNum = element;
firstMajCount = 1;
}else if(secondMajCount == 0){
secondMajNum = element;
secondMajCount = 1;
}else{
firstMajCount--;
secondMajCount--;
if(firstMajCount == 0) firstMajNum = null;
if(secondMajCount == 0) secondMajNum = null;
}
}
firstMajCount = 0;
secondMajCount = 0;
for(int e : nums){
if(firstMajNum != null && firstMajNum == e) firstMajCount++;
if(secondMajNum != null && secondMajNum == e) secondMajCount++;
}
List<Integer> ans = new ArrayList<Integer>();
if(firstMajCount > nums.length/3) ans.add(firstMajNum);
if(secondMajCount > nums.length/3) ans.add(secondMajNum);
return ans;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
Thank you for reading this article i hope you like and plz share with your dev friends. if you find something wrong let me in the comment section.
Top comments (0)