algoadvance

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.

Clarifying Questions

1. What specific types of elements are in the array?
   • The array consists of non-negative integers.
2. Can there be multiple subarrays that have the same degree?
   • Yes, but you are required to return the length of the smallest one.
3. Does the array always have at least one element?
   • Yes, the problem states the array is non-empty.

Strategy

1. Identify the Frequency and Positions:
   • Traverse through the array to calculate the frequency of each element.
   • At the same time, record the first and last positions of each element.
2. Determine the Degree of the Array:
   • The degree of the array is the maximum frequency of any element.
3. Calculate Lengths of Subarrays for Elements with Maximum Frequency:
   • For each element that contributes to the degree, calculate the length of the subarray (from its first to its last occurrence).
   • Keep track of the minimum length across these subarrays.

Code

def findShortestSubArray(nums):
    from collections import defaultdict

    # To store the frequency of elements
    num_freq = defaultdict(int)
    # To store the first position of elements
    first_position = {}
    # To store the last position of elements
    last_position = {}

    for i, num in enumerate(nums):
        num_freq[num] += 1
        if num not in first_position:
            first_position[num] = i
        last_position[num] = i

    # Find the degree of the array
    degree = max(num_freq.values())

    min_length = float('inf')

    # For each number, calculate the length of the subarray if that number contributes to the degree
    for num, count in num_freq.items():
        if count == degree:
            length = last_position[num] - first_position[num] + 1
            min_length = min(min_length, length)

    return min_length

# Example Usage
nums = [1, 2, 2, 3, 1, 4, 2]
print(findShortestSubArray(nums))  # Output: 6

Time Complexity

• Time Complexity: O(n)
  • We traverse the array multiple times to collect first and last positions, calculate frequency, and find the minimum length. However, each traversal is linear with respect to the size of the array, thus leading to an overall O(n) complexity.
• Space Complexity: O(n)
  • We use dictionaries to store the frequency and positions of elements, which requires extra space proportional to the number of unique elements in the array. In the worst case, this space usage is linear with respect to the size of the input array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?