Beat 100% || Maximum Gap || Using Unordered_map ||  Optimizing the brute force solution N^2 --> N
Intuition\n Describe your first thoughts on how to solve this problem. \nwe need to find the Minimum (maximum gaps for all positions of an element).\n# Approach
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe need to find the Minimum (maximum gaps for all positions of an element).\n# Approach 1\n<!-- Describe your approach to solving the problem. -->\n\nStep 1: The maxi_gap function finds the maximum gap between occurrences of a specific value (val) in the nums array.\n\nStep 2: The minimumSeconds function initializes ans to n-1 and iterates through the array, using maxi_gap to find the maximum gap for each element.\n\nStep 3: It keeps track of the overall minimum gap (ans) among all elements in the array.\n\nStep 4: The minimumSeconds function returns the minimum gap divided by 2, accounting for double counting (two movements per second). This represents the minimum number of seconds needed to traverse the array efficiently, considering the gaps between occurrences of elements.\n# Complexity\n- Time complexity:O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\nint maxi_gap(vector<int>& nums, int n, int val){\n\nint max_gap = 0;\n    int st = 0;\n    int end = n-1;\n\n    while(st < end){\n       if(nums[st] == val && nums[end] == val){\n        max_gap = max(max_gap, n-(end-st-1)-2);\n        break;\n       }\n       else if(nums[st] == val && nums[end] != val){\n         end--;\n       }\n       else if(nums[st] != val && nums[end] == val){\n         st++; \n       }\n       else{\n        st++;\n        end--;\n       }\n    }\n    if(st >= end){\n        max_gap = n-1;\n        return (max_gap+1)/2;\n    }\n    \n    int curr;\n    int prev = st;\n    for(curr = st+1; curr<=end; curr++){\n        \n     if(nums[curr] == val){\n        max_gap = max(max_gap, curr-prev-1);\n        prev = curr;\n    }       \n    }\n    return (max_gap+1)/2;\n}\nint minimumSeconds(vector<int>& nums) {\n    \n    int n = nums.size();\n    if(n == 1){\n        return 0;\n    }\n    \n    int ans = n-1;\n    for(int i=0; i<n; i++){\n     ans = min(maxi_gap(nums, n, nums[i]), ans);\n    }\n    return ans;\n    }\n};\n```\n# Approach 2\n<!-- Describe your approach to solving the problem. -->\n\n1.Initializes an unordered map mapping to store information about each element\'s maximum distance between occurrences.\n2.The function traverses the array and updates the mapping with the maximum distance between occurrences of each element.\n3.Then, it calculates the maximum distance for each element using the formula n - (last occurrence index - first occurrence index + 1).\nThe function keeps track of the minimum distance ans while iterating through the mapping.\n4.Finally, it returns the result (ans + 1) / 2, accounting for the double count of seconds (two movements per second).\n# Complexity\n- Time complexity:O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\nint minimumSeconds(vector<int>& nums){\n    \n    int n = nums.size();\n    if(n == 1){\n        return 0;\n    }\n\n   unordered_map<int, vector<int>> mapping;\n    int ans = n-1;\n    for(int i=0; i<n; i++){\n    \n    if(mapping.find(nums[i]) != mapping.end()){\n      mapping[nums[i]][0] = max(mapping[nums[i]][0] , i-mapping[nums[i]][2]-1);  \n      mapping[nums[i]][2] = i;   \n    }\n    else{\n     mapping[nums[i]] = {0, i, i};\n    }\n    }\n    \n   for(auto & pairs : mapping){\n\n    //  cout<<pairs.first<<":"<<pairs.second[0]<<" "<<pairs.second[1]<<" "<<pairs.second[2]<<endl;  \n     pairs.second[0] = max(pairs.second[0], n-(pairs.second[2]-pairs.second[1]-1)-2); \n     ans = min(ans, pairs.second[0]);\n    }\n    return (ans+1)/2;\n    }\n};\n```\n
['Greedy', 'Ordered Map', 'C++']