Degree of an Array Problem & Solution

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

See the degree of an array problem on LeetCode.

C++ Solution

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int findShortestSubArray(vector<int>& nums) {
    int degree = 0;
    unordered_map<int, help> freq;
    for (int i = 0; i < nums.size(); ++i) {
      if (freq.find(nums[i]) == freq.end()) {
        freq[nums[i]] = {1, i, i};
      } else {
        ++freq[nums[i]].count;
        freq[nums[i]].high = i;
      }
      
      degree = max(degree, freq[nums[i]].count);
    }
    
    int argdegree = numeric_limits<int>::max();
    for (auto it = freq.begin(); it != freq.end(); ++it) {
      if (it->second.count == degree) {
        argdegree = min(argdegree, it->second.high - it->second.low + 1);
      }
    }

    return argdegree;
  }
  
private:
  struct help {
    int count;
    int low;
    int high;
  };
};

Are you looking for a job?