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:[1, 2, 2, 3, 1]Output:2Explanation: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:[1,2,2,3,1,4,2]Output:6

**Note:**

`nums.length`

will be between 1 and 50,000.`nums[i]`

will be an integer between 0 and 49,999.

Idea: use a hash map to store number elements as key and indices as value, then the length of the value is frequency of a specific number element, and difference between first and last indices in the value is the potential minimum length of the sub-array which has the degree as the input array.

Code:

def findShortestSubArray1(self, nums): """ :type nums: List[int] :rtype: int https://leetcode.com/problems/degree-of-an-array/discuss/108647/Python-O(n)-concise-with-explanation-(two-approaches) Firstly, group each num and collect the index it appears into a list. The list with the longest length will be the degree of the array. Next loop through each of the lists, only those lists with the same length as the degree will qualify. We simply take difference between the first and last value of each qualifying lists to find the length of such a possible subarray. For example if we have [1, 1, 2, 2, 2, 3, 1], after grouping by value: [1, 1, 2, 2, 2, 3, 1] => { 1: [0, 1, 6], 2: [2, 3, 4], 3: [4] }, degree: 3 Only have to consider values where the length == degree: 1: [0, 1, 6] => subarray length: (6 - 0) + 1 = 7 2: [2, 3, 4] => subarray length: (4 - 2) + 1 = 3 (Winner!) beats 27.26% """ nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf') for index, num in enumerate(nums): nums_map[num].append(index) deg = max(deg, len(nums_map[num])) for num, indices in nums_map.items(): if len(indices) == deg: min_len = min(min_len, indices[-1] - indices[0] + 1) return min_len def findShortestSubArray2(self, nums): """ :type nums: List[int] :rtype: int nums_map: k as num, v as indices of num in the array deg: degree of array (maximum frequency of any one of its elements) min_len: minimum length to hold the continuous sub-array which has the degree difference between first and last indices of an element is the degree and potential min length for the num beats 52.72% """ nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf') for index, num in enumerate(nums): nums_map[num].append(index) if len(nums_map[num]) == deg: min_len = min(min_len, nums_map[num][-1] - nums_map[num][0] + 1) elif len(nums_map[num]) > deg: deg = len(nums_map[num]) min_len = nums_map[num][-1] - nums_map[num][0] + 1 return min_len

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Learning Reactive Programming With Java 8

Thinking in Java (4th Edition)

Java Artificial Intelligence: Made Easy, w/ Java Programming