LeetCode 1825: Finding MK Average Solution

Master LeetCode problem 1825 (Finding MK Average), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1825. Finding MK Average

Hard

Design Queue Heap (Priority Queue)Data Stream Ordered Set

Problem Explanation

Explanation:

To solve this problem, we can use a combination of a queue and a multiset (or two priority queues) to maintain the stream of elements and calculate the MKAverage as required. Here is the basic idea:

Initialize the MKAverage object with the given values of m and k.
Maintain a queue of size m to store the last m elements of the stream.
Maintain a multiset (or two priority queues) to efficiently get the smallest k elements and largest k elements.
When adding a new element, update the queue and the multiset accordingly.
When calculating the MKAverage, if the size of the stream is less than m, return -1. Otherwise, calculate the average of the remaining elements after removing the smallest k and largest k elements.

Time Complexity:

Adding an element: O(log m) to update the multiset.
Calculating the MKAverage: O(k log m) to remove smallest and largest k elements.

Space Complexity:

O(m) for the queue to store the last m elements.
O(m) for the multiset storing the last m elements.

Solution Code

import java.util.*;

class MKAverage {
    int m, k;
    Queue<Integer> queue;
    TreeSet<Integer> small, large;
    long sum;

    public MKAverage(int m, int k) {
        this.m = m;
        this.k = k;
        queue = new LinkedList<>();
        small = new TreeSet<>();
        large = new TreeSet<>();
        sum = 0;
    }

    public void addElement(int num) {
        if (queue.size() == m) {
            int old = queue.poll();
            if (!small.remove(old)) {
                large.remove(old);
                sum -= old;
            }
        }

        queue.offer(num);
        small.add(num);
        large.add(queue.peek());
        large.add(queue.peek());
        sum += num;

        if (queue.size() == m) {
            while (small.size() > k) {
                sum -= small.first();
                large.add(small.first());
                small.pollFirst();
            }
            while (large.size() > k) {
                sum -= large.last();
                small.add(large.last());
                large.pollLast();
            }
        }
    }

    public int calculateMKAverage() {
        return queue.size() < m ? -1 : (int) (sum / (m - 2 * k));
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1825 (Finding MK Average)?

This page provides optimized solutions for LeetCode problem 1825 (Finding MK Average) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1825 (Finding MK Average)?

The time complexity for LeetCode 1825 (Finding MK Average) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1825 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1825 in Java, C++, or Python.

Back to LeetCode Solutions