O(n) with O(n) space. Single walk.


  • 0
    F
    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) {
            // val -> initial location, count
            if (nums.empty()) {
                return 0;
            }
            unordered_map<int, pair<int, int>> map;
            int maxC = 0;
            int maxL = 1;
            for (int i = 0; i < nums.size(); ++i) {
                auto ret = map.insert({nums[i], {i, 1}});
                if (!ret.second) {
                    ret.first->second.second++;
                    if (ret.first->second.second > maxC) {
                        maxC = ret.first->second.second;
                        maxL = i - ret.first->second.first + 1;
                    } else if (ret.first->second.second == maxC) {
                        maxL = min(maxL, i - ret.first->second.first + 1);
                    }
                }
            }
            return maxL;
        }
    };
    

Log in to reply
 

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