How to divide array to subarrays with the least sum-CodePudding

Given an array of integers arr and a positive integer m, your task is to find the frequency of the most common element within each contiguous subarray of length m in arr.

Return an array of these highest frequencies among subarray elements, ordered by their corresponding subarray's starting index. You can look at the examples section for a better understanding.

Example

For arr = [1, 2] and m = 2, the output should be occurrencesInSubarrays(arr, m) = [1].

example 1

arr contains only one contiguous subarray of length m = 2 - arr[0..1] = [1, 2]. This subarray contains 2 most frequent elements - 1 and 2, both having a frequency of 1. So, the answer is [1].

For arr = [1, 3, 2, 2, 3] and m = 4, the output should be occurrencesInSubarrays(arr, m) = [2, 2].

example 2

arr contains two contiguous subarrays of length m = 4:

arr[0..3] = [1, 3, 2, 2] contains only one most frequent element - 2, and its frequency is 2. arr[1..4] = [3, 2, 2, 3] contains two most frequent elements - 2 and 3, both of them have a frequency of 2. Putting the answers for both subarrays together, we obtain the array [2, 2] For arr = [2, 1, 2, 3, 3, 2, 2, 2, 2, 1] and m = 3, the output should be occurrencesInSubarrays(arr, m) = [2, 1, 2, 2, 2, 3, 3, 2].

example 3

arr contains 8 contiguous subarrays of length m = 3:

arr[0..2] = [2, 1, 2] contains only one most frequent element - 2, and its frequency is 2.
arr[1..3] = [1, 2, 3] contains three most frequent elements - 1, 2, and 3. All of them have frequency 1.
arr[2..4] = [2, 3, 3] contains only one most frequent element - 3, and its frequency is 2.
arr[3..5] = [3, 3, 2] contains only one most frequent element - 3, and its frequency is 2.
arr[4..6] = [3, 2, 2] contains only one most frequent element - 2, and its frequency is 2.
arr[5..7] = [2, 2, 2] contains only one most frequent element - 2, and its frequency is 3.
arr[6..8] = [2, 2, 2] contains only one most frequent element - 2, and its frequency is 3.
arr[7..9] = [2, 2, 1] contains only one most frequent element - 1, and its frequency is 2.

Putting the answers for both subarrays together, we obtain the array [2, 1, 2, 2, 2, 3, 3, 2].

My approach is by using two Hashmaps. One as a queue for each row and one holds the sum of each row. But it is still buggy. Can anyone have any idea to solve this?

CodePudding user response：

Use two maps: elt_to_frequency, frequency_to_count. The former keeps track of the frequency of every element in the sliding window, the latter the count of every frequency.

Update both in the obvious way each time the sliding window moves.

Also keep track of max_frequency. Increment this to the new max_frequency if elt_to_frequency is ever bigger than it. On the other hand, if frequency_to_count[max_frequency] drops to zero then the new max_frequency is one less than the old max_frequency.

Linear time, linear space.

Is that clear?

CodePudding user response：

You can use a dictionary to keep track of the frequencies for the last m elements adding elements as you progress forward while subtracting the element that is m indexes behind.

def maxFreqs(arr,m):
    counts = dict.fromkeys(arr,0)          # frequency counters for range
    result = []
    for i,n in enumerate(arr,1):
        counts[n]  = 1                     # add to frequencies
        if i>m:  counts[arr[i-m-1]] -= 1   # subtract element going out
        if i>=m: result.append(max(counts.values())) # output max frequencies
    return result

print(maxFreqs([2, 1, 2, 3, 3, 2, 2, 2, 2, 1], 3 ))
[2, 1, 2, 2, 2, 3, 3, 2]