697. Degree of an Array

Level

Easy

Description

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: [1, 2, 2, 3, 1]

Output: 2

**Explanation: **

The input array has a degree of 2 because both elements 1 and 2 appear twice.

Of the subarrays that have the same degree:

[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2]

Output: 6

Note:

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

Solution

First get each number’s frequency in array nums. Next obtain the numbers with the maximum frequency. Then for each number with the maximum frequency, obtain the first occurrence minIndex and the last occurrence maxIndex of the number, and the subarray with this number has length maxIndex - minIndex + 1. Finally, return the minimum possible length among the subarrays of each number with maximum frequency.

public class Degree_of_an_Array {

    public static void main(String[] args) {
        Degree_of_an_Array out = new Degree_of_an_Array();
        Solution s = out.new Solution();

        System.out.println(s.findShortestSubArray(new int[]{1,2,2,3,1}));
    }

    // time: O(N)
    // space: O(N)
    class Solution {
        public int findShortestSubArray(int[] nums) {

            if (nums == null || nums.length == 0) {
                return 0;
            }

            Map<Integer, Integer> firstIndex = new HashMap<>();
            Map<Integer, Integer> lastIndex = new HashMap<>();
            Map<Integer, Integer> count = new HashMap<>();

            for (int i = 0; i < nums.length; i++) {
                int x = nums[i];
                firstIndex.putIfAbsent(x, i); // only update first time
                lastIndex.put(x, i);
                count.put(x, count.getOrDefault(x, 0) + 1);
            }

            int result = nums.length;
            int degree = Collections.max(count.values());
            for (int x: count.keySet()) {
                if (count.get(x) == degree) {
                    result = Math.min(result, lastIndex.get(x) - firstIndex.get(x) + 1);
                }
            }
            return result;
        }
    }
}

Java

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
        int maxFrequency = 0;
        for (int num : nums) {
            int frequency = frequencyMap.getOrDefault(num, 0);
            frequency++;
            maxFrequency = Math.max(maxFrequency, frequency);
            frequencyMap.put(num, frequency);
        }
        Set<Integer> maxFrequencySet = new HashSet<Integer>();
        Set<Integer> keySet = frequencyMap.keySet();
        for (int num : keySet) {
            int frequency = frequencyMap.getOrDefault(num, 0);
            if (frequency == maxFrequency)
                maxFrequencySet.add(num);
        }
        Map<Integer, List<Integer>> numIndicesMap = new HashMap<Integer, List<Integer>>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (maxFrequencySet.contains(num)) {
                List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>());
                indices.add(i);
                numIndicesMap.put(num, indices);
            }
        }
        int minLength = length;
        for (int num : maxFrequencySet) {
            List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>());
            int size = indices.size();
            if (size > 0) {
                int minIndex = indices.get(0), maxIndex = indices.get(size - 1);
                minLength = Math.min(minLength, maxIndex - minIndex + 1);
            }
        }
        return minLength;
    }
}

All Problems

All Solutions