🔥 Tricky Math Greedy HashMap question fully explained 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is a tricky hashmap+greedy+math question. You need to find the max number of eleme
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is a tricky hashmap+greedy+math question. You need to find the max number of elements between two consecutive occurrences of a val.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nYou need to create a map that stores each unique val and the index positions it occurs at inorder to find the max number of elements between each occurrence. With each number of elements between two occurrences of val you need to divide by two since you can turn two into current val(but you need to add 1 when dividing by two to account for odd number of elems).\n\nYou also need to account for the circular edge case which you get by adding the number of elements from the start to the first occurrence of val and the last occurrence of val to the end of the array nums. This will give you the number of elements between the first and last occurrence of val from a circular angle. You can then compare this as well to find the max number of elements for val which you compare with a global ans\n\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 {\n    public int minimumSeconds(List<Integer> nums) {\n        //we create a hashmap to store index position of each value of nums\n\n        Map<Integer, List<Integer>> store = new HashMap<>();\n\n        //we initialize each value with its list of indices\n        for(int i=0;i<nums.size();i++){\n            if(!store.containsKey(nums.get(i))) store.put(nums.get(i), new ArrayList<>());\n\n            //we add this index to its corresponding value key\n            store.get(nums.get(i)).add(i);\n        }\n\n        int ans=Integer.MAX_VALUE;\n\n        //we now iterate through and get the number of elements on the edges and the number of elements between consecutive indices for each val\n        for(int val: store.keySet()){\n            List<Integer> pos = store.get(val);\n            int n = nums.size();\n\n            //we then get the number of elements from start to the first occurrence of val\n            int startelems = pos.get(0);\n            //we then get the number of elements from the last occurrence of val to the end of the array\n            int endelems=n-1 - pos.get(pos.size()-1);\n            //Edge case is the dist/number of elements between the first and last occurrence of val from the edges circularly\n            //we then sum these up divided by 2 but we add 1 for the case there is an odd number\n            int edgecase=(startelems+endelems+1)/2;//+1 will sort odd case\n\n            //we then get the max number of elements between consecutive positions from first to last occurence of val\n            int normalcase = 0;\n            for(int i=1;i<pos.size();i++){\n                int numelems = pos.get(i)-pos.get(i-1);//we dont add 1 here since its 0 based index so it will always cancel the 1\n                numelems/=2;//we divide by two without adding 1 because it will\n                //we count the number of times needed considering odd case\n                normalcase=Math.max(numelems,normalcase);\n            }\n            //we now have our normalcase and our edgecase, we choose the max for our ans\n            int res=Math.max(normalcase,edgecase);\n            ans=Math.min(res,ans);\n        }\n\n        return ans;\n        \n    }\n    \n}\n```
['Hash Table', 'Math', 'Greedy', 'Java']