The "Top K Elements" pattern is commonly used in coding interviews when you need to find the K largest or smallest elements in a collection. It's particularly useful when K is significantly smaller than the total number of elements.

Here's an explanation of the pattern along with example questions and solutions using this approach:

Pattern: Top K Elements

1. Initialize a data structure to store the top K elements, such as a min-heap, max-heap, or priority queue.
2. Iterate through the collection of elements, and for each element:
   • If the data structure is not full (contains fewer than K elements), add the element.
   • If the data structure is full and the current element is greater (or smaller, depending on the problem) than the smallest (or largest) element in the data structure, replace the smallest (or largest) element with the current element.
3. The data structure will now contain the top K elements.

Example Questions:

1.  

   1. Find the K largest elements: Given an array of integers, find the K largest elements.

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

      Solution: We can use a min-heap to solve this problem. Initialize a min-heap and iterate through the array. If the min-heap is not full, add the element. If the min-heap is full and the current element is greater than the smallest element in the min-heap, replace the smallest element with the current element. At the end, the min-heap will contain the K largest elements.
      
      

      import heapq
      
      def find_k_largest_elements(nums, k):
          min_heap = []
          for num in nums:
              if len(min_heap) < k:
                  heapq.heappush(min_heap, num)
              elif num > min_heap[0]:
                  heapq.heappushpop(min_heap, num)
          return min_heap
      
      # Example usage:
      nums = [3, 1, 5, 12, 2, 11]
      k = 3
      result = find_k_largest_elements(nums, k)
      print(result)
      

      
      
      
      

   2. Find the K smallest elements: Given an array of integers, find the K smallest elements.

      Example: Input: [9, 4, 7, 1, -2, 6, 5], K = 3 Output: [-2, 1, 4]

      Solution: We can use a max-heap to solve this problem. Initialize a max-heap and iterate through the array. If the max-heap is not full, add the element. If the max-heap is full and the current element is smaller than the largest element in the max-heap, replace the largest element with the current element. At the end, the max-heap will contain the K smallest elements.
      
      

      import heapq
      
      def find_k_smallest_elements(nums, k):
          max_heap = []
          for num in nums:
              if len(max_heap) < k:
                  heapq.heappush(max_heap, -num)
              elif -num > max_heap[0]:
                  heapq.heappushpop(max_heap, -num)
          return [-num for num in max_heap]
      
      # Example usage:
      nums = [9, 4, 7, 1, -2, 6, 5]
      k = 3
      result = find_k_smallest_elements(nums, k)
      print(result)
      

      
      
      
      

   3. Find the Kth largest element: Given an array of integers, find the Kth largest element.

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

      Solution: We can modify the previous solution to find the Kth largest element. Instead of maintaining a heap of size K, we maintain a min-heap of size K. After iterating through the array, the Kth largest element will be at the root of the min-heap.
      
      

      import heapq
      
      def find_kth_largest(nums, k):
          min_heap = []
          for num in nums:
              if len(min_heap) < k:
                  heapq.heappush(min_heap, num)
              elif num > min_heap[0]:
                  heapq.heappushpop(min_heap, num)
          return min_heap[0]
      
      # Example usage:
      nums = [3, 1, 5, 12, 2, 11]
      k = 4
      result = find_kth_largest(nums, k)
      print(result)
      

      
      
      
      

   These examples demonstrate how to use the "Top K Elements" pattern to solve different problems involving finding the K largest or smallest elements.