LeetCode 697: Degree of an Array Solution in Python – A Step-by-Step Guide

Imagine you’re an array detective handed a list like [1, 2, 2, 3, 1], and your mission is to find the shortest chunk—like [2, 2] with length 2—that contains all instances of the most frequent number (here, 2 appears twice). That’s the challenge of LeetCode 697: Degree of an Array, an easy-level problem that’s all about pinpointing the tightest fit for an array’s most popular elements. Using Python, we’ll explore two solutions: the Best Solution, a single-pass with hash maps approach for efficiency, and an Alternative Solution, a brute-force with frequency count method that’s simpler but less optimized. With detailed examples, beginner-friendly breakdowns—especially for the hash map method—and clear code, this guide will help you crack that case, whether you’re new to coding or leveling up. Let’s dive into that array and start sleuthing!

What Is LeetCode 697: Degree of an Array?

In LeetCode 697: Degree of an Array, you’re given an integer array nums, and your task is to find the length of the shortest contiguous subarray that contains all occurrences of the element(s) with the maximum frequency (the "degree" of the array). Return this length as an integer. For example, with nums = [1, 2, 2, 3, 1], the degree is 2 (1 and 2 both appear twice), and the shortest subarray for 2 is [2, 2] (length 2), so return 2. If multiple elements tie for the maximum frequency, return the shortest subarray among them. This problem tests your ability to track frequencies and subarray spans efficiently.

Problem Statement

Input:

nums: List of integers.

Output: An integer—length of shortest subarray with all occurrences of max-frequency element(s).
Rules:

Degree: Maximum frequency of any element in nums.
Subarray: Contiguous segment containing all instances of a max-frequency element.
Return shortest such subarray length.
If multiple elements tie, return minimum length among them.

Constraints

1 ≤ nums.length ≤ 50,000.
0 ≤ nums[i] < 50,000.

Examples

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

Output: 2 (Degree = 2, shortest subarray [2, 2] for 2)

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

Output: 6 (Degree = 3 for 2, shortest subarray [1, 2, 2, 3, 1, 4] contains all 2s)

Input: nums = [1]

Output: 1 (Degree = 1, subarray [1])

These examples set the array—let’s solve it!

Understanding the Problem: Finding the Shortest Subarray

To solve LeetCode 697: Degree of an Array in Python, we need to find the shortest contiguous subarray in nums that includes all occurrences of any element with the maximum frequency (degree). A brute-force approach—counting frequencies and checking all subarrays—would be O(n²), inefficient for n ≤ 50,000. Since we’re tracking frequency and span, a single-pass with hash maps or a two-pass frequency count can optimize this. We’ll use:

Best Solution (Single-Pass with Hash Maps): O(n) time, O(n) space—fast and elegant.
Alternative Solution (Brute-Force with Frequency Count): O(n²) time, O(n) space—simple but slow.

Let’s start with the single-pass solution, breaking it down for beginners.

Best Solution: Single-Pass with Hash Maps

Why This Is the Best Solution

The single-pass with hash maps approach is the top choice for LeetCode 697 because it’s highly efficient—O(n) time with O(n) space—and uses two hash maps to track frequency and first/last positions of each element in one sweep, calculating the degree and minimum length on the fly. It fits constraints (n ≤ 50,000) perfectly and is intuitive once you see the map logic. It’s like keeping a live tally of who’s most popular and how tightly they’re packed!

How It Works

Think of this as an array tracker:

Step 1: Initialize Hash Maps:

count: Frequency of each number.
first: First index of each number.
last: Last index of each number (updated as we go).

Step 2: Single Pass:

For each num at index i:

Increment count[num].
Set first[num] = i if first occurrence.
Update last[num] = i.

Step 3: Compute Degree and Length:

Track max frequency (degree).
For each num with degree, length = last[num] - first[num] + 1.
Update min length among these.

Step 4: Return Result:

Minimum length found.

It’s like a frequency mapper—track and measure!

Step-by-Step Example

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

Step 1: Init:

count = {}, first = {}, last = {}, degree = 0, min_len = len(nums).

Step 2: Pass:

i=0, 1: count[1]=1, first[1]=0, last[1]=0, degree=1.
i=1, 2: count[2]=1, first[2]=1, last[2]=1, degree=1.
i=2, 2: count[2]=2, last[2]=2, degree=2, len=2-1+1=2, min_len=2.
i=3, 3: count[3]=1, first[3]=3, last[3]=3, degree=2.
i=4, 1: count[1]=2, last[1]=4, degree=2, len=4-0+1=5, min_len=2.

Step 3: Degree = 2 (1 and 2), min_len = 2 (for 2).
Step 4: Return 2.
Output: 2.

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

Step 1: Init:

count = {}, first = {}, last = {}, degree = 0, min_len = 7.

Step 2: Pass:

i=0, 1: count[1]=1, first[1]=0, last[1]=0, degree=1.
i=1, 2: count[2]=1, first[2]=1, last[2]=1, degree=1.
i=2, 2: count[2]=2, last[2]=2, degree=2, len=2-1+1=2, min_len=2.
i=3, 3: count[3]=1, first[3]=3, last[3]=3, degree=2.
i=4, 1: count[1]=2, last[1]=4, degree=2, len=4-0+1=5, min_len=2.
i=5, 4: count[4]=1, first[4]=5, last[4]=5, degree=2.
i=6, 2: count[2]=3, last[2]=6, degree=3, len=6-1+1=6, min_len=6.

Step 3: Degree = 3 (2), min_len = 6.
Step 4: Return 6.
Output: 6.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def findShortestSubarray(self, nums: List[int]) -> int:
        # Step 1: Initialize hash maps and variables
        count = {}
        first = {}
        last = {}
        degree = 0
        min_len = len(nums)

        # Step 2: Single pass to track frequency and positions
        for i, num in enumerate(nums):
            if num not in first:
                first[num] = i
            last[num] = i
            count[num] = count.get(num, 0) + 1
            if count[num] > degree:
                degree = count[num]
                min_len = last[num] - first[num] + 1
            elif count[num] == degree:
                curr_len = last[num] - first[num] + 1
                min_len = min(min_len, curr_len)

        # Step 3: Return minimum length
        return min_len

Lines 4-9: Init: Hash maps for count, first/last positions, degree, and min length.
Lines 12-21: Pass:

Update first/last, increment count, adjust degree and min_len.

Line 24: Return min_len.
Time Complexity: O(n)—single pass through array.
Space Complexity: O(n)—hash maps.

This is like an array sleuth—map and measure!

Alternative Solution: Brute-Force with Frequency Count

Why an Alternative Approach?

The brute-force with frequency count approach first counts frequencies—O(n²) time, O(n) space. It’s simpler, finding the degree and then checking all subarrays, but inefficient for large n. It’s like counting votes and then searching for the tightest winner’s group!

How It Works

Picture this as a frequency checker:

Step 1: Count frequencies:

Use Counter to find degree.

Step 2: Find shortest subarray:

For each element with degree, check all subarrays containing all occurrences.

Step 3: Update min length:

Track shortest valid length.

Step 4: Return result.

It’s like a subarray searcher—count and scan!

Step-by-Step Example

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

Step 1: Counter: {1: 2, 2: 2, 3: 1}, degree = 2.
Step 2: Check:

For 1: [0, 4] (len=5), [1, 4] (len=4), etc., min=5.
For 2: [1, 2] (len=2), min=2.

Step 3: Min_len = 2 (for 2).
Step 4: Return 2.
Output: 2.

Code for Brute-Force Approach

from collections import Counter

class Solution:
    def findShortestSubarray(self, nums: List[int]) -> int:
        # Step 1: Count frequencies
        count = Counter(nums)
        degree = max(count.values())

        # Step 2: Find shortest subarray for each max-freq element
        min_len = len(nums)
        for num, freq in count.items():
            if freq == degree:
                # Find first and last occurrence
                first = nums.index(num)
                last = len(nums) - 1 - nums[::-1].index(num)
                curr_len = last - first + 1
                min_len = min(min_len, curr_len)

        # Step 3: Return minimum length
        return min_len

Line 1: Import Counter.
Lines 6-8: Count: Get degree with Counter.
Lines 11-16: Check:

For each degree element, find first/last, compute length, update min.

Line 19: Return min_len.
Time Complexity: O(n²)—index search is O(n) per element.
Space Complexity: O(n)—Counter.

It’s a frequency scanner—count and search!

Comparing the Two Solutions

Single-Pass (Best):

Pros: O(n) time, O(n) space, fast and efficient.
Cons: Hash map logic less obvious.

Brute-Force (Alternative):

Pros: O(n²) time, O(n) space, straightforward.
Cons: Much slower.

Single-pass wins for efficiency.

Additional Examples and Edge Cases

Input: nums = [1]

Output: 1.

Input: nums = [1, 1, 1]

Output: 3.

Single-pass handles these well.

Complexity Breakdown

Single-Pass: Time O(n), Space O(n).
Brute-Force: Time O(n²), Space O(n).

Single-pass is optimal.

Key Takeaways

Single-Pass: Map tracking—smart!
Brute-Force: Count searching—clear!
Arrays: Measuring is fun.
Python Tip: Maps rock—see Python Basics.

Final Thoughts: Crack That Array Case

LeetCode 697: Degree of an Array in Python is a fun array challenge. Single-pass with hash maps offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 560: Subarray Sum Equals K or LeetCode 53: Maximum Subarray. Ready to sleuth? Head to Solve LeetCode 697 on LeetCode and find that shortest subarray today!