Skip to content

Commit 484e509

Browse files
PriyankaKhirePriyankaKhire
committed
Leetcode Accepted
1 parent b36bebb commit 484e509

2 files changed

Lines changed: 52 additions & 12 deletions

File tree

‎Blind 75/Programs/Top K Frequent Elements.py‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# Top K Frequent Elements
2+
# https://leetcode.com/problems/top-k-frequent-elements/
3+
4+
class Solution(object):
5+
def addToHeap(self, numHash):
6+
heap = []
7+
# add to heap in form of tuple, (frequency, number)
8+
# in python 2 there is no max heap, in order to get correct answer, I negated the frequency so top frequency element is on top of min heap.
9+
for key in numHash:
10+
heapq.heappush(heap, (-numHash[key], key))
11+
return heap
12+
13+
def addToHash(self, nums):
14+
numHash = {}
15+
# add all numbers to has, with key: number, value: frequency
16+
for n in nums:
17+
if n not in numHash:
18+
numHash[n] = 0
19+
numHash[n] = numHash[n] + 1
20+
return numHash
21+
22+
def topKFrequent(self, nums, k):
23+
hashMap = self.addToHash(nums)
24+
heap = self.addToHeap(hashMap)
25+
topK = []
26+
for i in range(k):
27+
(frequency, element) = heapq.heappop(heap)
28+
topK.append(element)
29+
return topK
30+
"""
31+
:type nums: List[int]
32+
:type k: int
33+
:rtype: List[int]
34+
"""
35+

‎Blind 75/README.md‎

Lines changed: 17 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
<h1>Blind 75</h1>
22
<a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Leetcode link to the post.</a>
33
<h4>Total Completed: 29</h4>
4-
<h2>Array</h2>
4+
<h2>Array (Solved: 4, Unsolved: 6)</h2>
55
<ul>
66
<li><a href="Programs/Two Sum.py">Two Sum</a>
77
<p><b>Approach</b>: Solved using hash table, you can even solve this using 2 pointer approach where you'd have to sort the array, but then you won't be able to return index. </p>
@@ -27,7 +27,7 @@
2727
<li>Find Minimum in Rotated Sorted Array</li>
2828
<li>Search in Rotated Sorted Array</li>
2929
</ul>
30-
<h2>Binary</h2>
30+
<h2>Binary (Solved: 1, Unsolved: 4)</h2>
3131
<ul>
3232
<li><a href="Programs/Sum of Two Integers.py">Sum of Two Integers</a>
3333
<p><b>Approach</b>: We can add 2 integers without using any arithmetic operator by using half adder.<br/>
@@ -102,7 +102,7 @@
102102
<li>Missing Number</li>
103103
<li>Reverse Bits</li>
104104
</ul>
105-
<h2>Dynamic Programming</h2>
105+
<h2>Dynamic Programming (Not started this)</h2>
106106
<ul>
107107
<li>Climbing Stairs</li>
108108
<li>Coin Change</li>
@@ -116,7 +116,7 @@
116116
<li>Unique Paths</li>
117117
<li>Jump Game</li>
118118
</ul>
119-
<h2>Graph</h2>
119+
<h2>Graph (Solved: 4, Unsolved: 4)</h2>
120120
<ul>
121121
<li><a href="Programs/Clone Graph.py">Clone Graph</a>
122122
<p><b>Approach</b>: Used both dfs and bfs to copy the graph. Leetcode accepted.</p>
@@ -154,15 +154,15 @@
154154
<li>Graph Valid Tree</li>
155155
<li>Number of Connected Components in an Undirected Graph</li>
156156
</ul>
157-
<h2>Interval</h2>
157+
<h2>Interval (Not started this)</h2>
158158
<ul>
159159
<li>Insert Interval</li>
160160
<li>Merge Intervals</li>
161161
<li>Non-overlapping Intervals</li>
162162
<li>Meeting Rooms</li>
163163
<li>Meeting Rooms II</li>
164164
</ul>
165-
<h2>Linked List</h2>
165+
<h2>Linked List (Solved all)</h2>
166166
<ul>
167167
<li><a href="Programs/Reverse Linked List.py">Reverse Linked List</a>
168168
<p><b>Approach</b>: Used 3 pointer approach </p>
@@ -193,7 +193,7 @@
193193
</p>
194194
</li>
195195
</ul>
196-
<h2>Matrix</h2>
196+
<h2>Matrix (Solved all)</h2>
197197
<ul>
198198
<li><a href="Programs/Set Matrix Zeroes.py">Set Matrix Zeroes</a>
199199
<p><b>Approach</b>: Set the row and col of the cell with zero to value "x".
@@ -219,7 +219,7 @@
219219
</p>
220220
</li>
221221
</ul>
222-
<h2>String</h2>
222+
<h2>String (Solved: 2, Unsolve: 8)</h2>
223223
<ul>
224224
<li><a href="Programs/Longest%20Substring%20Without%20Repeating%20Characters.py">Longest Substring Without Repeating Characters</a> <br/>
225225
<p><b>Approach</b>: We use sliding window for this one. Use hash table to keep track of the letters in the window.</p>
@@ -238,7 +238,7 @@
238238
<li>Palindromic Substrings</li>
239239
<li>Encode and Decode Strings (Leetcode Premium)</li>
240240
</ul>
241-
<h2>Tree</h2>
241+
<h2>Tree (Solved: 8, Unsolved: 6)</h2>
242242
<ul>
243243
<li><a href="Programs/Maximum Depth of Binary Tree.py">Maximum Depth of Binary Tree</a>
244244
<p><b>Approach</b>: done using simple (any)-order traversal.</p>
@@ -284,10 +284,15 @@
284284
<li>Add and Search Word</li>
285285
<li>Word Search II</li>
286286
</ul>
287-
<h2>Heap</h2>
287+
<h2>Heap (Solved: 1, Unsolved: 2)</h2>
288288
<ul>
289-
<li>Merge K Sorted Lists</li>
290-
<li>Top K Frequent Elements</li>
289+
<li><a href="Programs/Merge K sorted Lists.py">Merge K Sorted Lists</a> </li>
290+
<li><a href="Programs/Top K Frequent Elements.py">Top K Frequent Elements</a>
291+
<p><b>Approach</b>: First build a hash table with key: element, value: frequency.<br/>
292+
Then Create a heap and add all elements from the hash to the heap in form of tuple (python thing).<br/>
293+
Remove the top k elements from the heap.
294+
</p>
295+
</li>
291296
<li>Find Median from Data Stream</li>
292297
</ul>
293298

0 commit comments

Comments
 (0)