1+ class Solution {
2+ /**
3+ * First solution utilizes a hashmap and then does the due diligience of adding the
4+ * appropriate values that appear more than n/3 times
5+ * Runtime O(n) : Space O(n)
6+ */
7+ public List <Integer >majorityElement (int []nums ) {
8+ List <Integer >res =new ArrayList <>();
9+ Map <Integer ,Integer >map =new HashMap <>();
10+ for (int i =0 ;i <nums .length ;i ++) {
11+ if (map .containsKey (nums [i ]))
12+ map .put (nums [i ],map .get (nums [i ]) +1 );
13+ else
14+ map .put (nums [i ],1 );
15+ }
16+
17+ for (Map .Entry <Integer ,Integer >entry :map .entrySet ()) {
18+ int potentialCandidate =entry .getValue ();
19+ if (potentialCandidate >nums .length /3 )
20+ res .add (entry .getKey ());
21+ }
22+
23+ return res ;
24+ }
25+
26+
27+ /**
28+ * This is called Boyer-Moore Vote algorithm and the idea here is having candidates
29+ * with diff values and two counters.
30+ * For each number in the array we see if it equals the candidate and increment the count.
31+ * The two numbers left after this process are the majority candidates.
32+ * Loop through the array again then make sure that each candidate does indeed have more than n/3 occurrences
33+ *
34+ * Runtime O(n) : Space O(1)
35+ */
36+ public List <Integer >majorityElement_2 (int []nums ) {
37+ int candidate1 =0 ,candidate2 =0 ,count1 =0 ,count2 =0 ;
38+
39+ for (int num :nums ) {
40+ if (num ==candidate1 )count1 ++;
41+ else if (num ==candidate2 )count2 ++;
42+ else if (count1 ==0 ) {
43+ candidate1 =num ;
44+ count1 ++;
45+ }else if (count2 ==0 ) {
46+ candidate2 =num ;
47+ count2 ++;
48+ }else {
49+ count1 --;
50+ count2 --;
51+ }
52+ }
53+
54+ count1 =count2 =0 ;
55+ for (int num :nums ) {
56+ if (num ==candidate1 )count1 ++;
57+ else if (num ==candidate2 )count2 ++;
58+ }
59+
60+ List <Integer >res =new ArrayList <>();
61+ if (count1 >nums .length /3 )res .add (candidate1 );
62+ if (count2 >nums .length /3 )res .add (candidate2 );
63+ return res ;
64+ }
65+ }