Degree of an Array: Hash Map Tracking

LeetCode #697, Degree of an Array, is a great example of how a hash map can store more than just counts. The twist here is that you need to track three pieces of information per element, and you can do it all in one pass. Once you see the pattern, it clicks fast.

The problem

Given a non-empty array of non-negative integers nums, the degree of the array is the maximum frequency of any element. Your task is to find the smallest possible length of a contiguous subarray of nums that has the same degree as nums.

In other words: find the element that appears most often, then find the shortest window that contains all of its occurrences. If multiple elements share the same max frequency, pick the one with the shortest span.

The approach

The brute force way would be to count frequencies, find the degree, then for each element with that frequency, scan the array to find its first and last occurrence. That works but requires multiple passes.

The smarter approach: do everything in a single pass. For each element, maintain three things in a hash map:

• count: how many times the element has appeared so far
• first: the index where the element first appeared
• last: the index where the element most recently appeared

As you scan through the array, you update these values. After processing each element, you check if its count equals or exceeds the current max frequency. If it does, you compute the span (last - first + 1) and keep the smallest one.

The code

def find_shortest_sub_array(nums):
    count = {}
    first = {}
    last = {}

    for i, v in enumerate(nums):
        if v not in first:
            first[v] = i
        last[v] = i
        count[v] = count.get(v, 0) + 1

    degree = max(count.values())
    result = len(nums)

    for v in count:
        if count[v] == degree:
            result = min(result, last[v] - first[v] + 1)

    return result

The first loop does one pass over the array, populating all three dictionaries. For each element, if it is the first time we see it, we record its index in first. We always update last and increment count.

The second loop iterates over the keys of count (at most n unique values, but often far fewer). For every element whose count equals the degree, we compute last[v] - first[v] + 1 and take the minimum.

You could also combine both loops into one by tracking the degree and result as you go. The logic is the same either way.

Complexity analysis

Both approaches are O(n) in time and space. The single-pass version has a smaller constant because it avoids rescanning the array for first/last indices.

Building blocks

Frequency counter with metadata

The core pattern here is a frequency counter that tracks more than just counts. Instead of a simple Counter or defaultdict(int), you maintain parallel dictionaries (or a single dictionary of tuples/objects) that store auxiliary data alongside each count.

count = {}
first = {}
last = {}
for i, v in enumerate(items):
    if v not in first:
        first[v] = i
    last[v] = i
    count[v] = count.get(v, 0) + 1

This pattern shows up whenever you need to answer questions like "which element appears most, and where?" or "what is the span of the most frequent element?" The idea of augmenting a frequency map with positional data is reusable across many problems.

Edge cases

• Single element: [5] has degree 1. The shortest subarray is length 1.
• All elements the same: [3, 3, 3] has degree 3, and the shortest subarray is the whole array.
• Multiple elements with the same max frequency: [1, 2, 2, 1] has degree 2 for both 1 and 2. Element 2 spans indices 1 to 2 (length 2), while element 1 spans indices 0 to 3 (length 4). The answer is 2.
• No repeated elements: [1, 2, 3, 4] has degree 1. Every single-element subarray works, so the answer is 1.

From understanding to recall

Reading through this solution, the approach feels natural. Track counts, track positions, take the minimum span among max-frequency elements. But when you sit down to solve a similar problem a week from now, will the details come back? Will you remember to track first separately from last? Will you remember to handle ties by comparing spans?

That is where spaced repetition helps. You drill the frequency-counter-with-metadata pattern as a standalone building block, typing it from scratch at increasing intervals. After a few rounds, the pattern fires automatically when you see a problem that needs it.

Related posts

• Top K Frequent Elements - Another frequency counting problem that builds on the same hash map foundation
• Subarray Sum Equals K - Uses a hash map to track prefix sums, a related "augmented map" technique
• Contiguous Array - Tracks first occurrence of prefix sums to find the longest valid subarray