06. Top K Elements Technique

Top K Elements Technique

The "Top K Elements" technique involves finding the largest (or smallest) ( k ) elements from a dataset. This is a common problem in computer science with applications in data analysis, search engines, recommendation systems, and more.

Key Concepts

1. Priority Queue (Min-Heap or Max-Heap): A heap data structure that allows efficient extraction of the minimum or maximum element.
2. Quickselect Algorithm: A selection algorithm to find the ( k )th largest (or smallest) element in an unordered list.
3. Sorting: Sorting the entire dataset and then selecting the top ( k ) elements.
4. Bucket Sort or Counting Sort: Special techniques for integer data with a limited range.

Methods to Find Top K Elements

1. Heap (Priority Queue) Method: Efficient for dynamic data and large datasets.
2. Quickselect Algorithm: Efficient for static data with good average-case performance.
3. Sorting: Simple but less efficient for large datasets.
4. Bucket Sort or Counting Sort: Efficient for specific types of data.

1. Heap (Priority Queue) Method

Using a min-heap (for the largest ( k ) elements) or max-heap (for the smallest ( k ) elements) to maintain the top ( k ) elements.

Code:

import heapq

def top_k_elements(nums, k):
    # Use a min-heap for the largest k elements
    if k == 0:
        return []

    min_heap = nums[:k]
    heapq.heapify(min_heap)

    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heappushpop(min_heap, num)

    return min_heap

# Example usage:
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(top_k_elements(nums, k))  # Output: [5, 6]

Explanation:

1. Initialize: Create a min-heap with the first ( k ) elements.
2. Process: For each remaining element, if it is larger than the smallest element in the heap, replace the smallest element.
3. Result: The heap contains the top ( k ) largest elements.

2. Quickselect Algorithm

Quickselect is a selection algorithm to find the ( k )th largest (or smallest) element in an unordered list, which can then be used to find the top ( k ) elements.

Code:

import random

def quickselect(nums, k):
    def partition(left, right, pivot_index):
        pivot_value = nums[pivot_index]
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        store_index = left
        for i in range(left, right):
            if nums[i] < pivot_value:
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1
        nums[right], nums[store_index] = nums[store_index], nums[right]
        return store_index

    def select(left, right, k_smallest):
        if left == right:
            return nums[left]
        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            return select(left, pivot_index - 1, k_smallest)
        else:
            return select(pivot_index + 1, right, k_smallest)

    n = len(nums)
    return select(0, n - 1, n - k)

# Example usage:
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(quickselect(nums, k))  # Output: 5

Explanation:

1. Partition: Use the partitioning step from the QuickSort algorithm to position the pivot element correctly.
2. Select: Recursively select the ( k )th smallest element, which corresponds to the ( (n - k) )th largest element.
3. Result: The algorithm returns the ( k )th largest element, and the elements larger than it can be found in the list.

3. Sorting

Sorting the array and selecting the top ( k ) elements.

Code:

def top_k_elements_sort(nums, k):
    nums.sort(reverse=True)
    return nums[:k]

# Example usage:
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(top_k_elements_sort(nums, k))  # Output: [6, 5]

Explanation:

1. Sort: Sort the array in descending order.
2. Select: Take the first ( k ) elements from the sorted array.
3. Result: These are the top ( k ) largest elements.

---

4. Bucket Sort or Counting Sort

For integer data with a limited range, bucket sort or counting sort can be efficient.

Code (Counting Sort for a limited range):

def top_k_elements_counting_sort(nums, k):
    max_val = max(nums)
    count = [0] * (max_val + 1)

    for num in nums:
        count[num] += 1

    result = []
    for num in range(max_val, -1, -1):
        while count[num] > 0 and len(result) < k:
            result.append(num)
            count[num] -= 1

    return result

# Example usage:
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(top_k_elements_counting_sort(nums, k))  # Output: [6, 5]

Explanation:

1. Count Frequency: Count the frequency of each element.
2. Select: Traverse the count array from the highest value, selecting elements until ( k ) elements are selected.
3. Result: These are the top ( k ) largest elements.

---

If you want to find the largest K numbers and the smallest K numbers in an array simultaneously, you can use a combination of Min-Heap and Max-Heap. Here's a step-by-step approach in English:

Approach:

1. Initialization:
   • Create a Min-Heap to keep track of the largest K elements.
   • Create a Max-Heap to keep track of the smallest K elements. (Since Python's heapq module only provides a Min-Heap, you can simulate a Max-Heap by pushing negative values.)
2. Iterate through the array:
   • For each element in the array:
     • Add it to the Min-Heap if it's larger than the smallest element in the heap (the root). If the Min-Heap exceeds size K, remove the smallest element.
     • Add it to the Max-Heap (with a negative sign) if it's smaller than the largest element (the root). If the Max-Heap exceeds size K, remove the largest element.
3. Results:
   • After processing all elements, the Min-Heap contains the largest K elements, and the Max-Heap (with the negative signs removed) contains the smallest K elements.

This method ensures that you maintain both the largest and smallest K elements as you process the array, and the time complexity remains efficient.

Code:

import heapq

def find_largest_and_lowest_k_numbers(nums, k):
    # Min-Heap for largest K numbers
    min_heap = nums[:k]
    heapq.heapify(min_heap)

    # Max-Heap for smallest K numbers (using negative values)
    max_heap = [-num for num in nums[:k]]
    heapq.heapify(max_heap)

    # Process the remaining elements in the array
    for num in nums[k:]:
        # Maintain the largest K numbers
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)

        # Maintain the smallest K numbers
        if -num > max_heap[0]:
            heapq.heapreplace(max_heap, -num)

    # Convert the Max-Heap back to positive numbers
    lowest_k = [-x for x in max_heap]

    return min_heap, lowest_k

# Example usage
nums = [3, 2, 1, 5, 6, 4, 8, 7]
k = 3
largest_k, lowest_k = find_largest_and_lowest_k_numbers(nums, k)
print("Largest K:", largest_k)  # Output: [6, 7, 8]
print("Lowest K:", lowest_k)    # Output: [1, 2, 3]

---

215. Kth Largest Element in an Array

Problem: Given an integer array nums and an integer k, return the kth largest element in the array.

Approach:

• Min-Heap: Use a min-heap to keep track of the largest k elements in the array. The top element of the heap will be the kth largest element.
• Quickselect: Another approach is to use the Quickselect algorithm, which is based on the partition method used in QuickSort. This method is efficient with an average time complexity of (O(n)).

Min-Heap Code:

import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heappushpop(heap, num)
    return heap[0]

# Example usage:
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(nums, k))  # Output: 5

Quickselect Code:

def find_kth_largest(nums, k):
    k = len(nums) - k

    def quickselect(l, r):
        pivot, p = nums[r], l
        for i in range(l, r):
            if nums[i] <= pivot:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1
        nums[p], nums[r] = nums[r], nums[p]
        if p > k:
            return quickselect(l, p - 1)
        elif p < k:
            return quickselect(p + 1, r)
        else:
            return nums[p]

    return quickselect(0, len(nums) - 1)

# Example usage:
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(nums, k))  # Output: 5

---

---

23. Merge k Sorted Lists

Problem: You are given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Approach:

• Min-Heap: Use a min-heap to efficiently merge the k sorted linked lists. Each time, extract the smallest element from the heap and add it to the merged list.

Code:

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __lt__(self, other):
        return self.val < other.val

def merge_k_lists(lists):
    min_heap = []
    for root in lists:
        if root:
            heapq.heappush(min_heap, root)

    dummy = ListNode()
    curr = dummy

    while min_heap:
        smallest_node = heapq.heappop(min_heap)
        curr.next = smallest_node
        curr = curr.next
        if smallest_node.next:
            heapq.heappush(min_heap, smallest_node.next)

    return dummy.next

# Example usage:
# Assuming ListNode class is defined and linked lists are created.
lists = [list1, list2, list3]  # Example linked-lists
result = merge_k_lists(lists)

Explanation:

1. Min-Heap: Each list's head is added to the heap. The heap helps efficiently find and add the smallest element across all lists to the final merged list.

---

---

703. Kth Largest Element in a Stream

Problem: Design a class to find the kth largest element in a stream. Implement the KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Approach:

• Min-Heap: Maintain a min-heap of size k. The smallest element in the heap is the kth largest element in the stream.

Code:

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.min_heap = nums
        heapq.heapify(self.min_heap)
        while len(self.min_heap) > k:
            heapq.heappop(self.min_heap)

    def add(self, val):
        heapq.heappush(self.min_heap, val)
        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)
        return self.min_heap[0]

# Example usage:
k = 3
nums = [4, 5, 8, 2]
kthLargest = KthLargest(k, nums)
print(kthLargest.add(3))  # Output: 4
print(kthLargest.add(5))  # Output: 5
print(kthLargest.add(10))  # Output: 5
print(kthLargest.add(9))  # Output: 8
print(kthLargest.add(4))  # Output: 8

Summary

• Heap (Priority Queue) Method:
  • Pros: Efficient for dynamic data and large datasets.
  • Cons: Slightly complex to implement.
• Quickselect Algorithm:
  • Pros: Good average-case performance, efficient for static data.
  • Cons: Worst-case performance can be poor.
• Sorting:
  • Pros: Simple to implement.
  • Cons: Less efficient for large datasets ((O(n \log n))).
• Bucket Sort or Counting Sort:
  • Pros: Very efficient for integer data with a limited range.
  • Cons: Not general-purpose, requires specific data characteristics.

Choosing the right method depends on the characteristics of the dataset and the specific requirements of the problem at hand.