Solution For Degree Of An Array

Problem Statement:
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. To find the smallest possible length of a contiguous subarray with the same degree, we need to find the subarray that contains both 1 and 2. For example, the subarray [2,2,3,1] has a degree of 2 and the length of this subarray is 4. Therefore, the answer is 2, because the subarray [2,2] has the same degree as the input array and is the smallest possible subarray with this property.

Example 2:
Input: nums = [1,2,2,3,1,4,2] Output: 6

Approach:
1) Find the degree of the array, i.e., the maximum frequency of any one of its elements.
2) Create a dictionary freq to store the frequency of each element of the array nums.
3) Iterate through nums and update freq.
4) Create a dictionary firstIdx to store the index of the first occurrence of each element of nums.
5) Create a dictionary lastIdx to store the index of the last occurrence of each element of nums.
6) Initialize minLength to be the length of nums.
7) Iterate through freq, and for each element x and its frequency f:
i) If f is less than the current degree, continue to the next element in freq.
ii) If f is equal to the current degree, compute the length of the subarray that starts at the first occurrence of x and ends at the last occurrence of x.
iii) If the length of this subarray is less than minLength, update minLength.
8) Return minLength.

Solution:

class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
freq = {}
firstIdx = {}
lastIdx = {}
for i in range(len(nums)):
x = nums[i] if x not in freq:
freq[x] = 0
firstIdx[x] = i
freq[x] += 1
lastIdx[x] = i
degree = max(freq.values())
minLength = len(nums)
for x in freq:
if freq[x] < degree:
continue
else:
length = lastIdx[x] – firstIdx[x] + 1
if length < minLength:
minLength = length
return minLength

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for the use of the dictionaries freq, firstIdx and lastIdx.

Step by Step Implementation For Degree Of An Array

class Solution {
    public int findShortestSubArray(int[] nums) {
        // create a map to store the degree of each element
        Map map = new HashMap<>();
        // create a variable to store the degree of the array
        int degree = 0;
        // iterate through the array
        for (int i = 0; i < nums.length; i++) {
            // if the map does not contain the element, add it to the map
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            }
            // if the map contains the element, increment the value associated with the element
            else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            // update the degree if necessary
            if (map.get(nums[i]) > degree) {
                degree = map.get(nums[i]);
            }
        }
        // create a variable to store the shortest subarray length
        int shortest = nums.length;
        // iterate through the map
        for (Map.Entry entry : map.entrySet()) {
            // if the value associated with the element is equal to the degree
            if (entry.getValue() == degree) {
                // update the shortest subarray length if necessary
                int subarrayLength = findSubarrayLength(nums, entry.getKey());
                if (subarrayLength < shortest) {
                    shortest = subarrayLength;
                }
            }
        }
        // return the shortest subarray length
        return shortest;
    }
    
    // helper method to find the length of the shortest subarray containing a given element
    public int findSubarrayLength(int[] nums, int target) {
        // create variables to store the indices of the first and last occurrences of the target element
        int first = -1;
        int last = -1;
        // iterate through the array
        for (int i = 0; i < nums.length; i++) {
            // update the first index if necessary
            if (nums[i] == target && first == -1) {
                first = i;
            }
            // update the last index
            if (nums[i] == target) {
                last = i;
            }
        }
        // return the difference between the last and first indices + 1
        return last - first + 1;
    }
}

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

/**
 * @param {number[]} nums
 * @return {number}
 */
 
 // this is a o(n) solution that uses a hashmap to store the degree of each element
 // and an array to store the indices of the first occurance of each element
var findShortestSubArray = function(nums) {
    let map = {};
    let first = {};
    let degree = 0;
    let res = nums.length;
    
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        if (!(num in map)) {
            map[num] = 1;
            first[num] = i;
        } else {
            map[num]++;
        }
        if (map[num] > degree) {
            degree = map[num];
            res = i - first[num] + 1;
        } else if (map[num] === degree) {
            res = Math.min(res, i - first[num] + 1);
        }
    }
    
    return res;
};

vector findShortestSubArray(vector& nums) {
        int n = nums.size();
        unordered_map left;
        unordered_map right;
        unordered_map count;
        for (int i = 0; i < n; i++) {
            if (left.find(nums[i]) == left.end()) 
                left[nums[i]] = i;
            right[nums[i]] = i;
            count[nums[i]]++;
        }
        int ans = n;
        int degree = 0;
        for (auto x : count) {
            if (x.second == degree)
                ans = min(ans, right[x.first] - left[x.first] + 1);
            if (x.second > degree) {
                degree = x.second;
                ans = right[x.first] - left[x.first] + 1;
            }
        }
        return ans;
    }

public int FindShortestSubArray(int[] nums) { // create a dictionary to store the number of times an element occurs in the array Dictionary numsDict = new Dictionary(); // create a dictionary to store the first index at which an element occurs in the array Dictionary firstIndexDict = new Dictionary(); // iterate through the array for (int i = 0; i < nums.Length; i++) { // if the element is not in the dictionary, add it if (!numsDict.ContainsKey(nums[i])) { numsDict.Add(nums[i], 1); firstIndexDict.Add(nums[i], i); } // if the element is already in the dictionary, increment the count else { numsDict[nums[i]]++; } } // find the element with the highest frequency int maxCount = 0; int maxElement = 0; foreach (var item in numsDict) { if (item.Value > maxCount) { maxCount = item.Value; maxElement = item.Key; } } // return the difference between the last index at which the element occurs and the first index return nums.Length - 1 - firstIndexDict[maxElement]; }