This can be done in O(n) time

I was intrigued by this problem in part because, as I indicated in the comments, I felt certain that it could be done in O(n) time. I had some time over this past weekend, so I wrote up my solution to this problem.

Approach: Mode Frequencies

This means that whenever you add a number to the collection, if the number added was not already one of the mode-values then the frequency of the mode would not change. So with the collection (8 9 9) the mode-values are {9} and the mode-frequency is 2. If you add say a 5 to this collection ((8 9 9 5)) neither the mode-frequency nor the mode-values change. If instead you add an 8 to the collection ((8 9 9 8)) then the mode-values change to {9, 8} but the mode-frequency is still unchanged at 2. Finally, if you instead added a 9 to the collection ((8 9 9 9)), now the mode-frequency goes up by one.

Thus in all cases when you add a single number to the collection, the mode-frequency is either unchanged or goes up by only one. Likewise, when you remove a single number from the collection, the mode-frequency is either unchanged or goes down by at most one. So all incremental changes to the collection result in only two possible new mode-frequencies. This means that if we had all of the distinct numbers of the collection indexed by their frequencies, then we could always find the new Mode in a constant amount of time (i.e., O(1)).

To accomplish this I use a custom data structure ("ModeTracker") that has a multiset ("numFreqs") to store the distinct numbers of the collection along with their current frequency in the collection. This is implemented with a Dictionary<int, int> (I think that this is a Map in Java). Thus given a number, we can use this to find its current frequency within the collection in O(1).

This data structure also has an array of sets ("freqNums") that given a specific frequency will return all of the numbers that have that frequency in the current collection.

I have included the code for this data structure class below. Note that this is implemented in C# as I do not know Java well enough to implement it there, but I believe that a Java programmer should have no trouble translating it.

(pseudo)Code:

class ModeTracker
{
    HashSet<int>[] freqNums;        //numbers at each frequency
    Dictionary<int, int> numFreqs;  //frequencies for each number
    int modeFreq_ = 0;              //frequency of the current mode

    public ModeTracker(int maxFrequency)
    {
        freqNums = new HashSet<int>[maxFrequency + 2];
        // populate frequencies, so we dont have to check later
        for (int i=0; i<maxFrequency+1; i++)
        {
            freqNums[i] = new HashSet<int>();
        }

        numFreqs = new Dictionary<int, int>();
    }

    public int Mode { get { return freqNums[modeFreq_].First(); } }

    public void addNumber(int n)
    {
        int newFreq = adjustNumberCount(n, 1);

        // new mode-frequency is one greater or the same 
        if (freqNums[modeFreq_+1].Count > 0) modeFreq_++;
    }

    public void removeNumber(int n)
    {
        int newFreq = adjustNumberCount(n, -1);

        // new mode-frequency is the same or one less
        if (freqNums[modeFreq_].Count == 0)  modeFreq_--;
    }

    int adjustNumberCount(int num, int adjust)
    {
        // make sure we already have this number
        if (!numFreqs.ContainsKey(num))
        {
            // add entries for it
            numFreqs.Add(num, 0);
            freqNums[0].Add(num);
        }

        // now adjust this number's frequency
        int oldFreq = numFreqs[num];
        int newFreq = oldFreq + adjust;
        numFreqs[num] = newFreq;

        // remove old freq for this number and and the new one
        freqNums[oldFreq].Remove(num);
        freqNums[newFreq].Add(num);

        return newFreq;
    }
}

Also, below is a small C# function that demonstrates how to use this datastructure to solve the problem originally posed in the question.

    int[] ModesOfSubarrays(int[] arr, int subLen)
    {
        ModeTracker tracker = new ModeTracker(subLen);
        int[] modes = new int[arr.Length - subLen + 1];

        for (int i=0; i < arr.Length; i++)
        {
            //add every number into the tracker
            tracker.addNumber(arr[i]);

            if (i >= subLen)
            {
                // remove the number that just rotated out of the window
                tracker.removeNumber(arr[i-subLen]);
            }

            if (i >= subLen - 1)
            {
                // add the new Mode to the output
                modes[i - subLen + 1] = tracker.Mode;
            }
        }

        return modes;
    }

I have tested this and it does appear to work correctly for all of my tests.

Complexity Analysis

1. The new ModeTracker object is created in O(n) time or less.
2. The modes[] array is created in O(n) time.
3. The For(..) loops N times: . 3a: the addNumber() function takes O(1) time . 3b: the removeNumber() function takes O(1) time . 3c: getting the new Mode takes O(1) time

So the total time is O(n) + O(n) + n*(O(1) + O(1) + O(1)) = O(n)

Please let me know of any questions that you might have about this code.