c++ | O(n) | with explanation
credits\nIdea\nfirstDayVisited[i] = The first day when room i was visited.\nSince nextVisit[i] is less than or equal to i , our answer is already stored in an i
[credits](https://leetcode.com/problems/first-day-where-you-have-been-in-all-the-rooms/discuss/1445156/C%2B%2B-DP)\n<b>Idea</b>\n`firstDayVisited[i]` = The first day when room `i` was visited.\nSince `nextVisit[i]` is less than or equal to `i` , our answer is already stored in an index smaller than `i` (which is already visited).\nLets say on day `d` I am at the room `i` for the first time. Assume `n` is the total number of rooms. Since I visited the room `i` for the first time, I visited it odd number of times and I must visit `nextVisit[i]` now. \nI claim that if `nextVisit[i]!=i` then **I am visiting `nextVisit[i]` odd number of time**. For the case when `nextVisit[i]==i` the value of `firstDayVisited[i+1]` is simply 2 and we\'ll see that the expression that we develop takes into account of this `nextVisit[i]==i` case also.\nThis claim is true because in order to move at a room having index greater than `i` , I must have visited it even number of times. Since my current room index `i` is greater than `nextVisit[i]` , I must have already visited `nextVisit[i]` even number of times and visiting it again. So, now I am visiting `nextVisit[i]` odd number of times. \nThe first day I visited the room `nextVisit[i]` is stored in `firstDayVisited[nextVisit[i]]`. The day on which I visited room `i` is `d`. We can utilize these 2 informations to know when will we revisit room `i` again. The day of revisiting is the difference+1 , that is, `d-firstDayVisited[nextVisit[i]]+1` . Now, I\'ll take 1 extra day to visit the room `i+1`.\nSo, the day on which room `i+1` is visited for the first time = `d-firstDayVisited[nextVisit[i]]+2`. Using this pattern, we can see that the last room will be covered on the last day. So, we return `firstDayVisited[n-1]`.\nFrom our definition of `firstDayVisited` , `d=firstDayVisited[i]`. For the case when `nextVisit[i]==i` , \n`d-firstDayVisited[nextVisit[i]]+2 = firstDayVisited[i]-firstDayVisited[nextVisit[i]]+2 =  firstDayVisited[i]-firstDayVisited[i]+2 = 2`\n\n<b>Note</b>\nDon\'t take modulo at each step and maximize it. This may give wrong answer as it may happen that the modulo of a smaller number is greater than the modulo of a greater number. But we have to return the modulo of the greatest day of first visit of room `n-1` modulo 1e9+7\n\nDo comment in case of any confusion.\n\n```\n\n#define mod 1000000007\n\nclass Solution {\npublic:\nint firstDayBeenInAllRooms(vector<int>& nextVisit){\n    int n=nextVisit.size(),ans=0;\n    vector<int> firstDayVisited(n,0);\n    for(int i=0;i<n-1;i++) firstDayVisited[i+1]=(((firstDayVisited[i]-firstDayVisited[nextVisit[i]]+mod)%mod+2)%mod+firstDayVisited[i])%mod;\n    return firstDayVisited.back();\n}\n};\n```\n\n<b>100% faster code</b>\n```\n#define mod 1000000007\n\nclass Solution {\npublic:\nint firstDayBeenInAllRooms(vector<int>& nextVisit){\n    int n=nextVisit.size(),ans=0;\n    int *firstDayVisited=new int[n]();\n    for(int i=0;i<n-1;i++) firstDayVisited[i+1]=(((firstDayVisited[i]-firstDayVisited[nextVisit[i]]+mod)%mod+2)%mod+firstDayVisited[i])%mod;\n    return firstDayVisited[n-1];\n}\n};\n```
[]