LeetCode 697 - Degree of an Array

The problem asks us to find the shortest contiguous subarray of an array nums that has the same degree as the original array. The degree of an array is defined as the maximum frequency of any element in that array.

leetcodeeasyarrayhash-table

LeetCode Problem 697

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to find the shortest contiguous subarray of an array nums that has the same degree as the original array. The degree of an array is defined as the maximum frequency of any element in that array. In other words, if the element that appears the most appears k times, then k is the degree.

The input nums is a non-empty list of non-negative integers, and the output is a single integer representing the length of the smallest contiguous subarray that contains all occurrences of one of the elements contributing to the array's degree.

The constraints tell us that the array can be fairly large, up to 50,000 elements, and each element value can also be large, up to 49,999. This means we need a solution that is at least linear in time, as brute force approaches checking all possible subarrays would be far too slow. Important edge cases include arrays with all identical elements, arrays where multiple elements have the same maximum frequency, and arrays with degree 1 where every element is unique.

Approaches

A brute-force approach would be to compute the degree of the array, then for each element that occurs as many times as the degree, check all subarrays containing all occurrences of that element and track the smallest length. This approach is correct but would be very slow because generating all subarrays would take O(n²) time and is not feasible for n up to 50,000.

The key insight for an optimal solution is to track the first and last occurrence of each number while computing their frequency in a single pass. Once we know the first and last occurrence of every number, we can compute the smallest contiguous subarray length for elements with maximum frequency by simply taking last_index - first_index + 1. This reduces the problem to a single traversal of the array and a constant-time calculation per unique element, resulting in an O(n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Check all subarrays for each element contributing to the degree
Optimal O(n) O(n) Track frequency, first index, last index, then compute minimal subarray length

Algorithm Walkthrough

  1. Initialize three dictionaries: freq to store frequency of each number, first_index to store the first occurrence index, and last_index to store the last occurrence index.
  2. Iterate through the array using an index i. For each element num:
  • Increment freq[num] by 1.
  • If num is not in first_index, set first_index[num] = i.
  • Always update last_index[num] = i.
  1. Compute the degree of the array as the maximum value in freq.
  2. Initialize a variable min_length to infinity. Iterate through each number in freq:
  • If freq[num] equals the degree, calculate the length of the subarray containing all occurrences as last_index[num] - first_index[num] + 1.
  • Update min_length if this length is smaller than the current min_length.
  1. Return min_length.

This algorithm works because the subarray that captures all occurrences of a number contributing to the degree must start at its first occurrence and end at its last occurrence. By considering only these indices, we ensure the subarray contains all instances of that number and is minimal.

Python Solution

from typing import List

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        freq = {}
        first_index = {}
        last_index = {}
        
        for i, num in enumerate(nums):
            if num not in first_index:
                first_index[num] = i
            last_index[num] = i
            freq[num] = freq.get(num, 0) + 1
        
        degree = max(freq.values())
        min_length = float('inf')
        
        for num in freq:
            if freq[num] == degree:
                min_length = min(min_length, last_index[num] - first_index[num] + 1)
        
        return min_length

The Python implementation follows the algorithm directly. We track first and last occurrences and frequency in a single pass through the array. After computing the degree, we iterate over the frequency dictionary to find the minimal subarray length for elements with maximum frequency.

Go Solution

func findShortestSubArray(nums []int) int {
    freq := make(map[int]int)
    firstIndex := make(map[int]int)
    lastIndex := make(map[int]int)
    
    for i, num := range nums {
        if _, exists := firstIndex[num]; !exists {
            firstIndex[num] = i
        }
        lastIndex[num] = i
        freq[num]++
    }
    
    degree := 0
    for _, count := range freq {
        if count > degree {
            degree = count
        }
    }
    
    minLength := len(nums)
    for num, count := range freq {
        if count == degree {
            length := lastIndex[num] - firstIndex[num] + 1
            if length < minLength {
                minLength = length
            }
        }
    }
    
    return minLength
}

In Go, maps are used similarly to Python dictionaries. The key differences are that we explicitly check for the existence of a key before setting the first occurrence and that we initialize minLength to the array length instead of infinity, which is more idiomatic in Go.

Worked Examples

Example 1: [1,2,2,3,1]

Step i num freq first_index last_index
1 0 1 {1:1} {1:0} {1:0}
2 1 2 {1:1,2:1} {1:0,2:1} {1:0,2:1}
3 2 2 {1:1,2:2} {1:0,2:1} {1:0,2:2}
4 3 3 {1:1,2:2,3:1} {1:0,2:1,3:3} {1:0,2:2,3:3}
5 4 1 {1:2,2:2,3:1} {1:0,2:1,3:3} {1:4,2:2,3:3}

Degree is 2. For numbers 1 and 2: lengths are 4-0+1=5 and 2-1+1=2. Minimum length is 2.

Example 2: [1,2,2,3,1,4,2]

Degree is 3 for number 2. Subarray length is 6-1+1=6.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to compute frequency and indices, then iterate through unique numbers
Space O(n) Dictionaries/maps to store frequency and first/last occurrence of each unique element

The reasoning is that the number of unique elements is at most n, and all operations per element are constant time.

Test Cases

# test cases
sol = Solution()

# provided examples
assert sol.findShortestSubArray([1,2,2,3,1]) == 2  # minimal subarray [2,2]
assert sol.findShortestSubArray([1,2,2,3,1,4,2]) == 6  # minimal subarray [2,2,3,1,4,2]

# edge cases
assert sol.findShortestSubArray([1]) == 1  # single element
assert sol.findShortestSubArray([1,1,1,1]) == 4  # all same elements
assert sol.findShortestSubArray([1,2,3,4,5]) == 1  # all unique elements
assert sol.findShortestSubArray([1,2,2,3,1,1,2]) == 6  # multiple elements with same degree
Test Why
[1,2,2,3,1] Basic case with two elements contributing to degree
[1,2,2,3,1,4,2] Degree > 2 with subarray spanning middle of array
[1] Single element array
[1,1,1,1] All elements identical, subarray is full array
[1,2,3,4,5] Degree 1, minimal subarray length is 1
[1,2,2,3,1,1,2] Multiple elements share max frequency, pick shortest subarray

Edge Cases

A critical edge case is when the array has all identical elements, such as [1,1,1,1]. In this case, the degree is equal to the length of the array, and the minimal subarray containing all occurrences is the entire array. The implementation handles this correctly because it computes last_index - first_index + 1, which equals the array length.

Another edge case is when multiple elements share the maximum frequency. For example, `[1