The number of subarrays with the same "degree" as an array

Question

So, this problem was asked in a quiz, and the problem is this:

You are given an array "a" with elements in the range from 1 to 10 ⁶ and the size of the array can be no more than 10 ⁵ . Now we are asked to find the number of subarrays with the same “degree” as the original array. The degree of the array is defined as the frequency of the maximum occurring element in the array. Several elements may have the same frequency.

I was stuck in this problem for an hour, but could not come up with any solution. How to solve it?

Input Example:

first-input 1,2,2,3,1 first-output 2 second-input 1,1,2,1,2,2 second-output 4 

Answer 1

The most commonly used item is called mode; this problem defines degree as frequency. Your tasks:

Define all mode values. For each mode value, find the index range of that value. For example, in an array

 [1, 1, 2, 1, 3, 3, 2, 4, 2, 4, 5, 5, 5] 

You have three modes (1 2 5) with degree 3. Index ranges

 1 - 0:3 2 - 2:8 5 - 10:12 

You need to count all index ranges (subarrays) that include at least one of these three ranges.

I applied this example to have both the main cases: modes that overlap, and those that do not. Note that containment is controversial: if you have an array in which one range of modes contains another:

[0, 1, 1, 1, 0, 0]

You can completely ignore the external: any subarray containing 0 will also contain 1 .

ANALYSIS

A subarray is defined by two numbers, starting and ending indices. Since we must have 0 <= start <= end <= len (array), this is a handshake problem between the boundaries of the array. We have N (N + 1) / 2 possible subarrays.

For 10 ** 5 elements, you can simply reinstall the problem here: for each pair of indices, check if this range contains any of the mode ranges. However, you can easily shorten this with interval recognition.

ALGORITHM

Go through the ranges of modes, from left to right. First, count all subranges that include the first mode range [0: 3]. Only 1 start [0] and 10 possible ends [3:12] are possible; that is 10 subarrays.

Now go to the second range of modes [2: 8]. You need to count the subarrays that include this, but exclude the ones you have already counted. Since there is overlap, you need a starting point later than 0 or an ending point to 3. This second sentence is not possible with a given range.

So you count start [1: 2], end [8:12]. This is another 2 * 5 subarrays.

For the third range [10:12 (without overlapping) you need a starting point that does not include any other subrange. This means that any starting point [3:10] will be completed. Since there is only one possible endpoint, you have 8 * 1 or 8 additional subarrays.

Can you turn this into something formal?

Answer 2

Referring to the lit code https://leetcode.com/problems/degree-of-an-array/solution/ solutions

  class Solution { public int findShortestSubArray(int[] nums) { Map<Integer, Integer> left = new HashMap(), right = new HashMap(), count = new HashMap(); for (int i = 0; i < nums.length; i++) { int x = nums[i]; if (left.get(x) == null) left.put(x, i); right.put(x, i); count.put(x, count.getOrDefault(x, 0) + 1); } int ans = nums.length; int degree = Collections.max(count.values()); for (int x: count.keySet()) { if (count.get(x) == degree) { ans = Math.min(ans, right.get(x) - left.get(x) + 1); } } return ans; } }