697.degree-of-an-array.md

697. Degree of an Array

Breakdowns

1. How to know the maximum frequency? (maybe multiple)

Count the frequency and update the maximum frequency at the same time.

2. If I know the current number is the maximum frequency, how to calculate the shortest subarray that contains all the current number?

Suppose 8 is the most frequent number in the input array: [..., x, 8, x, x, x, 8, x, 8, x, ...], we need to know the first and last position of 8.

3. If there are multiple numbers which are the most frequent, how can we track the first and last position of each number?

Use a dictionary to store the first and last position of each number.

Hash Table

1. Count the frequency of each number, and update the maximum frequency.
2. Use a dictionary to store the first and last position of each number.
3. Calculate the shortest subarray that contains all the most frequent numbers.

fun findShortestSubArray(nums: IntArray): Int {
    val countMap = HashMap<Int, Int>()
    var maxCount = 0
    val first = HashMap<Int, Int>()
    val last = HashMap<Int, Int>()
    for (i in nums.indices) {
        val num = nums[i]
        val count = (countMap[num] ?: 0) + 1 
        countMap[num] = count
        maxCount = maxOf(maxCount, count)

        if (num !in first) {
            first[num] = i
        }
        last[num] = i
    }

    var ans = nums.size
    for (i in nums.indices) {
        val num = nums[i]
        val count = countMap[num] ?: continue
        if (count == maxCount) {
            ans = minOf(ans, last[num]!! - first[num]!! + 1)
        }
    }
    return ans
}