Given a linked list of size N consisting of a string as node value, the task is to find the majority string, having frequency greater than [N/3], in the linked list.
Note: It is guaranteed that there is only one majority string.
Examples:
Input: head -> neveropen -> neveropen -> abcd -> game -> knight -> neveropen -> harry.
Output: neveropen.
Explanation:
The frequency of neveropen string in link list is 3 which is greater than [7/3] i.e 2.Input: head -> hot -> hot -> cold -> hot -> hot
Output: hot
Explanation:
The frequency of hot string in the link list is 4 which is greater than [5/3] i.e 1.
Naive Approach:
Store the frequency of every string in a Map. Traverse the map and look for the string whose frequency is ? N / 3.
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach:
The idea is based on Moore’s Voting algorithm.
Find two candidates and check if any of these two candidates is actually a majority element or not.
Below is the implementation of the above approach:
C++
// C++ program to find an// element with frequency// of at least N / 3// in a linked list#include <bits/stdc++.h>using namespace std;// Structure of a node// for the linked liststruct node { string i; node* next = NULL;};// Utility function to// create a nodestruct node* newnode(string s){ struct node* temp = (struct node*) malloc(sizeof(struct node)); temp->i = s; temp->next = NULL; return temp;}// Function to find and return// the element with frequency// of at least N/3string Majority_in_linklist(node* head){ // Candidates for // being the required // majority element string s = "", t = ""; // Store the frequencies // of the respective candidates int p = 0, q = 0; node* ptr = NULL; // Iterate all nodes while (head != NULL) { if (s.compare(head->i) == 0) { // Increase frequency // of candidate s p = p + 1; } else { if (t.compare(head->i) == 0) { // Increase frequency // of candidate t q = q + 1; } else { if (p == 0) { // Set the new string as // candidate for majority s = head->i; p = 1; } else { if (q == 0) { // Set the new string as // second candidate // for majority t = head->i; q = 1; } else { // Decrease the frequency p = p - 1; q = q - 1; } } } } head = head->next; } head = ptr; p = 0; q = 0; // Check the frequency of two // final selected candidate linklist while (head != NULL) { if (s.compare(head->i) == 0) { // Increase the frequency // of first candidate p = 1; } else { if (t.compare(head->i) == 0) { // Increase the frequency // of second candidate q = 1; } } head = head->next; } // Return the string with // higher frequency if (p > q) { return s; } else { return t; }}// Driver Codeint main(){ node* ptr = NULL; node* head = newnode("neveropen"); head->next = newnode("neveropen"); head->next->next = newnode("abcd"); head->next->next->next = newnode("game"); head->next->next->next->next = newnode("game"); head->next->next->next->next->next = newnode("knight"); head->next->next->next->next->next->next = newnode("harry"); head->next->next->next->next->next->next ->next = newnode("neveropen"); cout << Majority_in_linklist(head) << endl; return 0;} |
Java
// Java program to find an // element with frequency // of at least N / 3 // in a linked list class GFG{// Structure of a node // for the linked list static class node{ String i; node next = null; }; // Utility function to // create a node static node newnode(String s) { node temp = new node(); temp.i = s; temp.next = null; return temp; } // Function to find and return // the element with frequency // of at least N/3 static String Majority_in_linklist(node head) { // Candidates for // being the required // majority element String s = ""; String t = ""; // Store the frequencies // of the respective candidates int p = 0, q = 0; node ptr = null; // Iterate all nodes while (head != null) { if (s.equals(head.i)) { // Increase frequency // of candidate s p = p + 1; } else { if (t.equals(head.i)) { // Increase frequency // of candidate t q = q + 1; } else { if (p == 0) { // Set the new string as // candidate for majority s = head.i; p = 1; } else { if (q == 0) { // Set the new string as // second candidate // for majority t = head.i; q = 1; } else { // Decrease the frequency p = p - 1; q = q - 1; } } } } head = head.next; } head = ptr; p = 0; q = 0; // Check the frequency of two // final selected candidate linklist while (head != null) { if (s.equals(head.i)) { // Increase the frequency // of first candidate p = 1; } else { if (t.equals(head.i)) { // Increase the frequency // of second candidate q = 1; } } head = head.next; } // Return the String with // higher frequency if (p > q) { return s; } else { return t; } } // Driver Code public static void main(String []arg){ node ptr = null; node head = newnode("neveropen"); head.next = newnode("neveropen"); head.next.next = newnode("abcd"); head.next.next.next = newnode("game"); head.next.next.next.next = newnode("game"); head.next.next.next.next.next = newnode("knight"); head.next.next.next.next.next.next = newnode("harry"); head.next.next.next.next.next.next.next = newnode("neveropen"); System.out.println(Majority_in_linklist(head)); } }// This code is contributed by rutvik_56 |
Python3
# Python3 program to find an element# with frequency of at least N / 3 # in a linked list # Structure of a node # for the linked listclass Node: def __init__(self, s): self.i = s self.next = None # Function to find and return # the element with frequency # of at least N/3 def Majority_in_linklist(head): # Candidates for # being the required # majority element s, t = "", "" # Store the frequencies # of the respective candidates p, q = 0, 0 ptr = None # Iterate all nodes while head != None: if s == head.i: # Increase frequency # of candidate s p = p + 1 else: if t == head.i: # Increase frequency # of candidate t q = q + 1 else: if p == 0: # Set the new string as # candidate for majority s = head.i p = 1 else: if q == 0: # Set the new string as # second candidate # for majority t = head.i q = 1 else: # Decrease the frequency p = p - 1 q = q - 1 head = head.next head = ptr p = 0 q = 0 # Check the frequency of two # final selected candidate linklist while head != None: if s == head.i: # Increase the frequency # of first candidate p = 1 else: if t == head.i: # Increase the frequency # of second candidate q = 1 head = head.next # Return the string with # higher frequency if p > q: return s else: return t# Driver codeptr = Nonehead = Node("neveropen") head.next = Node("neveropen") head.next.next = Node("abcd") head.next.next.next = Node("game") head.next.next.next.next = Node("game") head.next.next.next.next.next = Node("knight") head.next.next.next.next.next.next = Node("harry") head.next.next.next.next.next.next.next = Node("neveropen") print(Majority_in_linklist(head))# This code is contributed by stutipathak31jan |
C#
// C# program to find an element with// frequency of at least N / 3 in a// linked list using System;using System.Collections;using System.Collections.Generic;class GFG{ // Structure of a node // for the linked list class node{ public string i; public node next = null; }; // Utility function to // create a node static node newnode(string s) { node temp = new node(); temp.i = s; temp.next = null; return temp; } // Function to find and return // the element with frequency // of at least N/3 static string Majority_in_linklist(node head) { // Candidates for // being the required // majority element string s = ""; string t = ""; // Store the frequencies // of the respective candidates int p = 0, q = 0; node ptr = null; // Iterate all nodes while (head != null) { if (s.Equals(head.i)) { // Increase frequency // of candidate s p = p + 1; } else { if (t.Equals(head.i)) { // Increase frequency // of candidate t q = q + 1; } else { if (p == 0) { // Set the new string as // candidate for majority s = head.i; p = 1; } else { if (q == 0) { // Set the new string as // second candidate // for majority t = head.i; q = 1; } else { // Decrease the frequency p = p - 1; q = q - 1; } } } } head = head.next; } head = ptr; p = 0; q = 0; // Check the frequency of two // final selected candidate linklist while (head != null) { if (s.Equals(head.i)) { // Increase the frequency // of first candidate p = 1; } else { if (t.Equals(head.i)) { // Increase the frequency // of second candidate q = 1; } } head = head.next; } // Return the string with // higher frequency if (p > q) { return s; } else { return t; } } // Driver Code public static void Main(string []arg){ node head = newnode("neveropen"); head.next = newnode("neveropen"); head.next.next = newnode("abcd"); head.next.next.next = newnode("game"); head.next.next.next.next = newnode("game"); head.next.next.next.next.next = newnode("knight"); head.next.next.next.next.next.next = newnode("harry"); head.next.next.next.next.next.next.next = newnode("neveropen"); Console.Write(Majority_in_linklist(head)); } }// This code is contributed by pratham76 |
Javascript
<script> // JavaScript program to find an element with // frequency of at least N / 3 in a // linked list // Structure of a node // for the linked list class node { constructor() { this.i = ""; this.next = null; } } // Utility function to // create a node function newnode(s) { var temp = new node(); temp.i = s; temp.next = null; return temp; } // Function to find and return // the element with frequency // of at least N/3 function Majority_in_linklist(head) { // Candidates for // being the required // majority element var s = ""; var t = ""; // Store the frequencies // of the respective candidates var p = 0, q = 0; var ptr = null; // Iterate all nodes while (head != null) { if (s == head.i) { // Increase frequency // of candidate s p = p + 1; } else { if (t == head.i) { // Increase frequency // of candidate t q = q + 1; } else { if (p == 0) { // Set the new string as // candidate for majority s = head.i; p = 1; } else { if (q == 0) { // Set the new string as // second candidate // for majority t = head.i; q = 1; } else { // Decrease the frequency p = p - 1; q = q - 1; } } } } head = head.next; } head = ptr; p = 0; q = 0; // Check the frequency of two // final selected candidate linklist while (head != null) { if (s == head.i) { // Increase the frequency // of first candidate p = 1; } else { if (t == head.i) { // Increase the frequency // of second candidate q = 1; } } head = head.next; } // Return the string with // higher frequency if (p > q) { return s; } else { return t; } } // Driver Code var head = newnode("neveropen"); head.next = newnode("neveropen"); head.next.next = newnode("abcd"); head.next.next.next = newnode("game"); head.next.next.next.next = newnode("game"); head.next.next.next.next.next = newnode("knight"); head.next.next.next.next.next.next = newnode("harry"); head.next.next.next.next.next.next.next = newnode("neveropen"); document.write(Majority_in_linklist(head)); // This code is contributed by rdtank. </script> |
Output:
neveropen
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
