Key insight: there's no need to eagerly construct the adjacency list. In fact, there's no need to ever construct the adjacency list; you just need a way to find the next nodes. With this insight, we can construct an efficient version of the search.
Lazy edges
For any given node, finding indices i+1 and i-1 is trivial. Finding nodes that have the same value merely requires a lookup in the sets datastructure you've already created.
The rest of your breadth first search still applies equally; you mark off nodes you've already seen to make sure you don't revisit them.
Grouped values
Note that there's really no reason to return to a value once you've left it. Any path that reaches an X-valued index can reach any other X-valued index on the next step. That means your maximum path is 19 (each value can occur at most twice for a 20 nodes i.e. 19 edges along the path).
However, it it also means you don't want the following to occur:
- you're at index K with value X, and iterate over all other indices with value X, marking them as visited, and adding them to the queue
- you eventually reach each one of those X-valued indices in the queue, and iterate over everything it can reach, i.e. all those other X's - even though they've all been visited, and you already know you're not going to add them to the queue.
So you're doing quadratic work (each instance of a value iterates over each instance of the same value) and it's obviously pointless to boot. Once you process an X-valued index and thus visit all other X's, you know you'll never need to follow an X->X edge again. Easy fix? Just empty the list of indices by that value once you've processed one.
This new algorithm is linear time:
- reading the input is linear
- building
sets is linear (each index is inserted once)
- each index can be "processed" (added to the queue) at most once, so that's linear.
- each index can be "visited" (checking the visited array) at most three times: once by i-1, once by 1+1, and once by some other identically valued index.
If you really want, you can possibly shave off a bit of the constant factor here. After all, the final path will pass through each value once (and when it does, touching one or two indexes for that value). You can therefore construct a much, much smaller graph of how values can reach each other; solving that for the shortest paths is essentially free (at most 10 nodes, after all), and a shortest path through the indexes must be the shortest path through the values (proof left to reader, but note that any shortcut via i+1/i-1 costs at least a step, but can never win more than a step). Then, when you solve the bigger graph of indices, you don't need to bother taking any steps that conflict with what you already know of the solution; i.e. don't enqueue any indices that have a value other than your own or the "next" value along any shortest path in the value graph. (In essence, this optimization is A*).
Similarly, you could segment your queue by value and distance, and skip processing the rest of the current value with greater distance once you've found a way to the next.
Such trickery is almost certainly not worth it, but hey, it's possible :-).
Coding Style: I'd suggest naming your variables after what they represent. Your code is a little hard to follow because it contains things like sets (of what? why? - oh it's a way to lookup indices having a value), and a queue q (again, what's this mean? oh it's the reachable set in order of distance). Give meaningful concepts (that you repeat in the code) like adj[dq][i] a name. It's the neighbor you're going to visit. This algorithm is so simple, it's eventually clear, but there's no reason it shouldn't be clear right away.
TL;DR
- Don't precompute edges, instead compute reachability when needed.
- Empty the set of indices you use to compute value-to-value reachability after using it once to avoid quadratic behavior.
- The result is O(N).
Best Answer
It's possible because the "lists" in an adjacency list representation are not necessarily raw arrays.
In particular, adding a new node to a linked list is an O(1) operation, so if you make the adjacency list out of linked lists then adding a new node or edge is O(1).
As the chart you've linked points out, stacks and hash tables also have O(1) insertion so you could use them as well, but stacks would probably make many other operations highly inconvenient, and hash tables are only O(1) given some strong assumptions about the hashing function that are tricky to justify, so I usually assume adjacency lists are made out of linked lists if they want constant-time node/edge insertion.
It's also worth noting that even if you did use arrays, you would still have amortized constant-time complexity for node insertion, because the worst case of O(|v|) should be a rare occurrence. It's unclear whether the chart you linked is including any amortized complexities.