Brute Force | Optimal | Detailed Explanation
Question :\n\ncpp\nYou are given a 0-indexed array nums containing n integers.\n\nAt each second, you perform the following operation on the array:\n\nFor every
### Question :\n\n```cpp\nYou are given a 0-indexed array nums containing n integers.\n\nAt each second, you perform the following operation on the array:\n\nFor every index i in the range [0, n - 1], replace nums[i] with either\nnums[i], nums[(i - 1 + n) % n], or nums[(i + 1) % n].\nNote that all the elements get replaced simultaneously.\n\nReturn the minimum number of seconds needed to make all elements in the array nums equal.\n```\n\n### Brute Force :\n\n1. So according to question in 1 second we change the value at the index let\u2019s say `nums[i]` to  either `nums[i], nums[(i - 1 + n) % n]`, or `nums[(i + 1) % n]`.\n2. That mean we can change the current value to either previous or next value. i.e Neighbouring values. \n3. To have the minimum time, we can think greedily to choose the element with maxFreq, so maximum conversions can be made in less time. \n\n### **So now how do we now time Taken to convert all the elements to given element x ?**\n\n1. We can use the multiSource BFs here, think all the locations of `x` as source node and rest all the neighbouring nodes.\n2. Start from the source nodes, the first time we met the neighbouring node, that is the minimum Time taken to convert the vlaue to `x`\n\n### **Failure of Greedy :**\n\n1. We know the time taken to convert all the elmenets in array to given value `x`.\n2. The greedy approach of taking x as the maxFrequency element Fails. \n\n```cpp\nExample : \nConsider the arr = [2,2,3,9,3] \nThere are 2 elements of maxFrequency i.e 2,3. \nAmong them which to choose, contrdication occurs here. \nSuppose let\'s take 2 as x.\nIn 1 second array becomes [2,2,2,9,2]\nIn 2 second array becomes [2,2,2,2,2] \nHence we required 2 secconds if we consider x as 2. \n\nSuppose lets take 3 as x.\nIn 1 second array becomes [3,3,3,3,3]\nSo only 1 second is required to equalize the array. \n\nSo the Greedy Fails here.\n```\n\n1. So we are not sure about the optimal value of `x,` so we can try every unique value in the array and find out the time required to equalize the array and take the minimum among them. \n\n```cpp\nint findMinimumTimeRequired(vector<int>& nums,int num)\n   {  \n        int n = nums.size();\n        queue<int> q;\n        vector<int> visited(n,0);\n        for(int i = 0; i<n; ++i)\n        {\n            if(nums[i] == num)\n            {\n                q.push(i);\n                visited[i] = 1;\n            }\n        }\n        int seconds;\n        for(seconds = 0; !q.empty(); ++seconds)\n        {\n            for(int i = q.size(); i > 0; --i)\n            {\n                int ind = q.front();\n                q.pop();\n                int backInd = (ind-1+n)%n,frontInd = (ind+1)%n;\n                if(visited[backInd] == 0)\n                {\n                    q.push(backInd);\n                    visited[backInd] = 1;\n                } \n                if(visited[frontInd] == 0)\n                {\n                    q.push(frontInd);\n                    visited[frontInd] = 1;\n                }\n            }\n        }\n        return seconds-1;\n   }\n   int bruteForce(vector<int>& nums)\n   {\n        unordered_set<int> set;\n        for(auto num : nums) set.insert(num);\n        int ans = INT_MAX;\n        for(auto val : set)\n           ans = min(ans,findMinimumTimeRequired(nums,val));\n        return ans;\n   }\n```\n\n**Time Complexity :** O(N*N) \n\n`findMinimumTimeRequired` Functions takes O(N) time, we are searching for each unique value in array, at most there can be N unique values. \n\nSo Time Complexity is O(N*N) \n\n**Space Complexity :** O(N) \n\nO(N) space is required for the map and the queue.\n\n### Optimal approach :\n\n**Intuition:**\n\nAssume the final values of the modified array\xA0`nums`\xA0are all\xA0`x`s, then\xA0`x`\xA0must be among the original input array.\n\nSuppose\xA0`i < j`,\xA0`nums[i] == nums[j] == x`\xA0and\xA0`nums[k] != x`for all\xA0`k`\xA0such that\xA0`i < k < j`. we can derive following conclusion:\n\n**Since each second we can only change the neighbors of\xA0`x`s, we can at most change 2 numbers among those between 2\xA0`x`s each second. Therefore, at least\xA0`(j - i) / 2`seconds needed to change to\xA0`x`\xA0all numbers between\xA0`i`\xA0and\xA0`j`.**\n\nSo for given x, if we find out the maximum Time to convert among all the segments we will get the time required to equalize the array with given value x. \n\nAnswer would be minimum among all such values. \n\n### **How to Take care of the Circularity  ?**\n\n1. let\u2019s say `first` and `last` are the first and last locations of x in the array. We have taken care of all the segments which are between the consecutive locations of x.\n2. But we didn\u2019t consider the segments arr[0,first-1] and arr[last+1,n].\n3. Inorder to include these segment as whole, append the `first + n` to the locations vectors of x. \n4. Then these segment is also considered. \n\nCode : \n\n```cpp\nint usingHashTable(vector<int> &nums)\n   {   \n       int n = nums.size();\n       /*map to store the indexes of occurence of x*/\n       unordered_map<int,vector<int>> map;\n       for(int i = 0; i<n; ++i)\n          map[nums[i]].push_back(i);\n       int minTime = INT_MAX;\n       for(auto &[num,pos] : map)\n       {   \n           /*pushing the pos[0] + n to take care of circularity*/\n           pos.push_back(pos[0] + n);\n           int maxTime = INT_MIN;\n           /*finding the maximumTime required for conversion among all the segments*/\n           for(int i = 1; i < pos.size(); ++i)\n              maxTime = max(maxTime, (pos[i] - pos[i-1])/2);\n           /*Take minimum among all valid x*/\n           minTime = min(minTime,maxTime);\n       }\n       return minTime;\n   }\n```\n\nTime Complexity : O(N)\n\nSpace Complexity : O(N)\n### Please upvote If you like it.
['Hash Table', 'Breadth-First Search', 'C++']