697. Degree of an Array LeetCode Solution

In this guide, you will get 697. Degree of an Array LeetCode Solution with the best time and space complexity. The solution to Degree of an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Degree of an Array solution in C++
Degree of an Array solution in Java
Degree of an Array solution in Python
Additional Resources

697. Degree of an Array LeetCode Solution image

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.

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

697. Degree of an Array LeetCode Solution in C++

class Solution {
 public:
  int findShortestSubArray(vector<int>& nums) {
    int ans = 0;
    int degree = 0;
    unordered_map<int, int> debut;
    unordered_map<int, int> count;

    for (int i = 0; i < nums.size(); ++i) {
      const int num = nums[i];
      if (!debut.contains(num))
        debut[num] = i;
      if (++count[num] > degree) {
        degree = count[num];
        ans = i - debut[num] + 1;
      } else if (count[num] == degree) {
        ans = min(ans, i - debut[num] + 1);
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

697. Degree of an Array LeetCode Solution in Java

class Solution {
  public int findShortestSubArray(int[] nums) {
    int ans = 0;
    int degree = 0;
    Map<Integer, Integer> debut = new HashMap<>();
    Map<Integer, Integer> count = new HashMap<>();

    for (int i = 0; i < nums.length; ++i) {
      final int num = nums[i];
      debut.putIfAbsent(num, i);
      if (count.merge(num, 1, Integer::sum) > degree) {
        degree = count.get(num);
        ans = i - debut.get(num) + 1;
      } else if (count.get(num) == degree) {
        ans = Math.min(ans, i - debut.get(num) + 1);
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

697. Degree of an Array LeetCode Solution in Python

class Solution:
  def findShortestSubArray(self, nums: list[int]) -> int:
    ans = 0
    degree = 0
    debut = {}
    count = collections.Counter()

    for i, num in enumerate(nums):
      debut.setdefault(num, i)
      count[num] += 1
      if count[num] > degree:
        degree = count[num]
        ans = i - debut[num] + 1
      elif count[num] == degree:
        ans = min(ans, i - debut[num] + 1)

    return ans
 # code by PROGIEZ