How to create adjacency list for this problem.

I am solving this question using bfs as propsed in editorial, but I am not getting how the adjacency list will be generated for this graph.

Link to the Editorial

The adjacency list that you will use will be as follows :

vector graph[n]; //This is basically an array of n cells, each cell having it’s data type as a vector.

You iterate a variable i from 1 to n. For every index i, you push_back Si+1, Si-1, and all those indexes j such that Si == Sj into graph[i].

This way, you get the all possible adjacent nodes to a node i, in the vector graph[i].

1 Like

If suppose I have 5 on the first index and also 5 on the 5th index then index 5 should be there in adjacency list of 1. Ho this situation will be taken care of.

1 Like

@arpit728 : I dont think you actually need to build the graph. Just store indexes of each digit . Refer this if you still don’t understand.


The solution link you mentioned, it is generating graph only?? right.


I got you n that for every index i push si-1 and si+1 into its adjacency list but to find si==sj I will have to iterate through all graph again and will increase the complexity.

@ankg has explained quite nicely but if you want to look at implementation for reference here’s the link