8000 Added task 295 · jscrdev/LeetCode-in-Racket@a70210d · GitHub
[go: up one dir, main page]
Skip to content

Commit a70210d

Browse files
javadevjavadev
authored
Added task 295
1 parent a2e8a7b commit a70210d

File tree

3 files changed

+76
-0
lines changed

3 files changed

+76
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1317,6 +1317,7 @@ Racket-based LeetCode algorithm problem solutions, regularly updated.
13171317
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
13181318
|-|-|-|-|-|-
13191319
| 0215 |[Kth Largest Element in an Array](src/main/racket/g0201_0300/s0215_kth_largest_element_in_an_array/Solution.rkt)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Heap_Priority_Queue, Divide_and_Conquer, Quickselect, Big_O_Time_O(n\*log(n))_Space_O(log(n)) | 79 | 100.00
1320+
| 0295 |[Find Median from Data Stream](src/main/racket/g0201_0300/s0295_find_median_from_data_stream/MedianFinder.rkt)| Hard | Top_100_Liked_Questions, Sorting, Two_Pointers, Design, Heap_Priority_Queue, Data_Stream, Big_O_Time_O(n\*log_n)_Space_O(n) | 437 | 100.00
13201321

13211322
#### Top Interview 150 Bit Manipulation
13221323

@@ -1577,6 +1578,7 @@ Racket-based LeetCode algorithm problem solutions, regularly updated.
15771578
| 0338 |[Counting Bits](src/main/racket/g0301_0400/s0338_counting_bits/Solution.rkt)| Easy | Dynamic_Programming, Bit_Manipulation, Udemy_Bit_Manipulation, Big_O_Time_O(num)_Space_O(num) | 3 | 100.00
15781579
| 0322 |[Coin Change](src/main/racket/g0301_0400/s0322_coin_change/Solution.rkt)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Breadth_First_Search, Algorithm_II_Day_18_Dynamic_Programming, Dynamic_Programming_I_Day_20, Level_2_Day_12_Dynamic_Programming, Top_Interview_150_1D_DP, Big_O_Time_O(m\*n)_Space_O(amount) | 29 | 100.00
15791580
| 0300 |[Longest Increasing Subsequence](src/main/racket/g0201_0300/s0300_longest_increasing_subsequence/Solution.rkt)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Binary_Search, Algorithm_II_Day_16_Dynamic_Programming, Binary_Search_II_Day_3, Dynamic_Programming_I_Day_18, Udemy_Dynamic_Programming, Top_Interview_150_1D_DP, Big_O_Time_O(n\*log_n)_Space_O(n) | 3 | 100.00
1581+
| 0295 |[Find Median from Data Stream](src/main/racket/g0201_0300/s0295_find_median_from_data_stream/MedianFinder.rkt)| Hard | Top_100_Liked_Questions, Sorting, Two_Pointers, Design, Heap_Priority_Queue, Data_Stream, Top_Interview_150_Heap, Big_O_Time_O(n\*log_n)_Space_O(n) | 437 | 100.00
15801582
| 0287 |[Find the Duplicate Number](src/main/racket/g0201_0300/s0287_find_the_duplicate_number/Solution.rkt)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Two_Pointers, Bit_Manipulation, Binary_Search_II_Day_5, Big_O_Time_O(n)_Space_O(n) | 327 | 100.00
15811583
| 0238 |[Product of Array Except Self](src/main/racket/g0201_0300/s0238_product_of_array_except_self/Solution.rkt)| Medium | Top_100_Liked_Questions, Array, Prefix_Sum, Data_Structure_II_Day_5_Array, Udemy_Arrays, Top_Interview_150_Array/String, Big_O_Time_O(n^2)_Space_O(n) | 10 | 100.00
15821584
| 0234 |[Palindrome Linked List](src/main/racket/g0201_0300/s0234_palindrome_linked_list/Solution.rkt)| Easy | Top_100_Liked_Questions, Two_Pointers, Stack, Linked_List, Recursion, Level_2_Day_3_Linked_List, Udemy_Linked_List, Big_O_Time_O(n)_Space_O(1) | 69 | 100.00

‎src/main/racket/g0201_0300/s0295_find_median_from_data_stream/MedianFinder.rkt

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
; #Hard #Top_100_Liked_Questions #Sorting #Two_Pointers #Design #Heap_Priority_Queue #Data_Stream
2+
; #Top_Interview_150_Heap #Big_O_Time_O(n*log_n)_Space_O(n)
3+
; #2025_02_15_Time_437_ms_(100.00%)_Space_132.32_MB_(100.00%)
4+
5+
(require data/heap racket/class)
6+
7+
(define median-finder%
8+
(class object%
9+
(super-new)
10+
11+
;; Max heap (stores smaller half, max at the top)
12+
(define max-heap (make-heap >))
13+
;; Min heap (stores larger half, min at the top)
14+
(define min-heap (make-heap <))
15+
16+
;; add-num : exact-integer? -> void?
17+
(define/public (add-num num)
18+
(heap-add! max-heap num) ; Add to max-heap
19+
(heap-add! min-heap (heap-min max-heap)) ; Move max-heap root to min-heap
20+
(heap-remove-min! max-heap) ; Remove moved element
21+
22+
;; Balance: Ensure max-heap has at least as many elements as min-heap
23+
(when (> (heap-count min-heap) (heap-count max-heap))
24+
(heap-add! max-heap (heap-min min-heap))
25+
(heap-remove-min! min-heap)))
26+
27+
;; find-median : -> flonum?
28+
(define/public (find-median)
29+
(if (> (heap-count max-heap) (heap-count min-heap))
30+
(exact->inexact (heap-min max-heap))
31+
(/ (+ (heap-min max-heap) (heap-min min-heap)) 2.0)))))

‎src/main/racket/g0201_0300/s0295_find_median_from_data_stream/readme.md

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
295\. Find Median from Data Stream
2+
3+
Hard
4+
5+
The **median** is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.
6+
7+
* For example, for `arr = [2,3,4]`, the median is `3`.
8+
* For example, for `arr = [2,3]`, the median is `(2 + 3) / 2 = 2.5`.
9+
10+
Implement the MedianFinder class:
11+
12+
* `MedianFinder()` initializes the `MedianFinder` object.
13+
* `void addNum(int num)` adds the integer `num` from the data stream to the data structure.
14+
* `double findMedian()` returns the median of all elements so far. Answers within <code>10<sup>-5</sup></code> of the actual answer will be accepted.
15+
16+
**Example 1:**
17+
18+
**Input**
19+
20+
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
21+
[[], [1], [2], [], [3], []]
22+
23+
**Output:** [null, null, null, 1.5, null, 2.0]
24+
25+
**Explanation:**
26+
27+
MedianFinder medianFinder = new MedianFinder();
28+
medianFinder.addNum(1); // arr = [1]
29+
medianFinder.addNum(2); // arr = [1, 2]
30+
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
31+
medianFinder.addNum(3); // arr[1, 2, 3]
32+
medianFinder.findMedian(); // return 2.0
33+
34+
**Constraints:**
35+
36+
* <code>-10<sup>5</sup> <= num <= 10<sup>5</sup></code>
37+
* There will be at least one element in the data structure before calling `findMedian`.
38+
* At most <code>5 * 10<sup>4</sup></code> calls will be made to `addNum` and `findMedian`.
39+
40+
**Follow up:**
41+
42+
* If all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?
43+
* If `99%` of all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?

0 commit comments

Comments
 (0)
0