Sliding Window Median

shitgpt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        if k == 1:
            return nums
        if k == 2:
            return [(p + q) / 2 for p,q in pairwise(nums)]
        kodd = k % 2
        ref = sorted(nums[:k])
        hl = [-x for x in ref[:k//2]]
        hl.reverse()
        hr = ref[k//2:]
        if kodd:
            out = [hr[0]]
        else:
            out = [(hr[0] - hl[0]) / 2]
        hrd = []
        hld = []
        def cleanr():
            while hrd and hrd[0] == hr[0]:
                heappop(hrd)
                heappop(hr)
        def cleanl():
            while hld and hld[0] == hl[0]:
                heappop(hld)
                heappop(hl)
        for idx,x in enumerate(nums[k:]):
            y = nums[idx]
            mid = hr[0]
            if y >= mid:
                if x < mid:
                    x = -heappushpop(hl, -x)
                    cleanl()
                heappush(hr, x)
                heappush(hrd, y)
                cleanr()
            else:
                if x >= mid:
                    x = heappushpop(hr, x)
                    cleanr()
                heappush(hl, -x)
                heappush(hld, -y)
                cleanl()
            if kodd:
                out.append(hr[0])
            else:
                out.append((hr[0] - hl[0]) / 2)
        return out

Identifying Problem Isomorphism

“Sliding Window Median” involves finding the median of the current window of numbers from a data stream that can change as elements slide in and out of the window.

Two problems that could be considered isomorphic are:

1. “239. Sliding Window Maximum”: This problem is a simpler version of “Sliding Window Median”. Here, instead of maintaining and updating the median, we are tasked with finding the maximum in the current window.

2. “480. Sliding Window Maximum II”: This is a more complex version of “Sliding Window Median” where the task is to find the maximum in the current window, but with an added condition that the array could contain -1 indicating that the maximum number in the window is removed.

The order of complexity from simple to more complex:

• “239. Sliding Window Maximum”
• “Sliding Window Median”
• “480. Sliding Window Maximum II”.

These problems share the concept of managing and processing a sliding window of data.

10 Prerequisite LeetCode Problems

“Sliding Window Median” requires the understanding of concepts such as arrays, sliding window, and median finding which could be complex due to the need of maintaining a sorted order. Here are some problems to prepare:

1. Two Sum: This problem helps with understanding the basic manipulation of arrays.

2. Maximum Subarray: This problem introduces you to the concept of subarrays.

3. Find All Duplicates in an Array: A step further in complex array manipulation.

4. Sliding Window Maximum: This problem is a great introduction to the sliding window concept, which is crucial in solving the “Sliding Window Median” problem.

5. Median of Two Sorted Arrays: Understanding the concept of finding a median in an array.

6. Find Median from Data Stream: This problem provides practice on dynamically finding medians.

7. Minimum Size Subarray Sum: This problem uses a sliding window to find subarrays, adding a layer of complexity.

8. Contains Duplicate II: This problem helps to practice managing array indices.

9. Subarray Product Less Than K: Another problem focusing on the sliding window concept with a product operation twist.

10. 3Sum Closest: This problem introduces the concept of maintaining the sum while traversing the array, which is a bit similar to maintaining the median in the target problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        if k == 1:
            return nums
        if k == 2:
            return [(p + q) / 2 for p,q in pairwise(nums)]
        kodd = k % 2
        ref = sorted(nums[:k])
        hl = [-x for x in ref[:k//2]]
        hl.reverse()
        hr = ref[k//2:]
        if kodd:
            out = [hr[0]]
        else:
            out = [(hr[0] - hl[0]) / 2]
        hrd = []
        hld = []
        def cleanr():
            while hrd and hrd[0] == hr[0]:
                heappop(hrd)
                heappop(hr)
        def cleanl():
            while hld and hld[0] == hl[0]:
                heappop(hld)
                heappop(hl)
        for idx,x in enumerate(nums[k:]):
            y = nums[idx]
            mid = hr[0]
            if y >= mid:
                if x < mid:
                    x = -heappushpop(hl, -x)
                    cleanl()
                heappush(hr, x)
                heappush(hrd, y)
                cleanr()
            else:
                if x >= mid:
                    x = heappushpop(hr, x)
                    cleanr()
                heappush(hl, -x)
                heappush(hld, -y)
                cleanl()
            if kodd:
                out.append(hr[0])
            else:
                out.append((hr[0] - hl[0]) / 2)
        return out

Problem Classification

Sliding Window Median - This problem asks to find the median in a sliding window on a list of numbers. This is a Window-based Statistical Calculation Problem.

Language Agnostic Coding Drills

The syntax might vary across languages, but the core concepts and problem-solving approach remain the same.

1. Understanding Basic Data Types and Variables: Define integer, float, string, and boolean variables and print them.

2. Control Flow - Conditional Statements: Write a piece of code that uses if, else if, and else statements.

3. Control Flow - Loops: Write a piece of code that prints the numbers from 1 to 10 using a for loop and a while loop.

4. Functions: Define a function that takes two numbers as inputs and returns their sum. Call this function with different inputs.

5. Arrays/Lists: Initialize an array/list with some values, write a loop to iterate over it and print each value.

6. Sorting: Implement a basic sorting algorithm such as Bubble Sort or Selection Sort.

7. Strings Manipulation: Given a string, write a function that reverses the string.

8. Data Structures - Stack: Implement a basic stack with operations push and pop.

9. Data Structures - Queue: Implement a basic queue with operations enqueue and dequeue.

10. Recursion: Write a recursive function to calculate the factorial of a number.

11. Searching Algorithms: Implement a basic searching algorithm like Linear Search or Binary Search.

12. Basic Input and Output: Write a piece of code that takes input from the user and prints it.

13. Working with Dictionaries/Hashmaps: Create a dictionary/hashmap, add some key-value pairs, and write a function to print the value of a given key.

14. Exception Handling: Write a piece of code that can catch and handle an exception.

15. Working with Files: Write a piece of code that can read from a file and write to a file.

16. Sliding Window Algorithm: Given an array of integers, find the maximum/minimum sum of any contiguous subarray of size k.

17. Object-Oriented Programming: Define a class with some properties and methods. Instantiate this class and call its methods.

Python Coding Drills

1. Python List Comprehension: Python list comprehension is a concise way to create lists. It is a unique way of quickly creating a list with python.

2. Basic Data Structures (List, Heap): Understanding basic Python data structures such as lists and heaps is crucial for this problem.

3. Python Inbuilt Functions: This includes functions like enumerate(), heappush(), heappop(), and heappushpop().

4. Sorting Techniques: This involves understanding how to sort an array and understanding the complexity of various sorting techniques.

5. Sliding Window Algorithm: It’s a method for finding subarrays in an array that satisfy given conditions.

6. Managing Two Heaps: In this problem, we are maintaining two heaps to track the median in a streaming dataset or sliding window.

7. Understanding Python Ternary Operator: Python ternary operator is a one-line if-else statement.

These topics can be arranged in increasing level of difficulty as follows:

1. Python List Comprehension
2. Basic Data Structures (List, Heap)
3. Python Inbuilt Functions
4. Sorting Techniques
5. Understanding Python Ternary Operator
6. Sliding Window Algorithm
7. Managing Two Heaps

For a problem-solving approach:

1. Understand the problem requirements and constraints.
2. Determine the suitable data structure for solving the problem.
3. Implement a sliding window algorithm to keep track of the current window in the list.
4. For each window, sort the list and determine the median.
5. Handle edge cases, such as when k is 1 or 2.
6. Finally, append the calculated median to the output list.
7. Clean up the heaps for maintaining the two halves of the window after each movement.
8. Make sure the heaps are balanced in size after each operation.
9. Determine the median from the heaps based on the total number of elements. If it’s odd, the median is the smallest element in the larger heap. If it’s even, the median is the average of the smallest element in the larger heap and the largest element in the smaller heap.
10. Append the calculated median to the output list.

Targeted Drills in Python

1. Python List Comprehension:

   Task: Given a list, create a new list that squares each number in the original list.

   1 2 3

   original = [1, 2, 3, 4, 5] squares = [num**2 for num in original] print(squares) # Output: [1, 4, 9, 16, 25]

2. Basic Data Structures (List, Heap):

   Task: Implement a max heap and perform basic operations.

   1 2 3 4 5 6

   import heapq nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] # Use heapq to create a max heap max_heap = [-num for num in nums] heapq.heapify(max_heap) print(max_heap) # Output: [-9, -7, -8, -3, -4, -2, -5, -6, -1, 0]

3. Python Inbuilt Functions:

   Task: Use enumerate(), heappush(), heappop(), and heappushpop().

   1 2 3 4 5 6 7 8 9 10

   from heapq import heappush, heappop, heappushpop heap = [] data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] for i, num in enumerate(data): heappush(heap, num) if i % 3 == 0: print(heappop(heap)) if i % 4 == 0: print(heappushpop(heap, i))

4. Sorting Techniques:

   Task: Sort a list of numbers in ascending and descending order.

   1 2 3 4 5

   numbers = [5, 2, 3, 1, 4] sorted_asc = sorted(numbers) sorted_desc = sorted(numbers, reverse=True) print(sorted_asc) # Output: [1, 2, 3, 4, 5] print(sorted_desc) # Output: [5, 4, 3, 2, 1]

5. Understanding Python Ternary Operator:

   Task: Use a ternary operator to assign a variable based on a condition.

   1 2 3 4

   a = 10 b = 20 max_val = a if a > b else b print(max_val) # Output: 20

6. Sliding Window Algorithm:

   Task: Find the maximum sum subarray of a fixed size.

   1 2 3 4 5 6 7 8

   def max_sum_subarray(arr, window_size): window_sum = sum([arr[i] for i in range(window_size)]) max_sum = window_sum for i in range(len(arr) - window_size): window_sum = window_sum - arr[i] + arr[i + window_size] max_sum = max(window_sum, max_sum) return max_sum print(max_sum_subarray([1, 9, -1, -2, 7, 3, -1, 2, 4, -6], 5)) # Output: 13

7. Managing Two Heaps:

   Task: Implement a data structure to find the median of a number stream.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   import heapq class MedianFinder: def __init__(self): self.heaps = [], [] def addNum(self, num): small, large = self.heaps heapq.heappush(small, -heapq.heappushpop(large, num)) if len(large) < len(small): heapq.heappush(large, -heapq.heappop(small)) def findMedian(self): small, large = self.heaps if len(large) > len(small): return float(large[0]) return (large[0] - small[0]) / 2.0

   Test the MedianFinder class:

   1 2 3 4 5 6

   mf = MedianFinder() mf.addNum(1) mf.addNum(2) print(mf.findMedian()) # Output: 1.5 mf.addNum(3) print(mf.findMedian()) # Output: 2.0

For all of these drills, it’s important to not just write the code, but also understand why it works. If you find a particular topic challenging, spend some more time practicing and researching that topic until you feel comfortable with it.