In this Leetcode Sliding Window Median problem solution Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

Leetcode Sliding Window Median problem solution


Problem solution in Python.

def medianSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        import bisect
        left = []
        right = []
        result = []

        for i, n in enumerate(nums):
            if i + 1 > k:
                pop_idx = i - k
                if nums[pop_idx] <= left[-1]:
                    pos = bisect.bisect_left(left, nums[pop_idx])
                    left.pop(pos)
                else:
                    pos = bisect.bisect_left(right, nums[pop_idx])
                    right.pop(pos)

            if not left or n > left[-1]:
                bisect.insort(right, n)
            else:
                bisect.insort(left, n)

            while len(left) > len(right) + 1:
                x = left.pop(-1)
                bisect.insort(right, x)

            while len(right) > len(left):
                x = right.pop(0)
                bisect.insort(left, x)

            if i + 1 >= k:
                if len(left) > len(right):
                    result.append(left[-1])
                else:
                    result.append((left[-1] + right[0]) / 2.0)
        return result


Problem solution in Java.

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] res = new double[n - k + 1];
        int i = 0; //index of res

        int l = 0, r = k - 1;
        while (r < n) {
            int[] tmp = Arrays.copyOfRange(nums, l, r + 1);
            Arrays.sort(tmp);
            if (k % 2 == 1) {
                res[i++] = tmp[k / 2] * 1.0;
            } else {
                res[i++] = (tmp[k / 2 - 1] * 1.0 + tmp[k / 2] * 1.0) / 2;
            }
            l++; r++;
        }
        return res;
    }
}


Problem solution in C++.

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> ms;
        for (int i = 0; i < k - 1; ++i)
            ms.insert(nums[i]);
        
        vector<double> res;
        
        for (int i = k - 1; i < nums.size(); ++i) {
            ms.insert(nums[i]);
            auto it = next(ms.begin(), (k - 1) / 2);
            res.push_back(k % 2 ? *it : ((static_cast<double>(*it) + *next(it)) / 2));
            ms.erase(ms.lower_bound(nums[i - k + 1]));
        }
        
        return res;
    }
};