Heap Data Structure, Min and Max Heap with Leetcode # 215,

✅ 100% | minHeap | very simple | explained : ) ✅ - undefined - LeetCode

Intuition

In this problem, I have used the technique of heap called “minHeap”
if you already know about the minheap its perfect to directly jump into the approach section, for those who do not know about heap and minheap or maxheap I will explain it to you in my own simple words:

1. Heap
   Heap is a special tree-based-data-structure, in which the tree is a complete binary tree. Since a heap is a complete binary tree, a heap with N nodes has log N height. It is useful to remove the highest or lowest priority element. It is typically represented as an array. There are two types of Heaps in the data structure.
2. Min Heap
   In a Min-Heap the key present at the root node must be less than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Min-Heap the minimum key element is present at the root. Below is the Binary Tree that satisfies all the properties of Min Heap.

1. Max Heap
   In a Max-Heap the key present at the root node must be greater than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Max-Heap the maximum key element is present at the root. Below is the Binary Tree that satisfies all the properties of Max Heap.

1. Note: a little help from GFG for better explaination (a good plateform for programmers).

Approach

Perfect, Now you have the idea of min heap and max heap, here we will use the min heap technique or strategy. let's discuss the steps one by one:

1. Push all the elements from the nums array to the minHeap array.
   Apply the heapify function to sort the minHeap array using the min heap technique, sorting the elements in place.
2. Store the length of the given array nums in a variable called number for future use.
3. Now, we will pop the elements from the lower portion of our array until we reach the kth largest element:
4. We will reduce the number variable one by one until we meet the element which is at the kth location.
   Once we reach the largest element, we will pop it is our answer like this!
   return heapq.heappop(minHeap)

Complexity

• Time complexity:
  The time complexity of this code is O(n + klogn), where n is the number of elements in the input list nums. The initial heapification of the minHeap takes O(n) time, and then the loop runs k times, each time performing a heappop operation which takes O(logn) time. Therefore, the total time complexity is O(n + klogn).
• Space complexity:
  The space complexity of this code is O(n) because the minHeap list is a copy of the nums list and its size is proportional to the size of the input list.

Plz, Make me happy by upvoting.

Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        minHeap = nums[:]
        heapq.heapify(minHeap)
        number = len(nums)
        while number > k:
            number -= 1
            heapq.heappop(minHeap)
            
        return heapq.heappop(minHeap)