One pass Java solution using HashMap, O(N)


  • 0
    C

    Use the HashMap to store {degree, firstIndex, lastIndex} for a value.

    public int findShortestSubArray(int[] nums) {
    
            //the value of the map is a array with three elements {degree, firstIndex, lastIndex}
            Map<Integer, int[]> mp = new HashMap<Integer, int[]>();
            int deg = 1;
            int mnlen = 1;
            for (int i = 0; i < nums.length; i++) {
                if (mp.containsKey(nums[i])) {
                    int[] idx = mp.get(nums[i]);
                    idx[0] += 1; //update the degree of current element
                    idx[2] = i;  //update the lastIndex of current element
                    if (idx[0] > deg) { //if current degree is the biggest
                        mnlen = idx[2] - idx[1] + 1;
                        deg = idx[0];
                    }else if(idx[0] == deg) { //if current degree equeals to biggest degree, find the min len
                        mnlen = Math.min(mnlen, idx[2] - idx[1] + 1);
                    }
                }else {
                    mp.put(nums[i], new int[] {1, i, i});
                }
            }       
        return mnlen;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.