C++ solution containing all approaches from brute force to optimized || Time-O(n) Space- O(1)
Hey There, In this I would discuss two solutions along with explanation.\n### Please do upvote it if you like it and let me know in the comments if there are an
Hey There, In this I would discuss two solutions along with explanation.\n### Please do upvote it if you like it and let me know in the comments if there are any questions/mistakes etc.\n\n# Approach1(Naive Approach):\n\n### Algorithm:\n- Go to each round, start with the prev round and go till the next one.\n- To do this we would maintain a frequency array to count the frequency of each.\n- Then calculate the highest freq one, and then push them\n\n#### Code:\n```\nclass Solution {\n    void increase_with_modulo(int &n,int size){\n\t// Reason we are performing size++ is if it is 1 based, So we want 7 to say, If we don\'t do this 7 would become 0\n        size++;\n        n = (n+1)%size;\n        if(n==0)\n            n++;\n    }\npublic:\n    vector<int> mostVisited(int n, vector<int>& rounds) {\n        vector<int> ans;\n        vector<int> visited(n+1,0);\n        visited[rounds[0]]++;\n        \n        int i;\n        for(i=1;i<rounds.size();i++){\n            int prev_round = rounds[i-1];\n            int curr_round = rounds[i];\n            \n\t\t\t// Start with the current round and go with the circular fashion to the next round.\n            increase_with_modulo(prev_round, n);\n            while(prev_round != curr_round){\n                visited[prev_round]++;\n                increase_with_modulo(prev_round, n);\n            }\n\t\t\t// Since the condition is till curr_round, Curr_round was not taken into account.\n            visited[curr_round]++;\n        }\n        \n\t\t// Calculating frequency\n        int maxFreq = 0;\n        for(i=1;i<=n;i++)\n            maxFreq = max(maxFreq, visited[i]);\n        \n\t\t// Pushing those with the highest frequency\n        for(i=1;i<=n;i++)\n            if(maxFreq == visited[i])\n                ans.push_back(i);\n        return ans;\n        }\n};\n```\n**Time complexity:**  O(n*size), Reason is in the worst test case, We would be starting from x and going till x-1 in the circular fashion, which would take O(n) time, and we need to perform size such operations where size is the size of the array. \n**Space complexity:** O(n), Since we are maintaining a freq array.\n\n\n# Approach2(Optimized using observation):\n\n#### Observation:\nA small observation is that those with the highest frequency are those who will be visited in the last round.\nNow there are two test cases\n**Case1:**\nOne is start <= end, In that case all the nodes from start till end are part of our answer.\n**Case2:**\nstart>end. In this case to maintain our answer in the descending order, we will first push from 1 to end then start to n, Since we need to go circularly.\n\n#### Code:\n```\n   vector<int> mostVisited(int n, vector<int>& rounds) {\n        int i,start,end,size=rounds.size();\n        start = rounds[0];\n        end = rounds[size-1];\n        \n        vector<int> most_visited;\n        if(start<=end){\n\t\t// Going from start to end, Since we just want a forward traversal.\n            for(i=start;i<=end;i++)\n                most_visited.push_back(i);\n        }\n        else{\n\t\t// We need to go circularly.\n            for(i=1;i<=end;i++)\n                most_visited.push_back(i);\n            for(i=start;i<=n;i++)\n                most_visited.push_back(i);\n        }\n        return most_visited;\n    }\n```\n**Time complexity:** O(n), Since in worst case, We would perform a single traversal from 1 to n.\n**Space complexity:** O(1) Since no extra space is consumed.
['C', 'C++']