[JAVA] [BFS] [Detailed Analysis] O(n) BFS Solution
Let\'s first understand the normal bfs approach in this problem. One might simply use a queue and add all the indexes which they can visit from current index (i
Let\'s first understand the normal bfs approach in this problem. One might simply use a queue and add all the indexes which they can visit from current index (i.e all index in `[curr_idx + minJump, curr_idx + maxJump]`). And if one reaches the end index then return true. Simple! \n\nBut now we can see that there are overlapping indexes which needs to be removed. So what one can do is simply use `visited` array/set to track the processed indexes and if it comes in next traversal it can be ignored. \n\nApproach (using visited array/set ) **[Will Give TLE]**\n\n```\n    public boolean canReach(String s, int minJump, int maxJump) {\n        if(s.charAt(s.length() - 1) != \'0\')\n            return false;\n        \n        Queue<Integer> queue = new LinkedList<>();\n        boolean[] visited = new boolean[s.length()];\n        queue.add(0);\n        \n        while(!queue.isEmpty()){\n            int idx = queue.remove();\n            if(idx == s.length() - 1)\n                return true;\n            for(int i = idx + minJump; i <= idx + maxJump && i < s.length(); i++){\n                if(!visited[i] && s.charAt(i) == \'0\'){\n                    visited[i] = true;\n                    queue.add(i);\n                }   \n            }\n        }\n        \n        return false;\n    }\n```\n\nLet\'s now analyze why exactly we are facing TLE. Even though we are using set then also we are processing the already processed indexes. (How? Actually processing is happening in the inner loop, and in this solution also we are checking if the index is visited or not in the loop only so in worst case it will hit `O(N^2)`.\n\nSo how to avoid already processed indexes? What we can do is simply start our processing from the index till which we have already processed. For this we will keep track of **the maximum index till we have processed** and update it accordingly.\n\n**Optimized Solution** [Time Complexity - O(N)]\n\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        if(s.charAt(s.length() - 1) != \'0\')\n            return false;\n        \n        Queue<Integer> queue = new LinkedList<>();\n        queue.add(0);\n        \n        // This variable tells us till which index we have processed\n        int maxReach = 0;\n        \n        while(!queue.isEmpty()){\n            int idx = queue.remove();\n            // If we reached the last index\n            if(idx == s.length() - 1)\n                return true;\n            \n            // start the loop from max of [current maximum (idx + minJump), maximum processed index (maxReach)]\n            for(int j = Math.max(idx + minJump, maxReach); j <= Math.min(idx + maxJump, s.length() - 1); j++){\n                if(s.charAt(j) == \'0\')\n                    queue.add(j);\n            }\n            \n            // since we have processed till idx + maxJump so update maxReach to next index\n            maxReach = Math.min(idx + maxJump + 1, s.length() - 1);\n        }\n        \n        return false;\n    }\n}\n```\n\nI hope this helps!\n\n\n
['Breadth-First Search', 'Queue', 'Java']