Leetcode – Degree of an Array Solution in Python

Spread the love

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:

  1. Find the frequency of each number (degree of the array)
  2. Find the first occurrence of each number
  3. 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:

  1. 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.
  2. We then iterate over nums using enumerate() to get both the index i and the number num.
  3. For each number, we use setdefault() to record the first occurrence index if it’s not already recorded.
  4. 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.
  5. If the count of num is greater than degree, we update degree and res.
  6. 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.

Leave a Reply