🚀 LeetCode 480: Sliding Window Median – My Learning Journey & a Game-Changing Data Structure

Today I solved https://leetcode.com/problems/sliding-window-median/ and learned something super useful that I wanted to share with the community — especially if you're preparing for interviews or optimizing your Python solutions.

🧪 My First Attempt: Brute Force

I started with a simple brute-force approach using Python’s built-in sorted():

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        op = []
        for left in range(len(nums) - k + 1):
            temp = sorted(nums[left:left + k])
            if k % 2 == 0:
                med = (temp[k // 2] + temp[(k // 2) - 1]) / 2
            else:
                med = temp[k // 2]
            op.append(med)
        return op

✅ Works for small inputs
❌ Fails with Time Limit Exceeded on large test cases

Why? Because sorted() takes O(k log k) time for each window, and with n - k + 1 windows, the total time complexity becomes O(nk log k) — not scalable.

💡 The Breakthrough: SortedList from sortedcontainers

Then I discovered SortedList — a powerful data structure from the sortedcontainers Python module. Here's the optimized solution:

from sortedcontainers import SortedList

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        op = []
        temp = SortedList()
        for i in range(len(nums)):
            temp.add(nums[i])
            if len(temp) > k:
                temp.remove(nums[i - k])
            if len(temp) == k:
                if k % 2 == 0:
                    med = (temp[k // 2] + temp[(k // 2) - 1]) / 2
                else:
                    med = temp[k // 2]
                op.append(med)
        return op

🧠 What is SortedList?

SortedList is a part of the https://pypi.org/project/sortedcontainers/ module — a fast, pure-Python implementation of sorted collections.

It maintains elements in sorted order automatically and supports:

• O(log n) insertion
• O(log n) deletion
• O(1) access by index
• O(log n) search operations

This makes it ideal for problems where you need to maintain a dynamic sorted window or stream.

⏱️ Time Complexity Comparison

📚 Where Can You Use SortedList?

Perfect for problems involving:

• Dynamic median finding
• Sliding window min/max
• Kth largest/smallest in a stream

Example LeetCode problems:

• 295. Find Median from Data Stream
• 239. Sliding Window Maximum
• 703. Kth Largest Element in a Stream

💼 Pro Tip

This exact problem was asked in Walmart R1 interview recently. Knowing how to optimize sliding window problems using SortedList or heaps can really set you apart in interviews!