Short C++ using one hash map and a simple object, 36ms


  • 0
    M
        int findShortestSubArray(vector<int> nums) {
            auto N = static_cast<int>(nums.size());
    
            // Tracks occurence count and [lo,hi] indices
            struct range {
                int cnt = 0;
                int lo = 50000 + 1;  // lowest index
                int hi = 0;          // highest index
    
                int size() const { return hi - lo + 1; }
    
                // Increment count and update indices; return updated count
                int update(int index) {
                    cnt++;
                    lo = min(index, lo);
                    hi = max(index, hi);
                    return cnt;
                }
            };
    
            int freq = 0;
            unordered_map<int, range> ranges;
    
            // Find ranges for all numbers and the max frequency
            for (int i = 0; i < N; ++i)
                freq = max(freq, ranges[nums[i]].update(i));
    
            // Find a range with min size that matches the max frequency
            int size = N;
            for (auto item : ranges)
                if (item.second.cnt == freq)
                    size = min(size, item.second.size());
    
            return size;
        }
    

Log in to reply
 

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