697. Degree of an Array

EasyArrayHash Table
Leetcode Link

Problem Description

Given an array of non-negative integers nums, the task is to find the smallest length of a contiguous subarray that has the same degree as the entire array. The degree is defined as the maximum frequency of any one element in the array. For instance, if the number 2 appears five times in the array and no other number appears as frequently, then the degree of the array is 5. By finding a subarray with this degree, we're essentially looking for the shortest segment of the array where the most frequent element in the entire array appears its maximum number of times.

Intuition

The core idea behind the solution is to track the positions (indices) of each element in the array while also counting the occurrence (frequency) of each element. Since we need the subarray with the degree of the original array, we focus on elements that match the highest frequency.

Here's a step-by-step explanation of the thought process:

  1. First, count the occurrences of each element in the array using a Counter object. This will help us establish the degree of the array, which is the highest frequency of any element.

  2. Determine the degree by looking at the frequency of the most common element in the Counter.

  3. Two dictionaries, left and right, are used to store the first and last occurrences (indices) of each element in the array.

  4. Next, we iterate over each element in the array, updating the left dictionary with the index of the first occurrence, and the right dictionary with the index of the most recent occurrence of each element.

  5. Initialize an answer variable ans with infinity (inf). This variable will ultimately contain the smallest length of the required subarray.

  6. Iterate over the elements again, focusing on those with a frequency equal to the degree. Calculate the length of the subarray for these elements using their first and last occurrence indices.

  7. Update ans with the smallest length found.

  8. Once all elements have been processed, ans will have the length of the shortest subarray that has the degree of the original array.

With these steps, we efficiently find the shortest subarray by utilizing the frequency and positional information of elements and avoid unnecessary computations.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The implementation of the solution can be deconstructed into several parts to understand how it efficiently solves the problem using algorithms and data structures.

  1. Counter Data Structure: At the beginning of the solution, we use Python's Counter from the collections module to tally up the occurrences of each element. The Counter object cnt will count the frequency of each number in nums.

    1cnt = Counter(nums)
  2. Calculating the Degree: Once we have the count of each number, we can easily determine the degree of the original array, which is simply the highest frequency found in cnt.

    1degree = cnt.most_common()[0][1]
  3. Tracking Indices with Dictionaries: We make use of two dictionaries, left and right. The left dictionary stores the first occurrence index of each number, and the right dictionary keeps track of the last occurrence index. This step is crucial for understanding the range of each element.

    1left, right = {}, {}
    2for i, v in enumerate(nums):
    3    if v not in left:
    4        left[v] = i
    5    right[v] = i
  4. Finding the Shortest Subarray: We initialize ans to infinity (inf) to ensure any valid subarray length found will be smaller.

    1ans = inf

    We iterate over each key value v in the Counter:

    1for v in nums:

    For those numbers whose count equals the degree, we calculate the length t as the difference between their last and first occurrence indices plus one.

    1if cnt[v] == degree:
    2    t = right[v] - left[v] + 1

    We then compare t with ans to determine if we've found a smaller subarray. If t is smaller, we update ans.

    1if ans > t:
    2    ans = t
  5. Returning the Answer: After the loop finishes, ans contains the length of the smallest possible subarray with the same degree as nums, and we return it.

    1return ans

This solution effectively leverages hash maps (dictionaries) to track the indices of each element while using the Counter to determine their frequencies. By doing so, it provides an O(n) time complexity solution where n is the number of elements in nums, because each element is processed a constant number of times.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

To illustrate the solution approach, let's walk through an example:

Suppose we have the following array nums:

1nums = [1, 2, 2, 3, 1]

Firstly, we use Counter from the collections module to count the occurrences of each number in nums. The Counter object cnt is as follows:

1cnt = Counter(nums)  # cnt = {1:2, 2:2, 3:1}

Next, we determine the degree of the array, which is the maximum count for any number in cnt. In our example:

1degree = cnt.most_common()[0][1]  # degree = 2, since both 1 and 2 appear twice.

Now, we need to keep track of the first and last occurrences of each element. We use two dictionaries, left and right, to store these indices:

1left = {}
2right = {}
3for i, v in enumerate(nums):
4    if v not in left:
5        left[v] = i  # left = {1:0, 2:1, 3:3}
6    right[v] = i  # right = {1:4, 2:2, 3:3}

We initialize ans to infinity (inf) to ensure we can easily find the minimum subarray length:

1ans = inf

We iterate over each number 'v' in nums, and for those numbers whose count equals the degree, we compute the subarray length 't':

1# Pseudo-code iteration
2for v in nums:
3    if cnt[v] == degree:
4        t = right[v] - left[v] + 1
5
6        # For number 1: t = right[1] - left[1] + 1 = 4 - 0 + 1 = 5
7        # For number 2: t = right[2] - left[2] + 1 = 2 - 1 + 1 = 2

After we calculate 't' for both 1 and 2, we find that the subarray [2, 2] is the shortest subarray with the degree of the array:

1# Pseudo-code comparison and update
2if ans > t:
3    ans = t  # ans = min(inf, 5) = 5 for number 1, then ans = min(5, 2) = 2 for number 2

Therefore, the smallest length of a contiguous subarray that has the same degree as the entire array is 2, which corresponds to the subarray [2, 2], and we return this result:

1return ans  # Returns 2

This walkthrough demonstrates how the solution utilizes Counter to find the degree and uses dictionaries to find the range of each element. The subarray length is then computed and minimized to find the shortest subarray with the degree of the original array.

Not Sure What to Study? Take the 2-min Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Python Solution

1from collections import Counter
2from typing import List
3
4class Solution:
5    def findShortestSubArray(self, nums: List[int]) -> int:
6        # Count the frequency of each element in nums
7        frequency_counter = Counter(nums)
8        # Find the degree of the array (the maximum frequency of any element)
9        degree = max(frequency_counter.values())
10      
11        # Initialize dictionaries to store the first and last positions of each element
12        first_position = {}
13        last_position = {}
14      
15        # Loop through the list and populate first_position and last_position
16        for index, value in enumerate(nums):
17            if value not in first_position:  # Record the first occurrence if not already done
18                first_position[value] = index
19            last_position[value] = index  # Always update to the last occurrence
20      
21        # Initialize answer with infinity (act as a very large number)
22        shortest_subarray_length = float('inf')
23      
24        # Find the shortest subarray length that has the same degree
25        for element in frequency_counter:
26            if frequency_counter[element] == degree:
27                current_length = last_position[element] - first_position[element] + 1
28                if shortest_subarray_length > current_length:
29                    shortest_subarray_length = current_length
30      
31        # Return the length of the shortest subarray with the same degree as the entire array
32        return shortest_subarray_length
33

Java Solution

1class Solution {
2    public int findShortestSubArray(int[] nums) {
3        // HashMap to store the frequencies of numbers
4        Map<Integer, Integer> count = new HashMap<>();
5      
6        // HashMap to store the first index at which a number appears
7        Map<Integer, Integer> firstIndex = new HashMap<>();
8      
9        // HashMap to store the last index at which a number appears
10        Map<Integer, Integer> lastIndex = new HashMap<>();
11      
12        // Variable to keep track of the degree of the array
13        int degree = 0;
14      
15        // Iterate through the array to populate the maps and find the maximum degree
16        for (int i = 0; i < nums.length; ++i) {
17            int number = nums[i];
18            count.put(number, count.getOrDefault(number, 0) + 1);
19            degree = Math.max(degree, count.get(number));
20          
21            // Only set the firstIndex for the number if it hasn't been set before
22            if (!firstIndex.containsKey(number)) {
23                firstIndex.put(number, i);
24            }
25          
26            // Always update the lastIndex when the number is encountered
27            lastIndex.put(number, i);
28        }
29      
30        // Variable to store the length of the shortest subarray with the same degree as the whole array
31        int shortestSubarrayLength = Integer.MAX_VALUE;
32      
33        // Iterate over the array to find the shortest subarray length
34        for (int number : nums) {
35            if (count.get(number) == degree) { // If the current number contributes to the array degree
36                int tempLength = lastIndex.get(number) - firstIndex.get(number) + 1; // Calculate subarray length
37                if (shortestSubarrayLength > tempLength) {
38                    shortestSubarrayLength = tempLength; // Update shortest length if smaller subarray found
39                }
40            }
41        }
42        // Return the shortest subarray length with degree equal to that of the whole array
43        return shortestSubarrayLength;
44    }
45}
46

C++ Solution

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    int findShortestSubArray(vector<int>& nums) {
8        // Maps to keep track of the frequency, first occurrence, and last occurrence of elements.
9        unordered_map<int, int> count;
10        unordered_map<int, int> firstOccurrence;
11        unordered_map<int, int> lastOccurrence;
12      
13        // Degree of the array, which is the maximum frequency of any element.
14        int degree = 0;
15      
16        // Iterate through the array to populate the maps.
17        for (int i = 0; i < nums.size(); ++i) {
18            int value = nums[i];
19          
20            // Increase the count for this value and update the degree.
21            degree = max(degree, ++count[value]);
22          
23            // Record the first occurrence of this value.
24            if (firstOccurrence.count(value) == 0) {
25                firstOccurrence[value] = i;
26            }
27          
28            // Update the last occurrence of this value.
29            lastOccurrence[value] = i;
30        }
31      
32        // Initialize the answer as a large number.
33        int minLength = INT_MAX;
34      
35        // Loop through the array again to find the shortest subarray with the same degree.
36        for (const auto& kv : count) {
37            int value = kv.first;
38            if (count[value] == degree) {
39                // Calculate the length of the subarray for this value.
40                int length = lastOccurrence[value] - firstOccurrence[value] + 1;
41              
42                // Update the answer if this length is smaller.
43                minLength = min(minLength, length);
44            }
45        }
46      
47        // Return the minimum length found.
48        return minLength;
49    }
50};
51

Typescript Solution

1// Import statement not required in TypeScript for built-in types.
2
3// Function to find the smallest subarray length that has the same degree as the entire array.
4function findShortestSubArray(nums: number[]): number {
5    // Object to keep track of the frequency of elements.
6    const count: Record<number, number> = {};
7    // Object to keep track of the first occurrence index of each element.
8    const firstOccurrence: Record<number, number> = {};
9    // Object to keep track of the last occurrence index of each element.
10    const lastOccurrence: Record<number, number> = {};
11
12    // Variable to store the degree of the array (maximum frequency of any element).
13    let degree: number = 0;
14
15    // Iterate through the array to populate the objects.
16    nums.forEach((value, index) => {
17        // Initialize the value in the count object if it doesn't exist.
18        if (count[value] === undefined) {
19            count[value] = 0;
20        }
21        // Increase the frequency count for this value and update the degree.
22        degree = Math.max(degree, ++count[value]);
23      
24        // Record the first occurrence index of this value.
25        if (firstOccurrence[value] === undefined) {
26            firstOccurrence[value] = index;
27        }
28      
29        // Update the last occurrence index of this value.
30        lastOccurrence[value] = index;
31    });
32
33    // Variable to store the minimum length of the subarray with the same degree as the entire array.
34    let minLength: number = Infinity;  // 'Infinity' is used here as a large number.
35
36    // Loop through the elements in the count object to find the length of the shortest subarray with the same degree.
37    Object.keys(count).forEach(key => {
38        const value = parseInt(key);
39        // Check if current element has the same frequency as the degree of the array.
40        if (count[value] === degree) {
41            // Calculate the length of the subarray for this element.
42            const length = lastOccurrence[value] - firstOccurrence[value] + 1;
43            // Update the minLength if this subarray is shorter.
44            minLength = Math.min(minLength, length);
45        }
46    });
47
48    // Return the minLength found.
49    return minLength;
50}
51
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

The time complexity of the code is primarily determined by several factors: iterating over the list once which is O(n), the Counter operation, the most_common() operation, and the second iteration over the unique elements with respect to the degree.

  • Constructing the counter cnt from the nums list has a time complexity of O(n) as it requires a full pass through the list to count the occurrences of each element.
  • most_common() is then called on the Counter, which in the worst case can take O(k log k) time complexity where k is the number of unique elements since it sorts the elements based on their counts.
  • Then we have the second for-loop that iterates through each element in nums to update left and right dictionaries. This loop runs once for each of the n elements in the list, and hence it is O(n).
  • Finally, we have another for-loop that goes through each of the unique elements of the nums list to find the shortest subarray length. In the worst case, this loop runs for k unique elements leading to O(k) time complexity.

Combining these, the total worst-case time complexity of the code is O(n + k log k + n + k). Usually k will be much smaller than n as it's the count of the unique elements, so it can be approximated to O(n + n + k log k) which simplifies to O(n + k log k).

For space complexity:

  • We have cnt which is a Counter of all elements in nums and it will take O(k) space.
  • Two dictionaries left and right that also will store at most k elements each, contributing to another O(k + k) which is O(2k) space.
  • There are no other significant data structures that use up space.

Thus, the total space complexity is O(k) when combining cnt, left, and right since constants are dropped in the Big O notation.

So, the final time and space complexities are O(n + k log k) and O(k) respectively.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫