### LeetCode - Degree of an Array Java - The Coding Shala

Home >> LeetCode >> degree of an array

# LeetCode - Degree of an Array

In this post, you will learn how to find the Degree of an Array. Here we will implement LeetCode's Degree of an array solution in Java.

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: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice. 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

## Degree of an Array Java Solution

Approach 1:
To solve this problem in need to count occurrences of each element in the array and then the distance between the left index and right index of max occurred number. if the count of two elements is the same then we need to return minimum distance. We can solve this using HashMap.

Time Complexity: O(N)
Space Complexity: O(N), space used by HashMap.

Java Program:
```class Solution {
public int findShortestSubArray(int[] nums) {
HashMap<Integer, Integer> count = new HashMap<>();
HashMap<Integer, Integer> left = new HashMap<>();
HashMap<Integer, Integer> right = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(count.containsKey(nums[i])){
count.put(nums[i], count.get(nums[i])+1);
}else{
count.put(nums[i],1);
}
}
for(int i=nums.length-1;i>=0;i--){
left.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
right.put(nums[i],i);
}
int ans = nums.length;
int curr_count = 0;
for(int i=0;i<nums.length;i++){
int n = nums[i];
if(count.get(n)>=curr_count){
int dis = (right.get(n)-left.get(n))+1;
if(count.get(n)>curr_count) ans = dis;
else
if(dis<ans) ans = dis;
curr_count = count.get(n);
}
}
return ans;
}
}
```

Other Posts You May Like