Leetcode 697 Solution

This article provides solution to leetcode question 697 (degree-of-an-array)
Categories:
Tags:
Access this page by simply typing in "lcs 697" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/degree-of-an-array

Solution

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int max_degree = 0;
        int min_len = 10000000;



        map<int, int> degrees;
        map<int, int> start;
        map<int, int> end;



        for (int i = 0; i < nums.size(); i++)
        {
            int num = nums[i];



            degrees[num] += 1;



            if (start.find(num) == start.end())
                start[num] = i;
            end[num] = i;



            max_degree = max(max_degree, degrees[num]);
        }



        for (auto it = degrees.begin(); it != degrees.end(); it++)
        {
            int num = it->first;
            int degree = it->second;



            if (degree == max_degree)
                min_len = min(min_len, end[num] - start[num] + 1);
        }



        return min_len;
    }
};