## Introduction

In this article, we will examine the Degree of an Array problem on Leetcode in detail, break it down into understandable fragments, and solve it using Python.

## Problem Statement

Here is the problem statement of “Degree of an Array”:

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`

.

## Understanding the Problem

First, let’s try to understand the problem statement. The degree of an array is defined as the maximum frequency of any one of its elements. This means we need to find the most occurring number in the array.

The challenge is to find the smallest subarray that has the same degree as the original array. This means we need to find the shortest range within the array where the most occurring number appears the same number of times as it does in the entire array.

## A Simple Approach – Brute Force

A brute force approach would be to check all subarrays, calculate their degree, and keep track of the shortest subarray that matches the degree of the whole array.

However, this approach is time-consuming and inefficient. Its time complexity would be O(n^3), which is unacceptable for large inputs.

Let’s break down why it is O(n^3). We have two nested loops to generate subarrays, which gives us O(n^2). Then, for each subarray, we are calculating the degree, which, in the worst case, can take O(n) time. Hence, the total time complexity is O(n^3).

Given the above considerations, it’s clear we need to use a more optimized approach to solve this problem.

## Optimized Approach – Using Hash Maps

An optimized approach to solve this problem would be using Hash Maps (also known as dictionaries in Python). We can solve this problem in linear time, i.e., O(n), where n is the size of the array.

### Breaking down the Problem

Let’s break down our problem into sub-problems that we can solve individually:

- Find the frequency of each number (degree of the array)
- Find the first occurrence of each number
- Find the last occurrence of each number

The length of the smallest subarray would be ‘last occurrence – first occurrence + 1’ of a number with the maximum frequency.

```
def findShortestSubArray(nums):
first, counter, res, degree = {}, {}, 0, 0
for i, num in enumerate(nums):
first.setdefault(num, i) # set first[num] = i if num not in first
counter[num] = counter.get(num, 0) + 1 # increment counter[num]
if counter[num] > degree:
degree = counter[num]
res = i - first[num] + 1
elif counter[num] == degree:
res = min(res, i - first[num] + 1)
return res
```

In the above solution:

- We first initialize an empty dictionary
`first`

to store the first occurrence of each number,`counter`

to store the count of each number,`res`

to store the result, and`degree`

to store the maximum count. - We then iterate over
`nums`

using`enumerate()`

to get both the index`i`

and the number`num`

. - For each number, we use
`setdefault()`

to record the first occurrence index if it’s not already recorded. - We use
`get()`

to get the current count of`num`

in`counter`

and increment it by 1. If`num`

does not exist in`counter`

,`get()`

returns 0. - If the count of
`num`

is greater than`degree`

, we update`degree`

and`res`

. - If the count of
`num`

is equal to`degree`

, we update`res`

with the minimum length.

## Time and Space Complexity Analysis

The time complexity of this solution is O(n) because we’re doing a single pass through `nums`

. The space complexity is also O(n) because, in the worst case, we might store each unique number of `nums`

in `first`

and `counter`

.

## Conclusion

To conclude, the “Degree of an Array” problem is a classic example where understanding the problem’s constraints and requirements is crucial for developing an optimal solution. Although a brute force solution can solve the problem, it’s time-consuming and inefficient. An optimized approach using hash maps, as shown above, can solve the problem more efficiently.