Degree of an Array

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.

Example:

Input: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_SIZE = 50001;
int findShortestSubArray(vector<int&nums)
{
    map<intint> mp;
    int max1 = -1;
    vector<intfirstIndex(MAX_SIZE, -1), lastIndex(MAX_SIZE, -1);

    for (int i = 0; i < nums.size(); i++)
    {
        mp[nums[i]]++;
        max1 = max(max1, mp[nums[i]]);
        if (firstIndex[nums[i]] == -1)
        {
            firstIndex[nums[i]] = i;
        }
        lastIndex[nums[i]] = i;
    }

    vector<int> maxFreq;
    for (int i = 0; i < nums.size(); i++)
    {
        if (mp[nums[i]] == max1)
        {
            maxFreq.push_back(nums[i]);
        }
    }
    int ans = INT_MAX;
    for (int i = 0; i < maxFreq.size(); i++)
    {
        int diff = lastIndex[maxFreq[i]] - firstIndex[maxFreq[i]] + 1;
        ans = min(ans, diff);
    }
    return ans;
}
int main()
{
    vector<int> nums = {1223142};

    cout << findShortestSubArray(nums);

    return 0;
}


No comments:

Post a Comment