Untitled

import java.util.*;

public class SlidingWindowMedian {
    public double[] medianSlidingWindow(int[] nums, int k) {
        // Result array
        double[] result = new double[nums.length - k + 1];

        // Min-heap for larger half
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Max-heap for smaller half
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // Step 1: Process the first window
        for (int i = 0; i < k; i++) {
            addNumber(nums[i], maxHeap, minHeap);
        }
        balanceHeaps(maxHeap, minHeap);
        result[0] = getMedian(maxHeap, minHeap);

        // Step 2: Slide the window
        for (int i = k; i < nums.length; i++) {
            int incoming = nums[i];
            int outgoing = nums[i - k];

            // Add the new number
            addNumber(incoming, maxHeap, minHeap);

            // Remove the outgoing number
            removeNumber(outgoing, maxHeap, minHeap);

            // Balance the heaps
            balanceHeaps(maxHeap, minHeap);

            // Record the median for the current window
            result[i - k + 1] = getMedian(maxHeap, minHeap);
        }

        return result;
    }

    // Helper function to add a number to the heaps
    private void addNumber(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
    }

    // Helper function to remove a number from the heaps
    private void removeNumber(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (!maxHeap.isEmpty() && num <= maxHeap.peek()) {
            maxHeap.remove(num);
        } else {
            minHeap.remove(num);
        }
    }

    // Balance the two heaps
    private void balanceHeaps(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    // Helper function to get the median
    private double getMedian(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }

    public static void main(String[] args) {
        SlidingWindowMedian solver = new SlidingWindowMedian();
        int[] nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
        int k1 = 3;
        System.out.println(Arrays.toString(solver.medianSlidingWindow(nums1, k1)));

        int[] nums2 = {1, 2, 3, 4, 2, 3, 1, 4, 2};
        int k2 = 3;
        System.out.println(Arrays.toString(solver.medianSlidingWindow(nums2, k2)));
    }
}