How to divide array to subarrays with the least sum

Question

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.

Examples

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?

Answer 1

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):
    freqs = dict.fromkeys(arr,0)             # frequency counters for range
    result = []
    for i,n in enumerate(arr,1):             # once through the list
        freqs[n] += 1                        # add to frequencies
        if i>m:  freqs[arr[i-m-1]] -= 1      # remove element going out
        if i>=m: result.append(max(freqs.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]

Time complexity: O(NxM), space: O(N), where N is the size of the list, and M is the the length of the subarray window

Answer 2

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.

Ruby code

def f(arr, m)
    # Initialize everything
    elt_to_frequency = Hash.new {|h, elt| h[elt] = 0} #Rubyism: new elts default to zero
    frequency_to_count = Hash.new {|h, freq| h[freq] = 0}
    max_frequency = 0
    i = j = -1 # left & right indices
    ans = []
    0.upto(m-1) do |j|
        elt = arr[j]
        add_elt(elt, elt_to_frequency, frequency_to_count)
        max_frequency = [max_frequency, frequency_to_count[elt]].max
    end
    ans << max_frequency
    
    # Now slide the window & make updates. The window is [i, j] inclusive
    m.upto(arr.size - 1) do |j|
        i = j - m + 1
        new_elt = arr[j]
        old_elt = arr[i-1]
        add_elt(new_elt, elt_to_frequency, frequency_to_count)
        subtract_elt(old_elt, elt_to_frequency, frequency_to_count)
        if elt_to_frequency[new_elt] > max_frequency
            max_frequency = elt_to_frequency[new_elt]
        elsif frequency_to_count[max_frequency] == 0
            max_frequency -= 1
        end
        ans << max_frequency
    end
    return ans
end

def add_elt(elt, elt_to_frequency, frequency_to_count)
    elt_to_frequency[elt] += 1
    new_freq = elt_to_frequency[elt]
    frequency_to_count[new_freq] += 1
    frequency_to_count[new_freq - 1] -= 1 # We'll have a negative count for 0 but dont' care
end

def subtract_elt(elt, elt_to_frequency, frequency_to_count)
    elt_to_frequency[elt] -= 1
    new_freq = elt_to_frequency[elt]
    frequency_to_count[new_freq] += 1
    frequency_to_count[new_freq + 1] -= 1 
end

Results

f([2,1,2,3,3,2,2,2,2,1], 3)
=> [2, 1, 2, 2, 2, 3, 3, 2]

Answer 3

Method 1:

1. Create a window of size m.
2. Store frequencies of all elements in the window.
3. Find max frequency value.
4. Move window forward until we reach end of the array.

Time Complexity : O(N²)
Space Complexity : O(N)

    public static int[] occurrencesInSubarrays(int[] arr, int m) {
        int n = arr.length;
        int[] ans = new int[n - m + 1];
        int k = 0;
    
        HashMap<Integer, Integer> freq = new HashMap<>();
        // storing frequencies of each element
        for (int i = 0; i < m; i++)
            freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
    
        for (int i = m; i < n; i++) {
            // find maximum frequency(value) in the hashmap 
            for (int val : freq.values()) {
                ans[i - m] = Math.max(ans[i - m], val);
            }
            // remove element outside of current window
            freq.put(arr[i - m], freq.getOrDefault(arr[i - m], 0) - 1);
            // add new number in the window
            freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
        }
        // again store frequency for last window
        for (int val : freq.values()) {
                ans[n - m] = Math.max(ans[n - m], val);
        }
        return ans;
    }