TLE with BFS solution C++: Please suggest optimization


  • 0
    P
    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;		
    	}
    };

  • 0
    T

    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 :)


Log in to reply
 

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