Number of subarrays with same 'degree' as the array

user_6069756 0
Viewed 1742

So this problem was asked in a quiz and the problem goes like:

You are given an array 'a' with elements ranging from 1-106 and the size of array could be maximum 105 Now we are asked to find the number of subarrays with the same 'degree' as the original array. Degree of an array is defined as the frequency of maximum occurring element in the array. Multiple elements could have the same frequency.

I was stuck in this problem for like an hour but couldn't think of any solution. How do I solve it?

Sample Input:

first-input
1,2,2,3,1
first-output 2
second-input
1,1,2,1,2,2
second-output 4
arrays algorithm
2 Answers

Taking reference from leet code https://leetcode.com/problems/degree-of-an-array/solution/ solve

    class Solution {
        public int findShortestSubArray(int[] nums) {
            Map<Integer, Integer> left = new HashMap(),
                right = new HashMap(), count = new HashMap();

            for (int i = 0; i < nums.length; i++) {
                int x = nums[i];
                if (left.get(x) == null) left.put(x, i);
                right.put(x, i);
                count.put(x, count.getOrDefault(x, 0) + 1);
            }

            int ans = nums.length;
            int degree = Collections.max(count.values());
            for (int x: count.keySet()) {
                if (count.get(x) == degree) {
                    ans = Math.min(ans, right.get(x) - left.get(x) + 1);
                }
            }
            return ans;
        }

}
user_74688160
Related