Optimized approach: The right pointer traverses the whole list, or k nodes. And then the left pointer traverses the first k - n - 1 nodes. So the total nodes traversed is 2k - n - 1.
Naive approach: The first pass traverses k nodes, and the second traverses k - n - 1 nodes, so the total nodes traversed is 2k - n - 1.
Is the optimized approach better?
Hi @Isaac_Haseley!
Thanks for reaching us for your query.
In both given solutions, we traversed a total of 2k-n-1 nodes, but there is a difference in both approaches.
In the naive approach, we use a loop to count the number of nodes in the list and use another loop to find the node to be removed. In this approach, we are using two loops and traversing the list twice using a single pointer.
Meanwhile, in the optimized approach, we are using two pointers with a distance of n nodes and moving both in the single loop. Once the right pointer reaches the end of the list, the left pointer indicates the node before the nth node, and we can easily remove that node. In this approach, we traverse the list once using two pointers in one loop.
Time complexity is the reason to consider an approach to be better. In both approaches, the time complexity is linear, but the naive approach uses two loops, while the optimized approach uses one loop, and we can say the optimized approach is better.
I hope you get the difference. If you have any queries, do let us know. Thanks!
Thanks Rauf! Does time complexity care about the number of loops, or just about the total number of operations from start to finish?
In this particular case, the time complexity remains the same for both approaches, but an extra loop increases the number of operations. In the case of a loop, the loop itself has some operations to perform, e.g., initialization (one time), condition check (in each iteration), and increment/decrement (in each iteration). An extra loop definitely increases the number of operations. In the naive approach, we are using a loop to find the number of nodes that perform n operations of traversing the LinkedList. In this case, this loop performs the following operations:
In the second loop of the naive approach, we are iterating the list to k nodes (assuming the nth last node is k) and updating the next address of the kth node. The operations of the second loop are as follows:
Total operations for the naive approach are: 3n+1+3k+2 = 3n+3k+3
In the case of the optimized approach, we are using a single loop, updating 2 pointers and updating the next address. The operations of these loops are as follows:
Total operations for the optimized approach are: 3n+k+2
If we compare the number of operations, we can see the difference of 2k+1 operations. Although time complexity in terms of big-O will be the same for both approaches, but the number of operations will be less in the optimized approach. I hope you understand how a loop impacts the number of operations. If you’ve any other queries, do let us know. Thanks!
