Clean O(N) solution with hashmaps for frequency, first/last positions


  • 0
        int findShortestSubArray(vector<int>& nums) 
        {
            int degree = 0; // degree of entire array
            unordered_map<int, int> fre, first, last; // fequency, first position, last position
            for (int i = 0; i < nums.size(); ++i) {
                degree = max(degree, ++fre[nums[i]]);
                if (!first.count(nums[i])) first[nums[i]] = i;
                last[nums[i]] = i;
            }
            
            // get min length for those with frequency == degree
            int minLen = INT_MAX;
            for (auto& p : fre)
                if (p.second == degree)
                    minLen = min(minLen, last[p.first] - first[p.first] + 1);
            return minLen;            
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.