search

Just-A-Visitor / Algorithmic-Pseudocode

This repository contains the pseudocode(pdf) of various algorithms and data structures necessary for Interview Preparation and Competitive Coding
GNU General Public License v3.0
758 stars 166 forks source link

Added Kth Largest Element in Stream #94

Closed ymoullec closed 4 years ago

ymoullec commented 4 years ago

This is my version of the Kth Largest Element in a Stream Algorithm. This PR concerns the issue #40.

I kept the basic 2-function structure that was given as a template in LeetCode.

If the priority queue uses a heap data structure, time complexity is :

  1. O(log(n!)) for the initialization of the queue, n being the number of elements in the given array. Indeed, it requires n O(log(k)) insertions, k increasing from 1 to n as elements are inserted.
  2. O(log(k)) for adding a new element from the stream. Indeed, it requires 1 insertion and 1 deletion (except for the first call after init) both of which are O(log(k)).
welcome[bot] commented 4 years ago

Thanks for opening this pull request! Please check out our contributing guidelines.

ghost commented 4 years ago

Thanks. I'm a bit occupied till 20th, so I might not get time to review the code before that. Till then, you can look around other issues if you wish.

ymoullec commented 4 years ago

Ok good to know. When you do review the code, if you find any problem that can be described in less amount of time than what it takes to fix it, I'll be happy to fix it for you.

ghost commented 4 years ago

I've reviewed the code. You don't actually need to change anything. Just go through the reviews and mark them resolved once you are convinced. Then, you can just overwrite your code with this link

Finally, move the file to the Heaps folder.

ymoullec commented 4 years ago

I think everything has been taken care of. I've made the changes and updated my pull request.

ghost commented 4 years ago

Good Work. Merged!

welcome[bot] commented 4 years ago

Congrats on merging your first pull request! We here at behaviorbot are proud of you!