educative.io

Educative

Can improve the time complexity of this solution to O(V)

A reader sent us the following feedback:

Instead of traversing through all the nodes in DLL and finding the count, we can directly use the ‘size’ attribute of the DLL in O(1) time. Hence overall time complexity will be O(V).

Hi,

This is Fatimah Abdullah from Educative. I noticed your feedback here and I’m glad you reached out to us.

In response to your feedback, the approach you have mentioned is excellent and will give an optimal solution in the current scenario. However, usually, when you will encounter such a challenge in a coding interview, you will not have the choice to access the size variable. Therefore, the algorithm that is mentioned in this solution is generic and is valid for most of the graph implementations. You might recall the challenge: “Challenge 4: Find the Length of a Linked List” where we assumed that we didn’t have the size variable either. The same intuition goes for this challenge as well. I hope this answers your question.

We hope Educative has inspired to further your learning, and please drop us a note if you have any other questions or concerns.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative Inc.

3 Likes