Leetcode Sliding Window Median problem solution

YASH PAL,

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;
    }
};
coding problems