Top K Elements Pattern

import java.util.*;
public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        // Min heap to keep track of K largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Add first k elements
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }
        // Process remaining elements
        for (int i = k; i < nums.length; i++) {
            // If current element is larger than smallest in heap
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();  // Remove smallest
                minHeap.offer(nums[i]);  // Add current
            }
        }
        // Top of min heap is Kth largest
        return minHeap.peek();
    }
    // Alternative: Using QuickSelect (average O(n))
    public static int findKthLargestQuickSelect(int[] nums, int k) {
        // Convert to find (n-k)th smallest for easier logic
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    private static int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int pivotIndex = partition(nums, left, right);
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }
    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("Kth largest (heap): " + findKthLargest(nums, k));
        System.out.println("Kth largest (quickselect): " + findKthLargestQuickSelect(nums, k));
        // Output: 5 (second largest)
    }
}

import java.util.*;
public class TopKFrequent {
    public static int[] topKFrequent(int[] nums, int k) {
        // Step 1: Count frequencies
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        // Step 2: Use min heap of size k (ordered by frequency)
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        // Step 3: Keep k most frequent elements in heap
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();  // Remove least frequent
            }
        }
        // Step 4: Extract results
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll().getKey();
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        int[] result = topKFrequent(nums, k);
        System.out.println("Top " + k + " frequent: " + Arrays.toString(result));
        // Output: [1, 2] (1 appears 3 times, 2 appears 2 times)
    }
}

import java.util.*;
public class KClosestPoints {
    public static int[][] kClosest(int[][] points, int k) {
        // Max heap based on distance (keep k closest)
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1])
        );
        // Add points to heap
        for (int[] point : points) {
            maxHeap.offer(point);
            // Keep only k closest points
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        // Extract k closest points
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] points = {{1, 3}, {-2, 2}, {5, 8}, {0, 1}};
        int k = 2;
        int[][] result = kClosest(points, k);
        System.out.println("K closest points:");
        for (int[] point : result) {
            System.out.println("[" + point[0] + ", " + point[1] + "]");
        }
        // Output: [0, 1] and [-2, 2] or [1, 3]
        // (distances: 1, 8, 89, 10)
    }
}