697. Degree of an Array - Solution & Explanation

The problem

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.

Example 1:

Input: nums = [1,2,2,3,1]
Output: 2
Explanation: 
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
Explanation: 
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.

Approach overview

Problem Overview: You are given an integer array. The degree of the array is the maximum frequency of any element. The task is to find the length of the smallest contiguous subarray that has the same degree as the entire array.

Approach 1: Using HashMap to Track Frequencies and Positions (O(n) time, O(n) space)

The key observation: the degree depends on the element with the highest frequency, but the answer depends on the distance between that element's first and last occurrence. Traverse the array once and maintain three hash maps (or dictionaries): one for frequency, one for the first index where each number appears, and one for the last index. Each time you see a number, increment its count and update its last position. After traversal, compute the degree and evaluate the subarray length for elements that reach that degree using lastIndex - firstIndex + 1. Hash lookups make each update O(1), so the full pass is O(n). This approach is the most direct and works well whenever you need to track frequencies and positions in an hash table.

Approach 2: Two-Pass Array Traversal (O(n) time, O(n) space)

This version separates the frequency calculation from the subarray length calculation. In the first pass, iterate through the array and compute the frequency of each element using a hash map while tracking the overall degree. In the second pass, record the first occurrence of each number and update the minimum window length whenever that number reaches the array's degree. The logic focuses only on elements that match the degree, which simplifies reasoning during interviews. The time complexity remains O(n) because each element is processed a constant number of times, and the hash map stores up to n distinct values, resulting in O(n) space.

Recommended for interviews: The HashMap frequency and position tracking approach is what most interviewers expect. It demonstrates that you recognize the relationship between element frequency and the minimal window containing all occurrences. Starting with the idea of counting frequencies shows baseline understanding, but extending it to track first and last positions proves you can translate observations into an optimal O(n) solution using hash-based lookups.

Approach 1: Using HashMap to Track Frequencies and Positions

This approach involves creating a HashMap for tracking the frequency of each element, and two other HashMaps to keep track of the first and last indices of each element. The goal is to determine the degree of the array, then find the shortest subarray that has this same degree.

Python

def findShortestSubarray(nums):
    from collections import defaultdict
    count = defaultdict(int)
    first, last = {}, {}
    degree, minLen = 0, len(nums)
    
    for i, num in enumerate(nums):
        count[num] += 1
        if num not in first:
            first[num] = i
        last[num] = i
        degree = max(degree, count[num])
    
    for num in count:
        if count[num] == degree:
            minLen = min(minLen, last[num] - first[num] + 1)
    
    return minLen

if __name__ == "__main__":
    nums = [1, 2, 2, 3, 1]
    print(findShortestSubarray(nums))

Java

import java.util.HashMap;

public class DegreeOfArray {
    public static int findShortestSubarray(int[] nums) {
        HashMap<Integer, Integer> count = new HashMap<>();
        HashMap<Integer, Integer> first = new HashMap<>();
        HashMap<Integer, Integer> last = new HashMap<>();
        int degree = 0, minLen = nums.length;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            count.put(num, count.getOrDefault(num, 0) + 1);
            first.putIfAbsent(num, i);
            last.put(num, i);
            degree = Math.max(degree, count.get(num));
        }
        for (int key : count.keySet()) {
            if (count.get(key) == degree) {
                minLen = Math.min(minLen, last.get(key) - first.get(key) + 1);
            }
        }
        return minLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 1};
        System.out.println(findShortestSubarray(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findShortestSubarray(vector<int>& nums) {
    unordered_map<int, int> count, first, last;
    int degree = 0, minLen = nums.size();
    for (int i = 0; i < nums.size(); i++) {
        int num = nums[i];
        count[num]++;
        if (first.find(num) == first.end()) {
            first[num] = i;
        }
        last[num] = i;
        degree = max(degree, count[num]);
    }
    for (const auto& kv : count) {
        if (kv.second == degree) {
            minLen = min(minLen, last[kv.first] - first[kv.first] + 1);
        }
    }
    return minLen;
}

int main() {
    vector<int> nums = {1, 2, 2, 3, 1};
    cout << findShortestSubarray(nums) << endl;
    return 0;
}

JavaScript

function findShortestSubarray(nums) {
    let count = {}, first = {}, last = {};
    let degree = 0, minLen = nums.length;

    nums.forEach((num, i) => {
        if (!count[num]) count[num] = 0;
        count[num]++;
        if (first[num] === undefined) first[num] = i;
        last[num] = i;
        degree = Math.max(degree, count[num]);
    });

    for (let num in count) {
        if (count[num] === degree) {
            minLen = Math.min(minLen, last[num] - first[num] + 1);
        }
    }

    return minLen;
}

console.log(findShortestSubarray([1, 2, 2, 3, 1]));

#include <stdio.h>
#include <stdlib.h>

#define MAX 50000

int findShortestSubarray(int* nums, int numsSize) {
    int counts[MAX] = {0};
    int first[MAX];
    int last[MAX];
    for (int i = 0; i < MAX; i++) {
        first[i] = -1;
    }
    int degree = 0, minLen = numsSize;

    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        if (first[num] == -1) {
            first[num] = i;
        }
        last[num] = i;
        counts[num]++;
        if (counts[num] > degree) {
            degree = counts[num];
            minLen = last[num] - first[num] + 1;
        } else if (counts[num] == degree) {
            minLen = (last[num] - first[num] + 1 < minLen) ? 
                      (last[num] - first[num] + 1) : minLen;
        }
    }
    return minLen;
}

int main() {
    int nums[] = {1, 2, 2, 3, 1};
    int result = findShortestSubarray(nums, 5);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

class DegreeOfArray {
    public static int FindShortestSubarray(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        Dictionary<int, int> first = new Dictionary<int, int>();
        Dictionary<int, int> last = new Dictionary<int, int>();
        int degree = 0, minLen = nums.Length;

        for (int i = 0; i < nums.Length; i++) {
            int num = nums[i];
            if (!count.ContainsKey(num)) count[num] = 0;
            count[num]++;
            if (!first.ContainsKey(num)) first[num] = i;
            last[num] = i;
            degree = Math.Max(degree, count[num]);
        }

        foreach (int num in count.Keys) {
            if (count[num] == degree) {
                minLen = Math.Min(minLen, last[num] - first[num] + 1);
            }
        }
        return minLen;
    }

    static void Main(string[] args) {
        int[] nums = { 1, 2, 2, 3, 1 };
        Console.WriteLine(FindShortestSubarray(nums));
    }
}

This Python solution uses collections' defaultdict to manage count tracking and maintains dictionaries for the first and last positions. It efficiently determines the shortest subarray with the array's degree.

Complexity

Time Complexity: O(n) because it iterates through the list.
Space Complexity: O(n) for storing count and indices.

Try this approach in the editor

Approach 2: Two-Pass Array Traversal

This approach first calculates the degree of the array in a single pass, then performs a second traversal to identify the smallest contiguous subarray with the same degree. The second traversal uses the frequency and position data collected during the first pass.

Python

def findShortestSubarray(nums):
    from collections import defaultdict
    count = defaultdict(int)
    first, last = {}, {}
    degree, minLen = 0, len(nums)

    for i, num in enumerate(nums):
        count[num] += 1
        if num not in first:
            first[num] = i
        last[num] = i
        degree = max(degree, count[num])

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

    return minLen

if __name__ == "__main__":
    nums = [1, 2, 2, 3, 1]
    print(findShortestSubarray(nums))

Java

import java.util.HashMap;

public class DegreeOfArray {
    public static int findShortestSubarray(int[] nums) {
        HashMap<Integer, Integer> count = new HashMap<>();
        HashMap<Integer, Integer> first = new HashMap<>();
        HashMap<Integer, Integer> last = new HashMap<>();
        int degree = 0, minLen = nums.length;

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            count.put(num, count.getOrDefault(num, 0) + 1);
            first.putIfAbsent(num, i);
            last.put(num, i);
            degree = Math.max(degree, count.get(num));
        }

        for (int key : count.keySet()) {
            if (count.get(key) == degree) {
                minLen = Math.min(minLen, last.get(key) - first.get(key) + 1);
            }
        }

        return minLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 1};
        System.out.println(findShortestSubarray(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findShortestSubarray(vector<int>& nums) {
    unordered_map<int, int> count, first, last;
    int degree = 0, minLen = nums.size();

    for (int i = 0; i < nums.size(); i++) {
        int num = nums[i];
        count[num]++;
        if (first.find(num) == first.end()) {
            first[num] = i;
        }
        last[num] = i;
        degree = max(degree, count[num]);
    }

    for (const auto& entry : count) {
        if (entry.second == degree) {
            int num = entry.first;
            minLen = min(minLen, last[num] - first[num] + 1);
        }
    }
    return minLen;
}

int main() {
    vector<int> nums = {1, 2, 2, 3, 1};
    cout << findShortestSubarray(nums) << endl;
    return 0;
}

JavaScript

function findShortestSubarray(nums) {
    let count = {}, first = {}, last = {};
    let degree = 0, minLen = nums.length;

    nums.forEach((num, i) => {
        if (!count[num]) count[num] = 0;
        count[num]++;
        if (first[num] === undefined) first[num] = i;
        last[num] = i;
        degree = Math.max(degree, count[num]);
    });

    for (let num in count) {
        if (count[num] === degree) {
            minLen = Math.min(minLen, last[num] - first[num] + 1);
        }
    }

    return minLen;
}

console.log(findShortestSubarray([1, 2, 2, 3, 1]));

#include <stdio.h>
#include <stdlib.h>
#define MAX 50000

int findShortestSubarray(int* nums, int numsSize) {
    int lhs[MAX] = {0}, rhs[MAX] = {0}, counts[MAX] = {0};
    int degree = 0, minLength = numsSize;

    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        counts[num]++;
        if (lhs[num] == 0 && counts[num] == 1) { // This is first occurrence
            lhs[num] = i + 1; // Store as index + 1 to differentiate from initialized 0
        }
        rhs[num] = i; // Always update with the latest index
        if (counts[num] > degree) {
            degree = counts[num];
        }
    }

    for (int i = 0; i < MAX; i++) {
        if (counts[i] == degree) {
            int len = rhs[i] - (lhs[i] - 1) + 1; // Calculate length
            if (len < minLength) {
                minLength = len;
            }
        }
    }

    return minLength;
}

int main() {
    int nums[] = {1, 2, 2, 3, 1};
    int result = findShortestSubarray(nums, 5);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

class DegreeOfArray {
    public static int FindShortestSubarray(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        Dictionary<int, int> first = new Dictionary<int, int>();
        Dictionary<int, int> last = new Dictionary<int, int>();
        int degree = 0, minLen = nums.Length;

        for (int i = 0; i < nums.Length; i++) {
            int num = nums[i];
            if (!count.ContainsKey(num)) count[num] = 0;
            count[num]++;
            if (!first.ContainsKey(num)) first[num] = i;
            last[num] = i;
            degree = Math.Max(degree, count[num]);
        }

        foreach (int num in count.Keys) {
            if (count[num] == degree) {
                minLen = Math.Min(minLen, last[num] - first[num] + 1);
            }
        }
        return minLen;
    }

    static void Main(string[] args) {
        int[] nums = { 1, 2, 2, 3, 1 };
        Console.WriteLine(FindShortestSubarray(nums));
    }
}

This Python implementation uses defaultdict for frequency and dictionary for storing the first and last occurrence of elements. By doing so, it balances out the computation task into two assemblies.

Complexity

Time Complexity: O(n), as the list is traversed twice.
Space Complexity: O(n) due to the storage needs of counts and positional indices.

Try this approach in the editor

Approach 3: Default Approach

func findShortestSubArray(nums []int) int {
	cnt := map[int]int{}
	left := map[int]int{}
	right := map[int]int{}
	var degree int
	for i, v := range nums {
		cnt[v]++
		if degree < cnt[v] {
			degree = cnt[v]
		}
		if _, ok := left[v]; !ok {
			left[v] = i
		}
		right[v] = i
	}
	ans := 100000
	for v, c := range cnt {
		if c == degree {
			t := right[v] - left[v] + 1
			if ans > t {
				ans = t
			}
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using HashMap to Track Frequencies and Positions	Time Complexity: O(n) because it iterates through the list. Space Complexity: O(n) for storing count and indices.
Two-Pass Array Traversal	Time Complexity: O(n), as the list is traversed twice. Space Complexity: O(n) due to the storage needs of counts and positional indices.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap to Track Frequencies and Positions	O(n)	O(n)	General case. Best approach when you need both frequency and index range information.
Two-Pass Array Traversal	O(n)	O(n)	Useful when you prefer separating frequency calculation from window evaluation for clarity.

Frequently asked questions

Is Degree of an Array easy or hard?

Degree of an Array is classified as an Easy problem on LeetCode with an acceptance rate above 50%. The challenge is recognizing that you must track both frequency and index range to compute the smallest valid subarray.

How to solve Degree of an Array in O(n)?

Traverse the array and store three values for each number: frequency, first index, and last index. Track the maximum frequency (the degree). For numbers with that frequency, compute the subarray length using lastIndex - firstIndex + 1 and return the minimum length found.

What is the best approach for Degree of an Array?

The best approach uses a hash map to track each element's frequency along with its first and last occurrence indices. After computing the array's degree, calculate the smallest subarray length for elements that reach that degree using lastIndex - firstIndex + 1. This runs in O(n) time with O(n) space.

Is Degree of an Array asked at Google/Amazon/Meta?

Degree of an Array appears in coding interviews at several large tech companies including Amazon and other FAANG-level companies. The problem tests understanding of hash maps, frequency counting, and identifying minimal subarrays.

What data structure is used in Degree of an Array?

The main data structure is a hash table (hash map). It stores frequencies and indices for each number, allowing constant-time updates and lookups while scanning the array.

What is the time complexity of Degree of an Array?

The optimal solution runs in O(n) time because the array is traversed once (or twice) and each operation on the hash map is O(1) on average. Space complexity is O(n) in the worst case when all elements are unique.

Degree of an Array Python or Java solution approach?

In both Python and Java, the solution typically uses a dictionary or HashMap to store frequency counts and the first and last positions of each element. After computing the degree, iterate through the map to find the smallest subarray that maintains that degree.

Degree of an Array solution and explanation

The problem

Approach overview

Approach 1: Using HashMap to Track Frequencies and Positions

Approach 2: Two-Pass Array Traversal

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Degree of an Array solution and explanation

The problem

Approach overview

Approach 1: Using HashMap to Track Frequencies and Positions

Approach 2: Two-Pass Array Traversal

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems