Home/

...

/

Kth Largest Number in a Stream (medium)

Kth Largest Number in a Stream (medium)

Resources for finding the largest number in a stream.

Dry-run templates

This is the implementation of the solution provided for the problem posed in the lesson:

Press + to interact
Python 3.5
from heapq import *
class KthLargestNumberInStream:
  minHeap = []
  def __init__(self, nums, k):
    self.k = k
    # add the numbers in the min heap
    for num in nums:
      self.add(num)
  def add(self, num):
    # add the new number in the min heap
    heappush(self.minHeap, num)
    # if heap has more than 'k' numbers, remove one number
    if len(self.minHeap) > self.k:
      heappop(self.minHeap)
    # return the 'Kth largest number
    return self.minHeap[0]
def main():
  kthLargestNumber = KthLargestNumberInStream([3, 1, 5, 12, 2, 11], 4)
  print("4th largest number is: " + str(kthLargestNumber.add(6)))
  print("4th largest number is: " + str(kthLargestNumber.add(13)))
  print("4th largest number is: " + str(kthLargestNumber.add(4)))
main()

Students may be encouraged to run through the provided solution with the following sample inputs.

Sample input #1

Input: [3, 1, 5, 12, 2, 11], K = 4

Line number

num

minHeap

Kth largest element (minHeap[0])

27

-

[]

-

10 - 11, 15

3

[3]

3

10 - 11, 15

1

[1, 3]

1

10 - 11, 15

5

[1, 3, 5]

1

10 - 11, 15

12

[1, 3, 5, 12]

1

10 - 11, 15

2

[1, 2, 5, 12, 3]

1

18 - 19

2

[2, 3, 5, 12]

2

10 - 11, 15

11

[2, 3, 5, 12, 11]

2

18 - 19

11

[3, 11, 5, 12]

3

Sample input #2

Input: [3, 1, 5, 12, 2, 11, 6], K = 4

Line number

num

minHeap

Kth largest element (minHeap[0])

27

-

[]

-

10 - 11, 15

3

[3]

3

10 - 11, 15

1

[1, 3]

1

10 - 11, 15

5

[1, 3, 5]

1

10 - 11, 15

12

[1, 3, 5, 12]

1

10 - 11, 15

2

[1, 2, 5, 12, 3]

1

18 - 19

2

[2, 3, 5, 12]

2

10 - 11, 15

11

[2, 3, 5, 12, 11]

2

18 - 19

11

[3, 11, 5, 12]

3

10 - 11, 15

6

[3, 6, 5, 12, 11]

3

18 - 19

6

[5, 6, 11, 12]

5

Step-by-step solution construction

We’ll be using a heap to find the kth largest element in a given stream of numbers.

The first step is to populate our heap. We’ll iterate over the stream values and push them on to the heap using the class’s add() function.

We can either initialize a stream of numbers directly and the constructor in our class will call the add() function itself, or we can populate using the add() function manually. For example, consider a stream of numbers [1,2,3,4,5][1,2,3,4,5]. We can populate our heap in either of the following manner:

# Constructor method 
kthLargestNumber = KthLargestNumberInStream([1,2,3,4,5], k)

# Manually calling the 'add' function
kthLargestNumber = KthLargestNumberInStream([], k)
KthLargestNumberInStream.add(1)
KthLargestNumberInStream.add(2)
KthLargestNumberInStream.add(3)
KthLargestNumberInStream.add(4)
KthLargestNumberInStream.add(5)

We can also use both methods together. We have added a utility function, result() to our class, that returns the smallest element in the heap. Let’s see this below:

Press + to interact
Python 3.5
from heapq import *
 
 
class KthLargestNumberInStream:
 minHeap = []
 
 def __init__(self, nums, k):
   self.k = k
   # add the numbers in the min heap
   for num in nums:
     self.add(num)
 
 def add(self, num):
   # add the new number in the min heap
   print("Pushing",num, "on to the heap.")
   heappush(self.minHeap, num)
   print("Heap: ", self.minHeap, "\n")
 
 def result(self):
   # return the smallest number in the heap
   return self.minHeap[0]
 
 
def main():
 
 kthLargestNumber = KthLargestNumberInStream([3, 1, 5, 12, 2, 11], 4)
 print("Smallest number in the heap is: " + str(kthLargestNumber.result()))
 print("-"*100 + "\n")
 input = [6, 13, -1, 4]
 for i in input:
   kthLargestNumber.add(i)
   print("Smallest number in the heap is: " + str(kthLargestNumber.result()))
   print("-"*100 + "\n")
 
 
main()

Since we want the kth largest element, we’ll add a condition to only keep k elements in our heap. When the size of our heap exceeds k, we pop one number. In that state, after the pop operation, our kth largest element will be at the top of the heap, that is, the first element.

Press + to interact
Python 3.5
from heapq import *
 
 
class KthLargestNumberInStream:
 minHeap = []
 
 def __init__(self, nums, k):
   self.k = k
   # add the numbers in the min heap
   for num in nums:
     self.add(num)
 
 def add(self, num):
   # add the new number in the min heap
   print("Pushing",num, "on to the heap.")
   heappush(self.minHeap, num)
   print("\tHeap: ", self.minHeap)
 
   # if heap has more than 'k' numbers, remove one number
   if len(self.minHeap) > self.k:
     print("\tSize of heap: " + str(len(self.minHeap)) + ". Since it's greater than our k = " + str(self.k) + ", we pop from the heap.")
     heappop(self.minHeap)
     print("\tHeap after the pop operation: " + str(self.minHeap))
   print("")
 
 def result(self):
   # return the smallest number in the heap
   return self.minHeap[0]
 
 
def main():
 
 kthLargestNumber = KthLargestNumberInStream([3, 1, 5, 12, 2, 11], 4)
 print("4th largest number in the heap is: " + str(kthLargestNumber.result()))
 print("-"*100 + "\n")
 input = [6, 13, -1, 4]
 for i in input:
   kthLargestNumber.add(i)
   print("4th largest number in the heap is: " + str(kthLargestNumber.result()))
   print("-"*100 + "\n")
 
main()

Lastly, we return the top element of our heap since it’s our kth largest element. The return statement executes every time we add a new element to the heap until we’ve reached the end of our stream.

Press + to interact
Python 3.5
from heapq import *
 
 
class KthLargestNumberInStream:
 minHeap = []
 
 def __init__(self, nums, k):
   self.k = k
   # add the numbers in the min heap
   for num in nums:
     self.add(num)
 
 def add(self, num):
   # add the new number in the min heap
   print("Pushing",num, "on to the heap.")
   heappush(self.minHeap, num)
   print("\tHeap: ", self.minHeap)
 
   # if heap has more than 'k' numbers, remove one number
   if len(self.minHeap) > self.k:
     print("\tSize of heap: " + str(len(self.minHeap)) + ". Since it's greater than our k = " + str(self.k) + ", we pop.")
     heappop(self.minHeap)
     print("\tHeap after the pop operation: " + str(self.minHeap))
 
   # return the 'Kth largest number
   print("\tReturning the first element of the heap: " + str(self.minHeap[0]) + "\n")
   return self.minHeap[0]
 
 def result(self):
   # return the smallest number in the heap
   return self.minHeap[0]
 
 
def main():
 
 kthLargestNumber = KthLargestNumberInStream([3, 1, 5, 12, 2, 11], 4)
 print("4th largest number is: " + str(kthLargestNumber.result()))
 print("-"*100 + "\n")
 input = [6, 13, -1, 4]
 for i in input:
   print("4th largest number is: " + str(kthLargestNumber.add(i)))
   print("-"*100 + "\n")
 
 
main()