Degree of an Array

EASY

Description

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.

Approaches

Checkout 2 different approaches to solve Degree of an Array. Click on different approaches to view the approach and algorithm in detail.

Two-Pass Approach with Hash Maps

This approach involves two separate traversals. The first pass gathers information about each number: its frequency, and the indices of its first and last occurrences. The second pass uses this information to determine the degree of the array and then finds the shortest subarray length among all elements that have this degree.

Algorithm

Initialize three HashMaps: count to store frequencies, first to store the first index, and last to store the last index of each number.
Iterate through the input array nums from left to right with index i.
For each element num = nums[i], update its information in the three maps: increment its frequency in count, record its first occurrence index in first if it's not already present, and always update its last occurrence index in last.
After the first pass, calculate the degree of the array by finding the maximum frequency in the count map.
Initialize minLength to nums.length.
Iterate through the unique numbers (the keys of the count map).
If a number's frequency equals the degree, calculate the length of its span: len = last.get(num) - first.get(num) + 1.
Update minLength = Math.min(minLength, len).
Finally, return minLength.

The core idea is that the shortest subarray with the same degree as the original array must span from the first to the last occurrence of an element that has the maximum frequency. The length of this subarray is last_index - first_index + 1. We can find the minimum of these lengths over all elements that have the maximum frequency (the degree).

Step 1: Information Gathering (First Pass) We iterate through nums once to populate three HashMaps:

count: Stores the frequency of each number.
first: Stores the index of the first occurrence of each number.
last: Stores the index of the last occurrence of each number.

Map<Integer, Integer> count = new HashMap<>();
Map<Integer, Integer> first = new HashMap<>();
Map<Integer, Integer> last = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    count.put(num, count.getOrDefault(num, 0) + 1);
    if (!first.containsKey(num)) {
        first.put(num, i);
    }
    last.put(num, i);
}

Step 2: Finding the Shortest Subarray (Second Pass) After populating the maps, we first determine the degree of the array by finding the maximum frequency in the count map. Then, we iterate through the elements that have this degree and calculate the length of their corresponding subarrays. We keep track of the minimum length found.

int degree = 0;
for (int freq : count.values()) {
    degree = Math.max(degree, freq);
}

int minLength = nums.length;
for (int num : count.keySet()) {
    if (count.get(num) == degree) {
        minLength = Math.min(minLength, last.get(num) - first.get(num) + 1);
    }
}

return minLength;

Complexity Analysis

Time Complexity: O(N), where N is the number of elements in the array. The first pass takes O(N) to populate the maps. The second pass involves finding the degree (O(U), where U is the number of unique elements) and then iterating through the unique elements again (O(U)). Since U <= N, the total time complexity is O(N).Space Complexity: O(U), where U is the number of unique elements in the array. In the worst case, all elements are unique, so the space complexity is O(N). This space is used to store the three hash maps.

Pros and Cons

Pros:

Conceptually simple and easy to follow the logic.
Correctly solves the problem within the given constraints.

Cons:

Requires two passes over the data (one over the array, one over the map keys), which is less efficient than a single-pass solution.
Uses more memory due to three separate hash maps, although the asymptotic complexity is the same as other map-based approaches.

Code Solutions

Checking out 3 solutions in different languages for Degree of an Array. Click on different languages to view the code.

class Solution { public int findShortestSubArray ( int [] nums ) { Map < Integer , Integer > cnt = new HashMap <>(); Map < Integer , Integer > left = new HashMap <>(); Map < Integer , Integer > right = new HashMap <>(); int degree = 0 ; for ( int i = 0 ; i < nums . length ; ++ i ) { int v = nums [ i ]; cnt . put ( v , cnt . getOrDefault ( v , 0 ) + 1 ); degree = Math . max ( degree , cnt . get ( v )); if (! left . containsKey ( v )) { left . put ( v , i ); } right . put ( v , i ); } int ans = 1000000 ; for ( int v : nums ) { if ( cnt . get ( v ) == degree ) { int t = right . get ( v ) - left . get ( v ) + 1 ; if ( ans > t ) { ans = t ; } } } return ans ; } }

Video Solution

Watch the video walkthrough for Degree of an Array

Data Structures:

ArrayHash Table

Companies:

ByteDance |Expedia |IBM |J.P. Morgan |