Occurence of an integer in a Linked List

Given a singly linked list and a key, count the number of occurrences of the given key in the linked list.

Examples:

Input: Linked List: 1->2->1->2->1->3->1, key = 1

Output: 4
Explanation: 1 appears 4 times. 

Input: Linked List: 1->2->1->2->1, key = 3

Output: 0
Explanation: 3 appears 0 times.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ number of nodes, key ≤ 10⁵
1 ≤ data of node ≤ 10⁵

Approach 01:

class Solution {
  public:
    int count(struct Node* head, int targetValue) {
        unordered_map<int, int> frequencyMap;

        while (head != nullptr) {
            ++frequencyMap[head->data];
            head = head->next;
        }

        if (frequencyMap[targetValue] != 0) {
            return frequencyMap[targetValue];
        }

        return 0;
    }
};

class Solution:
    def count(self, head, targetValue):
        frequencyMap = {}
        
        while(head != None):
            if head.data in frequencyMap:
                frequencyMap[head.data] += 1
            else:
                frequencyMap[head.data] = 1
            head = head.next
            
        return frequencyMap[targetValue] if frequencyMap.get(targetValue) != None else 0
            

Time Complexity

• Traversing the Linked List:

  The function traverses the entire linked list once, visiting each node exactly once. If there are n nodes in the list, this traversal takes \(O(n)\) time.

• Updating Frequency Map:

  For each node, it increments the count in the unordered map, which is an average \(O(1)\) operation. This happens \(n\) times during the traversal, so the time complexity for updating the map is \(O(n)\).

• Overall Time Complexity:

  The total time complexity is \(O(n)\), where n is the number of nodes in the linked list.

Space Complexity

• Frequency Map:

  The unordered map stores the frequency of each unique value in the linked list. In the worst case, there are \(n\) unique values in the list, so the space required by the map is \(O(n)\).

• Other Variables:

  There are only a few other variables (like head, targetValue, and the loop control variables), all of which take constant space \(O(1)\).

• Overall Space Complexity:

  The total space complexity is \(O(n)\), where n is the number of nodes in the linked list, because of the space used by the frequency map.