Be the first user to complete this post

  • 0
Add to List
Beginner

234. Majority Element – Part 1

Objective:  Given an array of integer write an algorithm to find the majority element in it (if exist).

Majority Element: If an element appears more than n/2 times in array where n is the size of the array.

Example:

int [] arrA = {1,3,5,5,5,5,4,1,5};
Output: Element appearing more than n/2 times: 5

int []arrA = {1,2,3,4};
Output: No element appearing more than n/2 times

Click here to read O(n) approach-Boyer–Moore majority vote algorithm

Approach 1: Brute Force

Use nested for loops and count each element and if count>n/2 for each element.

Time Complexity: O(n^2)




public class Main { public static void find(int [] arrA){ boolean found = false; for (int i = 0; i <arrA.length ; i++) { int x = arrA[i]; int count = 1; for (int j = i+1; j <arrA.length ; j++) { if(x==arrA[j]) count++; } if(count>arrA.length/2) { System.out.println("Element appearing more than n/2 times: " + x); found = true; } } if(!found) System.out.println("No element appearing more than n/2 times"); } public static void main(String[] args) { int [] arrA = {1,3,5,5,5,5,4,1,5}; find(arrA); } }



def find_majority_element(arr): found = False for i in range(len(arr)): x = arr[i] count = 1 for j in range(i + 1, len(arr)): if x == arr[j]: count += 1 if count > len(arr) / 2: print("Element appearing more than n/2 times:", x) found = True if not found: print("No element appearing more than n/2 times") if __name__ == "__main__": arrA = [1, 3, 5, 5, 5, 5, 4, 1, 5] find_majority_element(arrA)



package main import ( "fmt" ) func findMajorityElement(arrA []int) { found := false for i := 0; i < len(arrA); i++ { x := arrA[i] count := 1 for j := i + 1; j < len(arrA); j++ { if x == arrA[j] { count++ } } if count > len(arrA)/2 { fmt.Println("Element appearing more than n/2 times:", x) found = true } } if !found { fmt.Println("No element appearing more than n/2 times") } } func main() { arrA := []int{1, 3, 5, 5, 5, 5, 4, 1, 5} findMajorityElement(arrA) }

Approach 2: Hash Map

  • Store the count of each element in Hash map.
  • Iterate through hash map and check if any element has count >n/2

Time Complexity: O(n), Space Complexity: O(n)




import java.util.*; public class Main { public static void find(int [] arrA){ boolean found = false; HashMap<Integer,Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i <arrA.length ; i++) { if(map.containsKey(arrA[i])){ int count = map.get(arrA[i]); map.put(arrA[i],++count); }else map.put(arrA[i],1); } Set set = map.keySet(); Iterator<Integer> iterator = set.iterator(); while (iterator.hasNext()){ int key = iterator.next(); if(map.get(key)>arrA.length/2){ System.out.println("(Hashing)Element appearing more than n/2 times: " + key); found = true; break; } } if(!found) System.out.println("No element appearing more than n/2 times"); } public static void main(String[] args) { int [] arrA = {1,3,5,5,5,5,4,1,5}; find(arrA); } }



def find_majority_element(arrA): found = False element_count = {} for num in arrA: if num in element_count: element_count[num] += 1 else: element_count[num] = 1 for key, value in element_count.items(): if value > len(arrA) / 2: print("(Hashing) Element appearing more than n/2 times:", key) found = True break if not found: print("No element appearing more than n/2 times") if __name__ == "__main__": arrA = [1, 3, 5, 5, 5, 5, 4, 1, 5] find_majority_element(arrA)



package main import "fmt" func findMajorityElement(arrA []int) { found := false elementCount := make(map[int]int) for _, num := range arrA { if _, ok := elementCount[num]; ok { elementCount[num]++ } else { elementCount[num] = 1 } } for key, value := range elementCount { if value > len(arrA)/2 { fmt.Println("(Hashing) Element appearing more than n/2 times:", key) found = true break } } if !found { fmt.Println("No element appearing more than n/2 times") } } func main() { arrA := []int{1, 3, 5, 5, 5, 5, 4, 1, 5} findMajorityElement(arrA) }

Approach 3: Sorting

  • Sort array, this will bring all the same elements together.
  • Iterate through array and check if any element has count >n/2

Time Complexity: O(nlogn), Space Complexity: O(1)




import java.util.*; public class Main { public static void find(int [] arrA){ if(arrA.length==0) return; boolean found = false; Arrays.sort(arrA); int count = 1; int x = arrA[0]; for (int i = 1; i <arrA.length ; i++) { if(x==arrA[i]){ count++; if(count>arrA.length/2) { System.out.println("(Sorting)Element appearing more than n/2 times: " + x); found = true; break; } }else{ x = arrA[i]; count = 1; } } if(!found) System.out.println("No element appearing more than n/2 times"); } public static void main(String[] args) { int [] arrA = {1,3,5,5,5,5,4,1,5}; find(arrA); } }



def find_majority_element(arrA): if len(arrA) == 0: return found = False arrA.sort() count = 1 x = arrA[0] for i in range(1, len(arrA)): if x == arrA[i]: count += 1 if count > len(arrA) // 2: print("(Sorting) Element appearing more than n/2 times:", x) found = True break else: x = arrA[i] count = 1 if not found: print("No element appearing more than n/2 times") if __name__ == "__main__": arrA = [1, 3, 5, 5, 5, 5, 4, 1, 5] find_majority_element(arrA)



package main import ( "fmt" "sort" ) func findMajorityElement(arrA []int) { if len(arrA) == 0 { return } found := false sort.Ints(arrA) count := 1 x := arrA[0] for i := 1; i < len(arrA); i++ { if x == arrA[i] { count++ if count > len(arrA)/2 { fmt.Println("(Sorting) Element appearing more than n/2 times:", x) found = true break } } else { x = arrA[i] count = 1 } } if !found { fmt.Println("No element appearing more than n/2 times") } } func main() { arrA := []int{1, 3, 5, 5, 5, 5, 4, 1, 5} findMajorityElement(arrA) }

Output:

Element appearing more than n/2 times: 5