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.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: nums
    integer :: i, j, k, l, m, n_subarrays, min_len

    ! Example 1
    nums(1) = 1
    nums(2) = 2
    nums(3) = 2
    nums(4) = 3
    nums(5) = 1
    call solve(nums, n, min_len)
    write (*, '(A, I0)') 'Example 1: ', min_len

    ! Example 2
    nums(1) = 1
    nums(2) = 2
    nums(3) = 2
    nums(4) = 3
    nums(5) = 1
    nums(6) = 4
    nums(7) = 2
    call solve(nums, n, min_len)
    write (*, '(A, I0)') 'Example 2: ', min_len

contains

    subroutine solve(nums, n, min_len)
        implicit none
        integer, intent(in) :: n
        integer, dimension(n), intent(in) :: nums
        integer, intent(out) :: min_len
        integer :: i, j, k, l, m, n_subarrays, degree
        logical :: found

        ! Initialize variables
        min_len = -1
        found = .false.

        ! Iterate over all subarrays
        do i = 1, n
            do j = i, n
                ! Calculate degree of current subarray
                degree = 0
                do k = i, j
                    if (nums(k) > degree) then
                        degree = nums(k)
                    end if
                end do

                ! Check if degree matches
                if (degree == nums(j)) then
                    ! Check if this is the shortest subarray so far
                    if (.not. found .or. j - i + 1 < min_len) then
                        min_len = j - i + 1
                        found = .true.
                    end if
                end if
            end do
        end do

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module smallest_subarray_with_same_degree

implicit none

contains

function smallest_subarray_with_same_degree(nums) result(min_length)
    integer, intent(in) :: nums(:)
    integer :: min_length, degree, count, i, j

    ! Find the degree of the array
    degree = 0
    do i = 1, size(nums)
        count = 0
        do j = 1, size(nums)
            if (nums(i) == nums(j)) then
                count = count + 1
            end if
        end do
        if (count > degree) then
            degree = count
        end if
    end do

    ! Find the smallest subarray with the same degree
    min_length = size(nums) + 1
    do i = 1, size(nums)
        count = 0
        do j = i, size(nums)
            if (nums(i) == nums(j)) then
                count = count + 1
            end if
            if (count == degree) then
                if (j - i + 1 < min_length) then
                    min_length = j - i + 1
                end if
                exit
            end if
        end do
    end do

end function smallest_subarray_with_same_degree

end module smallest_subarray_with_same_degree

program test_smallest_subarray_with_same_degree
    use smallest_subarray_with_same_degree
    implicit none

    integer, parameter :: nums1(5) = [1, 2, 2, 3, 1]
    integer, parameter :: nums2(7) = [1, 2, 2, 3, 1, 4, 2]
    integer, parameter :: nums3(3) = [1, 2, 2]
    integer, parameter :: nums4(4) = [1, 2, 2, 3]
    integer, parameter :: nums5(6) = [1, 2, 2, 3, 1, 4]

    write (*,*) smallest_subarray_with_same_degree(nums1)
    write (*,*) smallest_subarray_with_same_degree(nums2)
    write (*,*) smallest_subarray_with_same_degree(nums3)
    write (*,*) smallest_subarray_with_same_degree(nums4)
    write (*,*) smallest_subarray_with_same_degree(nums5)

end program test_smallest_subarray_with_same_degree
🌐 Data from online sources 
def findShortestSubArray(nums):
    freq_map, start_map = {}, {}
    max_freq, min_length = 0, len(nums)

    for i, num in enumerate(nums):
        if num not in start_map:
            start_map[num] = i
        freq_map[num] = freq_map.get(num, 0) + 1

        freq = freq_map[num]
        if freq > max_freq:
            max_freq = freq
            min_length = i - start_map[num] + 1
        elif freq == max_freq:
            min_length = min(min_length, i - start_map[num] + 1)

    return min_length

The algorithm first initializes two hash maps: freq_map to store the frequency count of each element and start_map to store the starting index of each unique element in the array. The max frequency max_freq and the minimum length min_length are initialized to 0 and the length of the input array, respectively.

Then, iterate through the input array, updating the frequency count of each element in freq_map and storing the starting index of each unique element in start_map.

For each index, update max_freq if a higher frequency is found. If the frequency is equal to max_freq, update min_length with the minimum length of the subarray having same degree as nums.

Finally, the algorithm returns the smallest length of a subarray with the maximum frequency. This approach has a time complexity of O(n), where n is the length of the input array.

🌐 Data from online sources 
#include <unordered_map>
#include <vector>

int findShortestSubArray(std::vector<int>& nums) {
    std::unordered_map<int, int> freq_map, start_map;
    int max_freq = 0, min_length = nums.size();

    for (int i = 0; i < nums.size(); ++i) {
        if (start_map.count(nums[i]) == 0) {
            start_map[nums[i]] = i;
        }
        freq_map[nums[i]]++;

        int freq = freq_map[nums[i]];
        if (freq > max_freq) {
            max_freq = freq;
            min_length = i - start_map[nums[i]] + 1;
        } else if (freq == max_freq) {
            min_length = std::min(min_length, i - start_map[nums[i]] + 1);
        }
    }

    return min_length;
}

The algorithm first initializes two hash maps: freq_map to store the frequency count of each element and start_map to store the starting index of each unique element in the array. The max frequency max_freq and the minimum length min_length are initialized to 0 and the length of the input array, respectively.

Then, iterate through the input array, updating the frequency count of each element in freq_map and storing the starting index of each unique element in start_map.

For each index, update max_freq if a higher frequency is found. If the frequency is equal to max_freq, update min_length with the minimum length of the subarray having same degree as nums.

Finally, the algorithm returns the smallest length of a subarray with the maximum frequency. This approach has a time complexity of O(n), where n is the length of the input array.