SDE - 1

I started with a basic brute force approach by counting the number of 0’s,1’s,2’s. Let the count be x,y,z then we can traverse again and fill x nodes as 0 , y nodes as 1 and z nodes as 2.
Then the interviewer asked me to optimize the solution
Next comes the efficient solution
Iterate through the linked list. Maintain 3 pointers named zero, one, and two to point to current ending nodes ...

First solution using extra space:
1) We can make a set of integer.
2) Traverse the linked list and store the values in set.
3) After traversal the set will contain all those elements which are unique.
4) We can then copy those elements back to the linked list.

The interviewer asked me to optimize and asked me the complexity.

So second optimised solution:
1) Traver...

Initially all vertex are unvisited so visited[i] will be false for all i and as no path is yet constructed so distance[i] will be infinity or you can take any value like -1 and set predecessor[i] as -1 for all i.

Now the first vertex to be visited is sourse and distace of Source to source is 0 hence visited[source] = true
distance[source]=0.
queue.push(source).

while there a...