Day 25.1.txt

697. 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 1:

Input: nums = [1,2,2,3,1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
Example 2:

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.
 

Constraints:

nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.



class Solution {
    public int findShortestSubArray(int[] n) {
        Map<Integer,Integer> nm=new HashMap<>();
        int i,j=0,k=0,s=Integer.MAX_VALUE;
        for(i=0;i<n.length;i++)
        {
            if(nm.containsKey(n[i]))
                nm.put(n[i],nm.get(n[i])+1);
            else
                nm.put(n[i],1);
        }
        ArrayList<Integer> kk=new ArrayList<>();
        for(int c : nm.keySet())
        {
            if(nm.get(c)>j)
            {
                kk.clear();
                kk.add(c);
                j=nm.get(c);
            }
            else if(nm.get(c)==j)
            {
                kk.add(c);
            }
        }
        for(int i1=0;i1<kk.size();i1++)
        {
            k=kk.get(i1);
            for(i=0;i<n.length;i++)
            {
                if(n[i]==k)
                    break;
            }
            for(j=n.length-1;j>i;j--)
            {
                if(n[j]==k)
                    break;
            }
            j++;
            if((j-i)<s)
                s=(j-i);
        }
        return s;
    }
}