697. Degree of an Array

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.

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.

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.

Solution Implementation

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 using problem constraints.