295. Find Median from Data Stream
Tags:
Hard
Skills:
Heapmin-heapmax-heap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
1/*
2Ques 1:
3Design a class has a function
4
5data_stream: number[]
6add_num(x: number): void -> add x to data_stream - O(1)
7find_median(): number -> O(1)
8 - find median in data_stream
9 - in case size is odd: only one mid
10 - in case size is even: average of 2 mid element
11
12Example of median:
13arr = [2,3,4], the median is 3.
14arr = [2,3], the median is (2 + 3) / 2 = 2.5. -> size 2 / 2 = Math.ceil(1) = 1, 1 - 0 = 0
15
16data_stream: number[]
17add_num(x) -> push x to data_stream -> O(1)
18find_median() - O(nlogn)
19 - sort() -> O(nlogn)
20 - check is size of data_stream
21 - case odd: find middle -> data_stream / 2;
22 - case even: find middle -> mid - 1, mid + 1
23
24Optimize
25data_stream: number[]
26candidates: number[]
27
28
29add_num(x) -> O(1)
30 init: data_stream []
31 x = 2; data_stream.push(x) -> [2]
32 x = 1; data_stream.at(-1) = 2 > x -> data.stream.push(1) -> [2, 1] -> swap [1, 2]
33 x = 0;
34
35
36 if (data_stream.at(-1) < x) data_stream.push(x)
37 if (data_stream.at(-1) > x) swap(x and data_stream.at(-1) -> sort data_stream
38
39find_median() -> O(1)
40 - check is size of data_stream
41 - case odd: find middle -> data_stream / 2;
42 - case even: find middle -> mid - 1, mid + 1
43
44data_stream: number[]
45max-heap -> a half of small number
46min-heap -> a half of large number
47
48-> all the element in max-heap < all the element in min-heap
49-> max-heap.size = min-heap.size, different is 1
50
51add_num(x)
52 - add x to min_heap or max_heap dependent on the value Min(min_heap) or Max(max_heap)
53 - [max-heap x min-heap] - O(logn), SC: O(n)
54 - compare x with max in max-heap, and x with min in min-heap
55 - balance the size of 2 heaps
56
57find_median(): number - O(1)
58 - if max_heap.size < min_heap.size, the median is in the min_heap
59 - else if max_heap.size > min_heap.size, the median is in the max_heap
60 - else if max_heap.size === min_heap.size, get Median of Max(max_heap) and Min(min_heap)
61*/
62class Solution {
63 private min_heap: number[];
64 private max_heap: number[];
65
66 constructor() {
67 this.min_heap = []
68 this.max_heap = []
69 }
70
71 add_num(x: number): void {
72 // Add to max_heap
73 if(this.max_heap.length === 0 && this.min_heap.length === 0) {
74 this.max_heap.pushHeap(x)
75 }
76
77
78 if(this.min_heap.length && this.max_heap.length && x > this.max_heap.at(-1)) {
79 this.min_heap.pushHeap(x)
80 } else {
81 this.max_heap.pushHeap(x)
82 }
83
84 if(this.min_heap.length > this.max_heap.length) {
85
86 }
87
88
89 }
90
91 find_median(): number {
92
93
94
95 }
96
97 pushHeap(val: number): void {
98 ...
99 }
100
101 popHeap(val: number): number {
102 ...
103 }
104
105
106}
107
108dequeue
front → lấy dữ liệu từ root
Problem
Bài toán yêu cầu thiết kế một class MedianFinder để thêm số vào luồng dữ liệu và return median (trung vị) của tất cả các số đã thêm vào bất cứ lúc nào. Median là số ở giữa khi dãy số được sắp xếp, nếu số lượng phần tử là chẵn thì median là trung bình cộng của hai số ở giữa
Approach
Quy tắc
Time and space complexity
Solution - Two heap
1class MedianFinder {
2 min_heap: any
3 max_heap: any
4 constructor() {
5 this.min_heap = new MinPriorityQueue();
6 this.max_heap = new MaxPriorityQueue();
7 }
8
9 addNum(num: number): void {
10 this.max_heap.enqueue(num);
11 this.min_heap.enqueue(this.max_heap.dequeue());
12 if (this.min_heap.size() > this.max_heap.size()) this.max_heap.enqueue(this.min_heap.dequeue())
13 }
14
15 findMedian(): number {
16 if (this.max_heap.size() > this.min_heap.size()) return this.max_heap.front()
17 else return (this.min_heap.front() + this.max_heap.front()) / 2
18 }
19}
20
21/**
22 * Your MedianFinder object will be instantiated and called as such:
23 * var obj = new MedianFinder()
24 * obj.addNum(num)
25 * var param_2 = obj.findMedian()
26 */