Given a linked list, find majority element. An element is called Majority element if it appears more than or equal to n/2 times where n is total number of nodes in the linked list.
Examples:
Input : 1->2->3->4->5->1->1->1->NULL Output : 1 Explanation 1 occurs 4 times Input :10->23->11->9->54->NULL Output :NO majority element
Method 1(simple): Run two loops starting from head and count frequency of each element iteratively. Print the element whose frequency is greater than or equal to n/2. In this approach time complexity will be O(n*n) where n is the number of nodes in the linked list.
Implementation:
C++
// C++ program to find majority element in // a linked list#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; struct Node* next;};/* Function to get the nth node from the last of a linked list*/int majority(struct Node* head){ struct Node* p = head; int total_count = 0, max_count = 0, res = -1; while (p != NULL) { // Count all occurrences of p->data int count = 1; struct Node* q = p->next; while (q != NULL) { if (p->data == q->data) count++; q = q->next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p->data; } p = p->next; total_count++; } if (max_count >= total_count/2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1;}void push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}/* Driver program to test above function*/int main(){ /* Start with the empty list */ struct Node* head = NULL; // create linked push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int res = majority(head); if (res != (-1)) cout << "Majority element is " << res; else cout << "No majority element"; return 0;} |
Java
// Java program to find majority element in // a linked listimport java.util.*;class GFG{static Node head;/* Link list node */static class Node { int data; Node next;};/* Function to get the nth node from the last of a linked list*/static int majority(Node head){ Node p = head; int total_count = 0, max_count = 0, res = -1; while (p != null) { // Count all occurrences of p->data int count = 1; Node q = p.next; while (q != null) { if (p.data == q.data) count++; q = q.next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p.data; } p = p.next; total_count++; } if (max_count >= total_count / 2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1;}static void push(Node head_ref, int new_data){ Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;}// Driver Codepublic static void main(String[] args) { /* Start with the empty list */ head = null; // create linked push(head, 1); push(head, 1); push(head, 1); push(head, 5); push(head, 4); push(head, 3); push(head, 2); push(head, 1); int res = majority(head); if (res != (-1)) System.out.println("Majority element is " + res); else System.out.println("No majority element"); }}// This code is contributed by Princi Singh |
Python3
# Python3 program to find majority element in # a linked listhead = None# Link list node class Node : def __init__(self): self.data = 0 self.next = None# Function to get the nth node from # the last of a linked listdef majority(head): p = head total_count = 0 max_count = 0 res = -1 while (p != None): # Count all occurrences of p->data count = 1 q = p.next while (q != None): if (p.data == q.data): count = count + 1 q = q.next # Update max_count and res if count # is more than max_count if (count > max_count): max_count = count res = p.data p = p.next total_count = total_count + 1 if (max_count >= total_count / 2): return res # if we reach here it means no # majority element is present. # and we assume that all the # element are positive return -1def push( head_ref, new_data): global head new_node = Node() new_node.data = new_data new_node.next = head_ref head_ref = new_node head = head_ref# Driver Code# Start with the empty list head = None# create linkedpush(head, 1)push(head, 1)push(head, 1)push(head, 5)push(head, 4)push(head, 3)push(head, 2)push(head, 1)res = majority(head)if (res != (-1)): print("Majority element is " , res)else: print("No majority element") # This code is contributed by Arnab Kundu |
C#
// C# program to find majority element in // a linked listusing System; class GFG{ static Node head; /* Link list node */ public class Node { public int data; public Node next; }; /* Function to get the nth node from the last of a linked list*/ static int majority(Node head) { Node p = head; int total_count = 0, max_count = 0, res = -1; while (p != null) { // Count all occurrences of p->data int count = 1; Node q = p.next; while (q != null) { if (p.data == q.data) count++; q = q.next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p.data; } p = p.next; total_count++; } if (max_count >= total_count / 2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1; } static void push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref; }// Driver Codepublic static void Main(String[] args) { /* Start with the empty list */ head = null; // create linked push(head, 1); push(head, 1); push(head, 1); push(head, 5); push(head, 4); push(head, 3); push(head, 2); push(head, 1); int res = majority(head); if (res != (-1)) Console.WriteLine("Majority element is " + res); else Console.WriteLine("No majority element"); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to find majority element in // a linked list var head = null;/* Link list node */class Node { constructor() { this.data = 0; this.next = null; }};/* Function to get the nth node from the last of a linked list*/function majority(head){ var p = head; var total_count = 0, max_count = 0, res = -1; while (p != null) { // Count all occurrences of p->data var count = 1; var q = p.next; while (q != null) { if (p.data == q.data) count++; q = q.next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p.data; } p = p.next; total_count++; } if (max_count >= total_count / 2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1;}function push(head_ref, new_data){ var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;}// Driver Code/* Start with the empty list */head = null;// create linkedpush(head, 1);push(head, 1);push(head, 1);push(head, 5);push(head, 4);push(head, 3);push(head, 2);push(head, 1);var res = majority(head);if (res != (-1)) document.write("Majority element is " + res);else document.write("No majority element");</script> |
Output
Majority element is 1
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Method 2: Use hashing technique. We count frequency of each element and then we print the element whose frequency is ? n/2;
Implementation:
C++
// CPP program to find majority element// in the linked list using hashing#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; struct Node* next;};/* Function to get the nth node from the last of a linked list*/int majority(struct Node* head){ struct Node* p = head; // Storing elements and their frequencies // in a hash table. unordered_map<int, int> hash; int total_count = 0; while (p != NULL) { // increase every element // frequency by 1 hash[p->data]++; p = p->next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 for (auto x : hash) if (x.second >= total_count/2) return x.first; // If we reach here means no majority element // is present. We assume that all the element // are positive return -1;}void push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Driver program to test above functionint main(){ /* Start with the empty list */ struct Node* head = NULL; push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int res = majority(head); if (res != (-1)) cout << "majority element is " << res; else cout << "NO majority element"; return 0;} |
Java
// JAVA program to find majority element// in the linked list using hashingimport java.util.*;class GFG{/* Link list node */static class Node{ int data; Node next;};/* Function to get the nth node from the lastof a linked list*/static int majority(Node head){ Node p = head; // Storing elements and their frequencies // in a hash table. HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); int total_count = 0; while (p != null) { // increase every element // frequency by 1 if(hash.containsKey(p.data)) hash.put(p.data, hash.get(p.data) + 1); else hash.put(p.data, 1); p = p.next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 for (Map.Entry<Integer,Integer> x : hash.entrySet()) if (x.getValue() >= total_count/2) return x.getKey(); // If we reach here means no majority element // is present. We assume that all the element // are positive return -1;}static Node push(Node head_ref, int new_data){ Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref;}// Driver codepublic static void main(String[] args){ /* Start with the empty list */ Node head = null; head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); int res = majority(head); if (res != (-1)) System.out.print("majority element is " + res); else System.out.print("NO majority element");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to find majority element# in the linked list using hashing ''' Link list node '''class Node: def __init__(self, data): self.data = data self.next = None ''' Function to get the nth node from the last of a linked list'''def majority(head): p = head; # Storing elements and their frequencies # in a hash table. hash = dict() total_count = 0; while (p != None): # increase every element # frequency by 1 if p.data not in hash: hash[p.data] = 0 hash[p.data] += 1 p = p.next; total_count += 1 # Check if frequency of any element # is more than or equal to total_count/2 for x in hash.keys(): if (hash[x] >= total_count//2): return x; # If we reach here means no majority element # is present. We assume that all the element # are positive return -1; def push(head_ref, new_data): new_node = Node(new_data) new_node.next = (head_ref); (head_ref) = new_node; return head_ref # Driver codeif __name__=='__main__': ''' Start with the empty list ''' head = None head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); res = majority(head); if (res != (-1)): print("majority element is " + str(res)) else: print("NO majority element") # This code is contributed by rutvik_56 |
C#
// C# program to find majority element// in the linked list using hashingusing System;using System.Collections.Generic;class GFG{/* Link list node */public class Node{ public int data; public Node next;};/* Function to get the nth nodefrom the last of a linked list*/static int majority(Node head){ Node p = head; // Storing elements and their frequencies // in a hash table. Dictionary<int, int> hash = new Dictionary<int, int>(); int total_count = 0; while (p != null) { // increase every element // frequency by 1 if(hash.ContainsKey(p.data)) hash[p.data] = hash[p.data] + 1; else hash.Add(p.data, 1); p = p.next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 foreach(KeyValuePair<int, int> x in hash) if (x.Value >= total_count/2) return x.Key; // If we reach here means no majority element // is present. We assume that all the element // are positive return -1;}static Node push(Node head_ref, int new_data){ Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref;}// Driver codepublic static void Main(String[] args){ /* Start with the empty list */ Node head = null; head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); int res = majority(head); if (res != (-1)) Console.Write("majority element is " + res); else Console.Write("NO majority element");}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find majority element // in the linked list using hashing /* Link list node */ class Node { constructor() { this.data = 0; this.next = null; } } /* Function to get the nth nodefrom the last of a linked list*/ function majority(head) { var p = head; // Storing elements and their frequencies // in a hash table. var hash = {}; var total_count = 0; while (p != null) { // increase every element // frequency by 1 if (hash.hasOwnProperty(p.data)) hash[p.data] = hash[p.data] + 1; else hash[p.data] = 1; p = p.next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 for (const [key, value] of Object.entries(hash)) { if (value >= parseInt(total_count / 2)) return key; // If we reach here means no majority element // is present. We assume that all the element // are positive return -1; } } function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Driver code /* Start with the empty list */ var head = null; head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); var res = majority(head); if (res != -1) document.write("majority element is " + res); else document.write("NO majority element"); // This code is contributed by rdtank. </script> |
Output
majority element is 1
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
