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:
-
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. -
Determine the degree by looking at the frequency of the most common element in the
Counter
. -
Two dictionaries,
left
andright
, are used to store the first and last occurrences (indices) of each element in the array. -
Next, we iterate over each element in the array, updating the
left
dictionary with the index of the first occurrence, and theright
dictionary with the index of the most recent occurrence of each element. -
Initialize an answer variable
ans
with infinity (inf
). This variable will ultimately contain the smallest length of the required subarray. -
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.
-
Update
ans
with the smallest length found. -
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.
-
Counter Data Structure: At the beginning of the solution, we use Python's
Counter
from thecollections
module to tally up the occurrences of each element. TheCounter
objectcnt
will count the frequency of each number innums
.cnt = Counter(nums)
-
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
.degree = cnt.most_common()[0][1]
-
Tracking Indices with Dictionaries: We make use of two dictionaries,
left
andright
. Theleft
dictionary stores the first occurrence index of each number, and theright
dictionary keeps track of the last occurrence index. This step is crucial for understanding the range of each element.left, right = {}, {} for i, v in enumerate(nums): if v not in left: left[v] = i right[v] = i
-
Finding the Shortest Subarray: We initialize
ans
to infinity (inf
) to ensure any valid subarray length found will be smaller.ans = inf
We iterate over each key value
v
in theCounter
:for 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.if cnt[v] == degree: t = right[v] - left[v] + 1
We then compare
t
withans
to determine if we've found a smaller subarray. Ift
is smaller, we updateans
.if ans > t: ans = t
-
Returning the Answer: After the loop finishes,
ans
contains the length of the smallest possible subarray with the same degree asnums
, and we return it.return 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's walk through an example:
Suppose we have the following array nums
:
nums = [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:
cnt = 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:
degree = 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:
left = {} right = {} for i, v in enumerate(nums): if v not in left: left[v] = i # left = {1:0, 2:1, 3:3} 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:
ans = inf
We iterate over each number 'v' in nums
, and for those numbers whose count equals the degree, we compute the subarray length 't':
# Pseudo-code iteration for v in nums: if cnt[v] == degree: t = right[v] - left[v] + 1 # For number 1: t = right[1] - left[1] + 1 = 4 - 0 + 1 = 5 # 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:
# Pseudo-code comparison and update if ans > t: 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:
return 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
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
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
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
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
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 thenums
list has a time complexity ofO(n)
as it requires a full pass through the list to count the occurrences of each element. most_common()
is then called on theCounter
, which in the worst case can takeO(k log k)
time complexity wherek
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 updateleft
andright
dictionaries. This loop runs once for each of then
elements in the list, and hence it isO(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 fork
unique elements leading toO(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 aCounter
of all elements innums
and it will takeO(k)
space. - Two dictionaries
left
andright
that also will store at mostk
elements each, contributing to anotherO(k + k)
which isO(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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!