Degree of an Array

• LeetCode: Degree of an Array

• 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.

• Note:

1. nums.length will be between 1 and 50,000.

2. nums[i] will be an integer between 0 and 49,999.

• Examples:

Input: [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.

Input: [1,2,2,3,1,4,2]
Output: 6

• Analysis:

Divide and conquer, use three arrays, which are counts, lIndex, and rIndex.

counts: the number of every every distinct element of the input array nums.

lIndex: the most left index of every distinct element of the input array nums.

rIndex: the most right index of every distinct element of the input array nums.

Find the max(counts[i]) and min(rIndex[i] - lIndex[i] + 1).

• Code - Java:

class Solution {
    public int findShortestSubArray(int[] nums) {
        int[] counts = new int[50000];
        int[] lIndex = new int[50000];
        int[] rIndex = new int[50000];
        int len = nums.length;
        int maxCount = 0;
        for (int i = 0; i < len; i++) {
            if (counts[nums[i]] == 0) {
                lIndex[nums[i]] = i;
            } 
            counts[nums[i]]++;
            rIndex[nums[i]] = i;
            maxCount = Math.max(maxCount, counts[nums[i]]);
        }
        int result = len;
        for (int i = 0; i < 50000; i++) {
            if (counts[i] != maxCount) {
                continue;
            }
            result = Math.min(result, rIndex[i] - lIndex[i] + 1);
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        vector<int> counts(50000, 0);
        vector<int> lIndex(50000, 0);
        vector<int> rIndex(50000, 0);
        int len = nums.size();
        int maxCount = 0;
        for (int i = 0; i < len; i++) {
            if (counts[nums[i]] == 0) {
                lIndex[nums[i]] = i;
            } 
            counts[nums[i]]++;
            rIndex[nums[i]] = i;
            maxCount = max(maxCount, counts[nums[i]]);
        }
        int result = len;
        for (int i = 0; i < 50000; i++) {
            if (counts[i] != maxCount) {
                continue;
            }
            result = min(result, rIndex[i] - lIndex[i] + 1);
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counts = [0 for i in range(50000)]
        lIndex = [0 for i in range(50000)]
        rIndex = [0 for i in range(50000)]
        maxCount = 0
        numsLen = len(nums)
        for i in range(numsLen):
            num = nums[i]
            if counts[num] == 0:
                lIndex[num] = i
            counts[num] += 1
            rIndex[num] = i
            maxCount = max(maxCount, counts[num])
        result = len(nums)
        for i in range(50000):
            if counts[i] != maxCount:
                continue
            result = min(result, rIndex[i] - lIndex[i] + 1)
        return result

• Code - C:

int findShortestSubArray(int* nums, int numsSize) {
    int* counts = (int*)malloc(50000 * sizeof(int));
    int* lIndex = (int*)malloc(50000 * sizeof(int));
    int* rIndex = (int*)malloc(50000 * sizeof(int));
    int maxCount = 0;
    for (int i = 0; i < numsSize; i++) {
        if (counts[nums[i]] == 0) {
            lIndex[nums[i]] = i;
        } 
        counts[nums[i]]++;
        rIndex[nums[i]] = i;
        if (counts[nums[i]] > maxCount) {
            maxCount = counts[nums[i]];
        }
    }
    int result = numsSize;
    for (int i = 0; i < 50000; i++) {
        if (counts[i] != maxCount) {
            continue;
        }
        int temp = rIndex[i] - lIndex[i] + 1;
        result = temp < result ? temp : result;
    }
    return result;
}

• Time Complexity: O(N), N is the length of input array

• Space Complexity: O(M), M is the max length of input array mentioned in problem description