Find the length of minimum sub array with maximum degree in an array

Question

I tried solving a problem in hackerrank which is to find the length of minimum sub array with maximum degree in an array. The maximum degree of an array is the count of element with maximum frequency. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array length is 4 as 2 has the maximum degree and the smallest sub array which has degree 3 is {2, 2, 1, 2}

Below is my solution for the problem

public class FindingMinSubArrayWithDegree {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(degreeOfArray(arr));
        sc.close();
    }

    static int degreeOfArray(int[] arr) {
        HashMap<Integer, Integer> numbersByDegree = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i++) {
            int degree = numbersByDegree.getOrDefault(arr[i], 0);
            numbersByDegree.put(arr[i], degree + 1);
        }
        List<Map.Entry<Integer, Integer>> sortedEntries = sortByValue(numbersByDegree);
        int maxDegree = sortedEntries.get(0).getValue();

        int[] degreeArr = new int[arr.length] ;
        int minSubArrayLength = arr.length;
        for (Map.Entry<Integer, Integer> entry : sortedEntries) {
            if (entry.getValue() < maxDegree) {
                break;
            }
            boolean startIndexFound = false, endIndexFound = false;
            int startIndex = 0, endIndex = 0;
            for (int i = 0; i < arr.length; i++) {
                if (entry.getKey() == arr[i]) {
                    if (i - 1 >= 0)
                        degreeArr[i] = degreeArr[i - 1] + 1;
                    else
                        degreeArr[i] = 1;
                } else {
                    if (i - 1 >= 0)
                        degreeArr[i] = degreeArr[i - 1];
                }
                if (!startIndexFound && degreeArr[i] == 1) {
                    startIndex = i;
                    startIndexFound = true;
                }
                if (!endIndexFound && degreeArr[i] == entry.getValue()) {
                    endIndex = i;
                    endIndexFound = true;
                }
                if (startIndexFound && endIndexFound)
                    break;
            }
            startIndexFound = false; endIndexFound = false;
            if ((endIndex - startIndex) < minSubArrayLength) {
                minSubArrayLength = endIndex - startIndex;
            }
            for (int i = 0; i < degreeArr.length; i++)
                degreeArr[i] = 0;
        }
        return minSubArrayLength + 1;
    }

    private static <K, V extends Comparable<? super V>> List<Map.Entry<K, V>> 
    sortByValue(Map<K, V> map) {
        List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
        Collections.sort( list, new Comparator<Map.Entry<K, V>>() {
            public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
                return (o2.getValue()).compareTo( o1.getValue() );
            }
        });
        return list;
    }
}

This approach has a worst case running time of O(N ^ 2) for inputs like { 1, 1, 2, 2, 3, 3, 4, 4} . Is there a better algorithm for this problem ?

PS - I tried asking this question in code review but didn't get any response that is why moved here

Solution 1

To find the degree of an array, we just need to keep track of the frequency of each distinct element in the array, and those elements that have the highest frequencies will be the degree.

So, to find the sub-array with the maximum degree, we only need to care about the subarray that contains the element that have the maximum counts, which means all the sub array with [start , end] is the start and end occurrence of that element.

Thus, what we need to do is keeping track of frequency, start and end position of each element.

Pseudo code:

int max = 0;
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, Integer> startIndex = new HashMap<>();
Map<Integer, Integer> endIndex = new HashMap<>();
for(int i = 0; i < data.length; i++){
   int value = data[i];
   if(map.containsKey(value)){
      map.put(value, map.get(value) + 1);
   }else{
      startIndex.put(value, i);
      map.put(value, 1);
   }
   endIndex.put(value, i);
   max = Integer.max(max, map.get(value));//Calculate the degree of the array
}
int result = data.length;
for(int i : map.keySet()){
   if(map.get(i) == max){
      int len = endIndex.get(i) - startIndex.get(i) + 1;
      result = Integer.min(result, len);
   }
}
return result;

Time complexity is O(n)

Solution 2

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.

We will create 3 HashMap .

• remember the frequency of Each Element -- HashMap Count
• index of 1st occurrence of Each Element -- HashMap left
• index of Last occurrence of Each Element -- HashMap Right.

Then we Will iterate through Count(HashMap) and compare for max frequency, if Equal to max frequency then We will find The length of a (contiguous) subarray.

CODE :-

class Solution {
public int findShortestSubArray(int[] nums) {
    int n = nums.length;
    int degree = 0;
    HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();
    HashMap<Integer,Integer> left = new HashMap<Integer,Integer>();
    HashMap<Integer,Integer> right = new HashMap<Integer,Integer>();
    for(int i = 0;i<n;i++){
        count.put(nums[i],count.getOrDefault(nums[i],0)+1);
        if(!left.containsKey(nums[i]))left.put(nums[i],i);
        right.put(nums[i],i);
        degree = Math.max(degree,count.get(nums[i]));
    }
    int len ;
    int result = n;
    for(int c : count.keySet()){
        if(count.get(c)==degree){
            len = right.get(c)-left.get(c)+1;
            if(len < result)
                result = len;
        }

    }
    return result;

}

}

Time Complexcity O(N) Space Complexcity O(N)

Solution 3

JavaScript Solution:

function findShortestSubArray(nums) {

  // Elements is a map of key => elementInfo
  // with key being each of the elements in the array
  // and elementInfo being the object with properties count, leftIndex, rightIndex for 
  // one particular element in the array

  let degree = 0
  const elementsInfoHighestCount = new Map()
  let subArray = []

  const elements = nums.reduce((acc, num, index) => {
    let count
    let leftIndex
    let rightIndex

    if (acc.has(num)) {
      const existing = acc.get(num)
      count = existing.count + 1
      leftIndex = existing.leftIndex
      rightIndex = index

    } else {
      count = 1
      leftIndex = index
      rightIndex = index
    }

    return acc.set(num, { count, leftIndex, rightIndex })
  }, new Map())


  // Determine the degree by looping through elements map
  elements.forEach((element, uniqueNum) => {
    if (element.count === degree) {
      elementsInfoHighestCount.set(uniqueNum, element)
    } else if (element.count > degree) {
      elementsInfoHighestCount.clear()
      elementsInfoHighestCount.set(uniqueNum, element)
      degree = element.count
    }
  })

  // Get the shortest subarray array by looping through the elementInfoHighestCount map
  let result = elementsInfoHighestCount.values().next().value
  if (elementsInfoHighestCount.size === 1) {
    subArray = nums.slice(result.leftIndex, result.rightIndex + 1)
  } else if (elementsInfoHighestCount.size > 1) {
    elementsInfoHighestCount.forEach((element, num) => {

      const thisElementDiff = element.rightIndex - element.leftIndex
      const previousElementDiff = result.rightIndex - result.leftIndex

      if (thisElementDiff - previousElementDiff < 0) {
        result = elementsInfoHighestCount.get(num)
      }
    })

    subArray = nums.slice(result.leftIndex, result.rightIndex + 1)
  }

  return subArray.length
};

// Time complexity: O(N)

// Testcases - [1, 2, 2, 3, 1], [1,2,2,3,1,4,2]

Comments

[Pham Trung]

What is degree of an array?

[Aarish Ramesh]

The degree of an array is the count of element with maximum frequency