1
\$\begingroup\$

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array.

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;
        }
        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];
            }
        }
        boolean startIndexFound = false, endIndexFound = false;
        int startIndex = 0, endIndex = 0;
        for (int i = 0; i < degreeArr.length; i++) {
            if (startIndexFound && endIndexFound)
                break;
            if (!startIndexFound && degreeArr[i] == 1) {
                startIndex = i;
                startIndexFound = true;
            }
            if (!endIndexFound && degreeArr[i] == entry.getValue()) {
                endIndex = i;
                endIndexFound = true;
            }
        }
        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} .

Can this problem be solved in better runtime and space complexity ? Also It would be good if someone can review my approach and solution

\$\endgroup\$
  • \$\begingroup\$ Can you also post the link to the challenge? \$\endgroup\$ – RobAu Oct 4 '17 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.