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

Practice this problem on LeetCode: Click Here

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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala