Count of Nodes in a LinkedList whose value is equal to their frequency

0 0 5 minutes read

Given a Singly linked list, the task is to count the number of nodes whose data value is equal to its frequency.

Examples:

Input: Linked list = 2 -> 3 -> 3 -> 3 -> 4 -> 2
Output: 2
Frequency of element 2 is 2
Frequency of element 3 is 3
Frequency of element 4 is 1
So, 2 and 3 are elements which have same frequency as it’s value

Input: Linked list = 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 1

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach:
Approach to solve this problem is as following

Iterate over the linked list and store the frequency of every element of the array using a map
Iterate over the map and count the number of elements whose frequency is equal to their value

Below is the implementation of the above approach:

C++

/* Link list node */
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
};
 
// Function to add a node at the 
// beginning of List
void push(Node** head_ref, int data)  
{  
    /* allocate node */
    Node* new_node =new Node(); 
   
    /* put in the data */
    new_node->data = data;  
   
    // link the old list of the new
    // node
    new_node->next = (*head_ref);  
   
    // move the head to point to the
    // new node
    (*head_ref) = new_node;  
} 
 
 
// Counts the no. of occurrences of a
// node in a linked list
int countValuesWithSameFreq(Node* start)
{
    map<int, int> mpp;
    Node* current = start;
    int count = 0;
    while (current != NULL) {
        mpp[current->data] += 1;
        current = current->next;
    }
    int ans = 0;
    for (auto x : mpp) {
        int value = x.first;
        int freq = x.second;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq) {
            ans++;
        }
    }
    return ans;
}
 
// main program
int main()
{
    Node* head = NULL;
    push(&head, 3);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 2);
    push(&head, 3);
 
    cout << countValuesWithSameFreq(head);
    return 0;
}

Java

/* Link list node */
import java.util.*;
 
class GFG{
 
public static class Node
{
    int data;
    Node next;
};
 
// Function to add a node at the
// beginning of List
static Node push(Node head_ref, int data)
{
     
    // Allocate node 
    Node new_node = new Node();
 
    // Put in the data 
    new_node.data = data;
 
    // Link the old list of the new
    // node
    new_node.next = head_ref;
 
    // Move the head to point to the
    // new node
    head_ref = new_node;
    return head_ref;
}
 
// Counts the no. of occurrences of a
// node in a linked list
static int countValuesWithSameFreq(Node start)
{
    HashMap<Integer, Integer> mpp = new HashMap<>();
     
    Node current = start;
    while (current != null)
    {
        if (mpp.containsKey(current.data)) 
        {
            mpp.put(current.data,
                     mpp.get(current.data) + 1);
        }
        else
        {
            mpp.put(current.data, 1);
        }
        current = current.next;
    }
    int ans = 0;
    for(Map.Entry<Integer, 
                  Integer> x : mpp.entrySet())
    {
        int value = x.getKey();
        int freq = x.getValue();
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq)
        {
            ans++;
        }
    }
    return ans;
}
 
// Driver code 
public static void main(String[] args)
{
    Node head = null;
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 3);
    head = push(head, 2);
    head = push(head, 2);
    head = push(head, 3);
 
    System.out.print(countValuesWithSameFreq(head));
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Link list node 
class Node:
     
    def __init(self, next):
         
        self.data = 0
        self.next = None
  
# Function to add a node at the 
# beginning of List
def push(head_ref, data):
     
    # Allocate node 
    new_node = Node()
     
    # Put in the data 
    new_node.data = data
    
    # Link the old list of the new
    # node
    new_node.next = (head_ref)  
    
    # Move the head to point to the
    # new node
    (head_ref) = new_node
     
    return head_ref
     
# Counts the no. of occurrences of a
# node in a linked list
def countValuesWithSameFreq(start):
     
    mpp = dict()
    current = start
    count = 0
     
    while (current != None):
        if current.data not in mpp:
            mpp[current.data] = 0
             
        mpp[current.data] += 1
        current = current.next
     
    ans = 0
     
    for x in mpp.keys():
        value = x
        freq = mpp[x]
         
        # Check if value equals to frequency
        # and increment the count
        if (value == freq):
            ans += 1
             
    return ans
  
# Driver code
if __name__=='__main__':
     
    head = None
    head = push(head, 3)
    head = push(head, 4)
    head = push(head, 3)
    head = push(head, 2)
    head = push(head, 2)
    head = push(head, 3)
  
    print(countValuesWithSameFreq(head))
     
# This code is contributed by rutvik_56

C#

/* Link list node */
using System;
using System.Collections.Generic;
 
class GFG{
 
public class Node
{
    public int data;
    public Node next;
};
 
// Function to add a node at the
// beginning of List
static Node push(Node head_ref, int data)
{
     
    // Allocate node 
    Node new_node = new Node();
 
    // Put in the data 
    new_node.data = data;
 
    // Link the old list of the new
    // node
    new_node.next = head_ref;
 
    // Move the head to point to the
    // new node
    head_ref = new_node;
    return head_ref;
}
 
// Counts the no. of occurrences of a
// node in a linked list
static int countValuesWithSameFreq(Node start)
{
    Dictionary<int, 
                 int> mpp = new Dictionary<int, 
                                           int>();
     
    Node current = start;
    while (current != null)
    {
        if (mpp.ContainsKey(current.data)) 
        {
            mpp[current.data] = mpp[current.data] + 1;
        }
        else
        {
            mpp.Add(current.data, 1);
        }
        current = current.next;
    }
    int ans = 0;
     
    foreach(KeyValuePair<int, int> x in mpp)
    {
        int value = x.Key;
        int freq = x.Value;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq)
        {
            ans++;
        }
    }
    return ans;
}
 
// Driver code 
public static void Main(String[] args)
{
    Node head = null;
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 3);
    head = push(head, 2);
    head = push(head, 2);
    head = push(head, 3);
 
    Console.Write(countValuesWithSameFreq(head));
}
}
 
// This code is contributed by Rohit_ranjan

Javascript

<script>
 
/* Link list node */
 
class Node
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
};
 
// Function to add a node at the
// beginning of List
function push(head_ref, data)
{
     
    // Allocate node 
    var new_node = new Node();
 
    // Put in the data 
    new_node.data = data;
 
    // Link the old list of the new
    // node
    new_node.next = head_ref;
 
    // Move the head to point to the
    // new node
    head_ref = new_node;
    return head_ref;
}
 
// Counts the no. of occurrences of a
// node in a linked list
function countValuesWithSameFreq(start)
{
    var mpp = new Map();
     
    var current = start;
    while (current != null)
    {
        if (mpp.has(current.data)) 
        {
            mpp.set(current.data , mpp.get(current.data)+1);
        }
        else
        {
            mpp.set(current.data, 1);
        }
        current = current.next;
    }
    var ans = 0;
     
    mpp.forEach((value, key) => {
        var value = value;
        var freq = key;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq)
        {
            ans++;
        }
    });
    return ans;
}
 
// Driver code 
var head = null;
head = push(head, 3);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 2);
head = push(head, 3);
document.write(countValuesWithSameFreq(head));
 
</script>

Output:

Complexity Analysis:
Time Complexity: For a given linked list of size n, we are iterating over it once. So the time complexity of this solution is O(n)
Space Complexity: For a given linked list of size n, we are using an extra map which can have maximum of n key-values, so space complexity of this solution is O(n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!