✅C++ || Easy || BFS || TC=O(n) && SC=O(n)
Intuition\nThink about bfs but it\'s not enough think more about how you can optimize range, Lets say start and end range.\n\n# Approach\n->it uses a BFS approa
# Intuition\nThink about bfs but it\'s not enough think more about how you can optimize range, Lets say start and end range.\n\n# Approach\n->it uses a BFS approach, starting from index 0. \n->It maintains a queue of indices to explore and a max_reach variable to optimize search range. \n->It iterates through the queue, considering valid jumps within the given range. If a path reaches the last index (\'1\'), it returns true. The max_reach helps avoid redundant iterations. \n->The algorithm continues until all possible paths are explored or no valid path is found, returning false if the last index is not reachable.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump ) {\n        int n=s.size();\n        if(s[n-1]==\'1\')\n        return false;\n        queue<int>q; vector<int>vis(n,0);\n        q.push(0);\n        vis[0]=1;\n        int max_reach=0;\n    \n        while(!q.empty()){\n            int x=q.front();\n            q.pop(); \n            int start=max(x+minJump,max_reach+1);\n            int end=min(x+maxJump,n-1);\n\n            for(int i=start ;i<=end;i++){\n                if(i==n-1 && s[i]==\'0\')\n                return true;\n                \n                if(s[i]==\'0\' && vis[i]==0)\n                {\n                  vis[i]=1;\n                  q.push(i);\n                }\n            }\n            max_reach=max(max_reach,x+maxJump);\n        }\n        return false;\n    }\n};\n```
['Breadth-First Search', 'Sliding Window', 'C++']