# Degree of an Array

• This post is deleted!

• This post is deleted!

• i think it's much better to use a hashmap<Integer, List<Integer>>, where value of map store all the indexes of current num, the size of list appears to be the frequency.
and the list.get(list.size()-1) - list.get(0) appear to be the length

• This post is deleted!

• Can I get the solutions of weekly contests in C++ too ?

• This post is deleted!

• This post is deleted!

• Here I add the scala implementation with same approach:
'
def findShortestSubArray(nums: Array[Int]): Int = {
var leftmap = MapInt, Int
var rightmap = MapInt, Int
var countmap = MapInt, Int

``````    var i: Int = 0
for (i <- 0 until nums.length) {
val num = nums(i)
if (!leftmap.contains(num)) leftmap += (num -> i)
rightmap += (num -> i)
countmap += (num -> (countmap.getOrElse(num, 0) + 1))
}

var minlen = nums.length
val degree = countmap.values.toList.max

countmap.foreach {
case (k, v) => if (v == degree) minlen = Math.min(minlen, rightmap(k) - leftmap(k) + 1)
}

minlen
}
``````

'

• in JavaScript, with only one map used:
var findShortestSubArray = function(nums) {
var m = new Map(),
degree = 1,
whichDegree = nums[0]
for (var i = 0; i < nums.length; i++) {
if (m.has(nums[i])) {
var pos = m.get(nums[i])
pos.push(i)
if (pos.length > degree) {
degree = pos.length
whichDegree = nums[i]
} else if (pos.length == degree && pos[pos.length - 1] - pos[0] < m.get(whichDegree)[m.get(whichDegree).length - 1] - m.get(whichDegree)[0]) {
degree = pos.length
whichDegree = nums[i]
}
} else m.set(nums[i], [i])
}
return m.get(whichDegree)[m.get(whichDegree).length - 1] - m.get(whichDegree)[0] + 1
};

• 16 ms C Solution

typedef struct hashmap{
int freq;
int loc[2];
}hash_m;

int findShortestSubArray(int* nums, int numsSize) {
hash_m hash[50000]={0};
int max=0,val;
for(int i=0;i<numsSize;i++){
if(hash[nums[i]].freq == 0){
hash[nums[i]].loc[0]=i;
hash[nums[i]].loc[1]=i;
}
else{
hash[nums[i]].loc[1]=i;
}
hash[nums[i]].freq++;
}

``````for(int i=0;i<numsSize;i++){
if(max < hash[nums[i]].freq){
max = hash[nums[i]].freq;
val = hash[nums[i]].loc[1] - hash[nums[i]].loc[0];
}
else if(max == hash[nums[i]].freq){
if((hash[nums[i]].loc[1] - hash[nums[i]].loc[0]) < val)
val = hash[nums[i]].loc[1] - hash[nums[i]].loc[0];
}
}

return  val+1;
``````

}

• class Solution:
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
degree = 1
item = nums[0]
mydic={}
indexend = 0
if len(nums) == 1:
return 1
for i in range(0,len(nums)):
if nums[i] in mydic:
mydic[nums[i]][0] = mydic[nums[i]][0] + 1
if mydic[nums[i]][0] > degree:
degree = mydic[nums[i]][0]
item = nums[i]
indexend = i
elif mydic[nums[i]][0] == degree:
if (i-mydic[nums[i]][1]+1) <(indexend-mydic[item][1]+1):
item = nums[i]
indexend = i
else:
mydic[nums[i]]=[1,i]

``    return (indexend - mydic[item][1])+1``

• class Solution {
public int findShortestSubArray(int[] nums) {

``````    Map<Integer, NumInfo> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
NumInfo info = map.getOrDefault(nums[i], new NumInfo(nums[i]));
if (info.first == -1) {
info.first = i;
}
info.last = i;
info.count++;
map.put(nums[i], info);
}

PriorityQueue<NumInfo> queue = new PriorityQueue<>(new Comparator<NumInfo>() {

@Override
public int compare(NumInfo o1, NumInfo o2) {
if (o1.count > o2.count)
return -1;

if (o1.count < o2.count)
return 1;

if (o1.last-o1.first < o2.last-o2.first)
return -1;
else
return 1;
}
});

for (int n : map.keySet()) {
}

NumInfo obj = queue.poll();
return obj.last-obj.first+1;
}

private class NumInfo {
int num ;

public NumInfo(int num) {
this.num = num;
}
int first = -1;
int last = -1;
int count = 0;
}
``````

}

• Here is a one pass solution (only scans the array once and no need to scan the map again)
in the map keep the current count of the Integer and the position once it was first seen, when see a new int during the scan, fetch the record of the current Int, and add the occurrence , if the occurrence is lesser than the global max, do nothing. If the occurrence equals to the global max, update the len if needed with the current numbers' current seen - first seen position +1. If the occurrence is larger than the global max, replace the global max with the local max and update the len with the current len reading. (Beat 80% Java)

public int findShortestSubArray(int[] nums) {
Map<Integer,Integer[]> lookup = new HashMap<>();
int degree = 0 ;
int len = Integer.MAX_VALUE;
for (int idx = 0 ; idx < nums.length; idx ++) {
Integer[] res = lookup.get(nums[idx]);
if (res == null) {
res = new Integer[] {1, idx} ;
}
res[0] ++;
if (res[0] >=degree) {
if (res[0] > degree) {
degree = res[0];
len = idx - res[1] +1;
} else {
len = Math.min(len, idx-res[1] +1);
}
}

``````        lookup.put(nums[idx], res);

}
return len;
}``````

• #ruby #codegolf

Short Version:

``````a.each.with_object({}).with_index{|(i,h),x|h[i]=(h[i]||[])<<x}.values.map{|a|[a.size,a[-1]-a[0]]}.sort{|a,b|[a[0],b[-1]]<=>[b[0],a[-1]]}[-1][-1]+1
``````

``````  h = Hash.new { |h,k| h[k] = [] }