Find Frequency

Unit 3 Session 2 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What should the function return if the linked list is empty?

  • A: The function should return 0 as the frequency of any value in an empty list is zero.

• Q: Does the function handle different data types stored in the linked list nodes, or are we assuming all values are of the same type?

  • A: The function as provided assumes all nodes store values of the same type that can be compared with val.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the linked list, counting the number of times the specified value appears.

1) Initialize a counter to zero to keep track of the number of times `val` appears.
2) Start traversing the linked list from the head.
3) For each node, check if the node's value equals `val`.
   - If yes, increment the counter.
4) Continue until the end of the list is reached.
5) Return the counter value.

⚠️ Common Mistakes

• Not initializing the counter to zero before starting the traversal.
• Not handling the case where the linked list is empty.
• Assuming node values are comparable to val without checking type consistency.

I-mplement

def count_element(head, val):
    count = 0  # Initialize a counter for the occurrences
    current = head  # Start with the head of the list
    
    while current:
        if current.value == val:
            count += 1  # Increment count if the current node's value matches val
        current = current.next  # Move to the next node
    
    return count  # Return the total count of occurrences

**Time Complexity:** The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because each node is visited exactly once.

**Space Complexity:** The space complexity is O(1), as we only use a fixed amount of space (for the counter and a pointer to traverse the list).

**Explanation:**
- **Time Complexity:** Each node in the linked list is visited once, hence the complexity is proportional to the length of the list.
- **Space Complexity:** Only a small, constant amount of space is needed for the counter and the current pointer regardless of the size of the input list.