Count minimum frequency elements in a Linked List in C++

Hello every one, here in this article, we have to count the minimum frequency of elements in a Linked List in C++. In simple terms, we have to determine those elements in the list, who occur the least no. of times.

If we have an array {5,5,7,8,8,9,1}. In this array, the min freq is 3 as only 7, 9 and 1 occur least. So how do we do this?

Start by going along the linked list. We then employ a data structure known as a hash table. In this, we store the occurrence of elements of the linked list. the penultimate step is to go through the hash table to determine the least frequency available. The last step is to traverse the hash table to find the occurrence of elements. This is then matched with the minimum frequency obtained earlier. If both matches, we add this frequency to count. Here is a C++ code to formulate it.

We start by defining a linked list and a function to push the data into the linked list.

#include <bits/stdc++.h> 
using namespace std; 


struct Node { 
  int k; 
  struct Node* n; 
}; 


void pushinto(struct Node** hr, int new_key) 
{ 
  struct Node* new_node = new Node; 
  new_node->k = new_key; 
  new_node->n = (*hr); 
  (*hr) = new_node; 
} 

 

We then declare a function to count the minimum by traversing the array and using a map in C++. We also declare the main() and input the values.

int check(struct Node* h) 
{ 
  map<int, int> m; 
  struct Node* present = h; 
  while (present != NULL) { 
    int d = present->k; 
    m[d]++; 
    present = present->n; 
  } 

  present = h; 
  int freq, ans = 0; 
  for (auto it = m.begin(); it != m.end(); it++) { 
    if (it->second <= freq) { 
      freq = it->second; 
    } 
  } 

  for (auto it = m.begin(); it != m.end(); it++) { 
    if (it->second == freq) { 
      ans += (it->second); 
    } 
  } 

  return ans; 
} 

int main() 
{ 
  struct Node* h = NULL; 

  pushinto(&h, 5); 
  pushinto(&h, 5); 
  pushinto(&h, 7); 
  pushinto(&h, 8); 
  pushinto(&h, 8);
  pushinto(&h, 9);
  pushinto(&h, 1);
   
  cout<<check(h) << endl; 
  return 0; 
} 

 

The output would be as:-

 3
..Program finished with exit code 0