🚀 Day 14: Top-K Elements Pattern (Amazon Interview Series)

Amazon loves ranking, recommendation, and selection problems—whether it’s finding the top-selling products, most visited pages, or most frequent queries. These problems usually need priority queues (heaps) or bucket sorting.

This is where the Top-K Elements Pattern shines.

---

🔑 What is the Top-K Elements Pattern?

The idea is to efficiently find the K largest/smallest/frequent elements without sorting the entire dataset.

• Sorting takes O(n log n).
• With a min-heap of size K, we can reduce this to O(n log k).
• In some frequency problems, bucket sort can achieve O(n).

When Amazon uses this pattern:

• Product ranking (top K sellers).
• Log analytics (most frequent IPs or queries).
• Performance optimization (K nearest servers, K largest numbers).

---

📝 Problem 1: Top K Frequent Elements

👉 Amazon-style phrasing:
Given an integer array nums and an integer k, return the k most frequent elements.

Java Solution

import java.util.*;

public class TopKFrequent {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums) {
            freq.put(n, freq.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> heap =
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            heap.add(entry);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        int[] result = new int[k];
        int i = 0;
        while (!heap.isEmpty()) {
            result[i++] = heap.poll().getKey();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        System.out.println(Arrays.toString(topKFrequent(nums, k))); // [1, 2]
    }
}

✅ Time Complexity: O(n log k)
✅ Why Amazon likes it: Handling huge logs/data streams efficiently.

---

📝 Problem 2: Kth Largest Element in an Array

👉 Amazon-style phrasing:
Find the kth largest element in an unsorted array.

Java Solution

import java.util.*;

public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int n : nums) {
            minHeap.add(n);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        int k = 2;
        System.out.println(findKthLargest(nums, k)); // Output: 5
    }
}

✅ Time Complexity: O(n log k)
✅ Alternative: Quickselect → O(n) average.

---

📝 Problem 3: K Closest Points to Origin

👉 Amazon-style phrasing:
Given a list of points on a 2D plane, return the k closest points to the origin (0,0).

Java Solution

import java.util.*;

public class KClosestPoints {
    public static int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap =
            new PriorityQueue<>((a, b) -> (distance(b) - distance(a)));

        for (int[] p : points) {
            maxHeap.add(p);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        int[][] result = new int[k][2];
        int i = 0;
        while (!maxHeap.isEmpty()) {
            result[i++] = maxHeap.poll();
        }
        return result;
    }

    private static int distance(int[] p) {
        return p[0] * p[0] + p[1] * p[1]; // avoid sqrt for efficiency
    }

    public static void main(String[] args) {
        int[][] points = {{1,3},{-2,2},{5,8},{0,1}};
        int k = 2;
        int[][] res = kClosest(points, k);
        for (int[] p : res) {
            System.out.println(Arrays.toString(p));
        }
    }
}

✅ Time Complexity: O(n log k)
✅ Why Amazon likes it: Real-world analogy → nearest servers or warehouses.

---

📝 Problem 4: Reorganize String

👉 Amazon-style phrasing:
Given a string s, rearrange it so that no two adjacent characters are the same. If not possible, return an empty string.

Java Solution

import java.util.*;

public class ReorganizeString {
    public static String reorganizeString(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

        maxHeap.addAll(freq.entrySet());

        StringBuilder result = new StringBuilder();
        Map.Entry<Character, Integer> prev = null;

        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> curr = maxHeap.poll();
            result.append(curr.getKey());
            curr.setValue(curr.getValue() - 1);

            if (prev != null && prev.getValue() > 0) {
                maxHeap.add(prev);
            }
            prev = curr;
        }

        return result.length() == s.length() ? result.toString() : "";
    }

    public static void main(String[] args) {
        String s = "aab";
        System.out.println(reorganizeString(s)); // Output: "aba"
    }
}

✅ Time Complexity: O(n log k)
✅ Why Amazon likes it: Scheduling tasks, arranging workloads, load balancing.

---

🎯 Key Takeaways

• Top-K Elements often involve min-heaps for efficiency.
• Use bucket sort or quickselect when optimizing further.
• Amazon asks this pattern often in recommendation systems, search ranking, and resource allocation problems.

---

📅 Next in the series (Day 15):
👉 Bit Manipulation Pattern – tricks Amazon loves in problems like Single Number, Missing Number, Counting Bits, and XOR-based puzzles.

---