The trick here is to name the state correctly, then let the implementation follow. For 480. Sliding Window Median, the solution in this repository is mainly a binary search solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: binary search, two pointers, sliding window, greedy.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are medianSlidingWindow, window.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(Nlogk)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Runtime: 324 ms, faster than 6.78% of C++ online submissions for Sliding Window Median.
02//Memory Usage: 10 MB, less than 100.00% of C++ online submissions for Sliding Window Median.
03class Solution {
04public:
05 vector<double> medianSlidingWindow(vector<int>& nums, int k) {
06 int l = 0;
07 vector<int> window(k);
08 vector<double> ans;
09
10 while(l+k-1 < nums.size()){
11 //update the data structure
12 if(l == 0){
13 window.assign(nums.begin()+l, nums.begin()+l+k);
14 sort(window.begin(), window.end());
15 }else{
16 window.erase(find(window.begin(), window.end(), nums[l-1]));
17 //insert the new element into right place
18 //lower_bound: position of smallest element >= x
19 auto it = lower_bound(window.begin(), window.end(), nums[l+k-1]);
20 window.insert(it, nums[l+k-1]);
21 }
22
23 int median;
24 if(k % 2 == 1){
25 ans.push_back(window[k/2]);
26 }else{
27 double median = 0.0;
28 //to avoid overflow
29 median += window[k/2-1]/2.0;
30 median += window[k/2]/2.0;
31 ans.push_back(median);
32 }
33
34 l++;
35 }
36
37 return ans;
38 }
39};
40
41//C++ multiset and middle iterator
42//https://leetcode.com/problems/sliding-window-median/discuss/96340/O(n-log-k)-C%2B%2B-using-multiset-and-updating-middle-iterator
43//Runtime: 80 ms, faster than 46.39% of C++ online submissions for Sliding Window Median.
44//Memory Usage: 12.8 MB, less than 100.00% of C++ online submissions for Sliding Window Median.
45//time: O(Nlogk)
46class Solution {
47public:
48 vector<double> medianSlidingWindow(vector<int>& nums, int k) {
49 multiset<int> window(nums.begin(), nums.begin()+k);
50 /*
51 if k is odd, midIt points to the median
52 if k is even, we average *midIt and *prev(midIt)
53 */
54 auto midIt = next(window.begin(), k/2);
55 vector<double> ans;
56 int l = 0;
57
58 while(l+k-1 < nums.size()){
59 //window is initialized, so we don't update window when l == 0
60 if(l > 0){
61 //l+k-1 is now inside the window
62 //insert nums[l+k-1]
63 window.insert(nums[l+k-1]);
64 if (nums[l+k-1] < *midIt){
65 //move the iterator to correct position
66 midIt--;
67 }
68
69 //l-1 is now outside the window
70 //erase nums[l-1]
71 if (nums[l-1] <= *midIt){
72 midIt++;
73 }
74 window.erase(window.lower_bound(nums[l-1]));
75 }
76
77 //to avoid overflow
78 ans.push_back(*midIt/2.0 + *prev(midIt, 1 - k%2)/2.0);
79
80 l++;
81 }
82
83 return ans;
84 }
85};Cost