# TLE with BFS solution C++: Please suggest optimization

• ``````class Solution {
public:
int jump(vector<int>& nums) {
if(!nums.size())
return 0;
if(nums.size() == 1 && nums[0] == 0)
return 0;
queue<int>BFSqueue;
vector<bool> visited(nums.size(), false);
vector<int>distance(nums.size(), INT_MAX);
BFSqueue.push(0);
visited[0] = true;
distance[0] = 0;
while(!BFSqueue.empty()) {
int currentVertex = BFSqueue.front();
BFSqueue.pop();
for(int i = 1;i<=nums[currentVertex];i++) {
if(!visited[i+currentVertex]) {
visited[i+currentVertex] = true;
distance[i+currentVertex] = 1 + distance[currentVertex];
if(currentVertex+i>=nums.size()-1)
return distance[nums.size()-1] == INT_MAX ? -1 : distance[nums.size()-1];
BFSqueue.push(i+currentVertex);
}
}
}
return -1;
}
};``````

• My suggestion is to write your for loop Like this(notice the first line):

``````for(int i = nums[currentVertex]; i>=0; i--) {
if(!visited[i+currentVertex]) {
visited[i+currentVertex] = true;
distance[i+currentVertex] = 1 + distance[currentVertex];
if(currentVertex+i>=nums.size()-1)
return distance[nums.size()-1] == INT_MAX ? -1 : distance[nums.size()-1];
BFSqueue.push(i+currentVertex);
}
}
``````

Namely search the distance from back to front and it will save sometime. This is only my suggestion that may be not helpful to you. You can have a try :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.