#697

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Degree of an Array

Find the shortest subarray with the same degree as the given array using efficient array scanning and hash lookups.

Problem Statement

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 that has the same degree as nums.

For example, consider nums = [1,2,2,3,1]. The degree of this array is 2 because both elements 1 and 2 appear twice. The task is to find the shortest subarray that has the same degree, which in this case would be 2.

Examples

Example 1

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

Output: 2

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

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.

Solution Approach

Track Frequency and Indices

First, scan the array to count the frequency of each element and record the first and last occurrence of each element using a hash table. This allows you to determine the degree and potential subarrays.

Evaluate Minimal Subarray Length

For each element that contributes to the degree of the array, compute the subarray length from its first to last occurrence. Return the shortest such length.

Optimize Using One Pass

While calculating frequencies and indices, ensure the solution only makes one pass through the array, providing an O(N) time complexity. This avoids unnecessary recomputation and ensures scalability for larger arrays.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity is O(N), as we make a single pass through the array to track frequencies and indices. The space complexity is O(N) due to the storage of element counts and their positions in a hash table.

What Interviewers Usually Probe

The candidate should be comfortable with array scanning and hash table usage.
Look for clarity in their explanation of tracking both frequency and positions.
The ability to optimize with a single pass through the array is crucial.

Common Pitfalls or Variants

Common pitfalls

Failing to track both the first and last occurrence of elements, leading to incorrect subarray length calculations.
Overcomplicating the problem by attempting to brute force the subarrays instead of leveraging the hash table for direct access.
Not maintaining the degree accurately across elements, which could lead to incorrect results.

Follow-up variants

Handling arrays with no repeated elements, where the degree is 1.
Considering very large arrays, where space and time efficiency becomes critical.
Adapting the solution for arrays with negative integers, ensuring the algorithm is generalized.

FAQ

How can I solve the Degree of an Array problem?

To solve the Degree of an Array problem, track element frequencies and their first and last occurrences, then compute the minimal subarray length.

What is the optimal time complexity for this problem?

The optimal time complexity for this problem is O(N), where N is the length of the array, by scanning it just once and using a hash table.

What are the common mistakes in solving Degree of an Array?

Common mistakes include failing to track both the first and last occurrence of elements and attempting a brute force solution instead of using a hash table.

How do I handle large input arrays for this problem?

For large input arrays, the solution should remain O(N) in time and O(N) in space by using efficient array scanning and hash table usage.

What pattern does the Degree of an Array problem follow?

The problem follows the pattern of array scanning plus hash table lookup, where you efficiently track and compute frequencies and positions to determine the degree and subarray length.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        degree = cnt.most_common()[0][1]
        left, right = {}, {}
        for i, v in enumerate(nums):
            if v not in left:
                left[v] = i
            right[v] = i
        ans = inf
        for v in nums:
            if cnt[v] == degree:
                t = right[v] - left[v] + 1
                if ans > t:
                    ans = t
        return ans

Solution 2

#### Go

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        degree = cnt.most_common()[0][1]
        left, right = {}, {}
        for i, v in enumerate(nums):
            if v not in left:
                left[v] = i
            right[v] = i
        ans = inf
        for v in nums:
            if cnt[v] == degree:
                t = right[v] - left[v] + 1
                if ans > t:
                    ans = t
        return ans

Continue Practicing

#692 top k frequent words #691 stickers to spell word #690 employee importance