Improving the running time of Breadth First Search and Adjacency List creation
- by user45957
We are given an array of integers where all elements are between 0-9. have to start from the 1st position and reach end in minimum no of moves such that we can from an index i move 1 position back and forward i.e i-1 and i+1 and jump to any index having the same value as index i.
Time Limit : 1 second
Max input size : 100000
I have tried to solve this problem use a single source shortest path approach using Breadth First Search and though BFS itself is O(V+E) and runs in time the adjacency list creation takes O(n2) time and therefore overall complexity becomes O(n2). is there any way i can decrease the time complexity of adjacency list creation? or is there a better and more efficient way of solving the problem?
int main(){
vector<int> v;
string str;
vector<int> sets[10];
cin>>str;
int in;
for(int i=0;i<str.length();i++){
in=str[i]-'0';
v.push_back(in);
sets[in].push_back(i);
}
int n=v.size();
if(n==1){
cout<<"0\n";
return 0;
}
if(v[0]==v[n-1]){
cout<<"1\n";
return 0;
}
vector<int> adj[100001];
for(int i=0;i<10;i++){
for(int j=0;j<sets[i].size();j++){
if(sets[i][j]>0)
adj[sets[i][j]].push_back(sets[i][j]-1);
if(sets[i][j]<n-1)
adj[sets[i][j]].push_back(sets[i][j]+1);
for(int k=j+1;k<sets[i].size();k++){
if(abs(sets[i][j]-sets[i][k])!=1){
adj[sets[i][j]].push_back(sets[i][k]);
adj[sets[i][k]].push_back(sets[i][j]);
}
}
}
}
queue<int> q;
q.push(0);
int dist[100001];
bool visited[100001]={false};
dist[0]=0;
visited[0]=true;
int c=0;
while(!q.empty()){
int dq=q.front();
q.pop();
c++;
for(int i=0;i<adj[dq].size();i++){
if(visited[adj[dq][i]]==false){
dist[adj[dq][i]]=dist[dq]+1;
visited[adj[dq][i]]=true;
q.push(adj[dq][i]);
}
}
}
cout<<dist[n-1]<<"\n";
return 0;
}
